exercise:C04b09a77f: Difference between revisions
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> Here is an elegant method due to Guibas and Odlyzko<ref group="Notes" >L. J. Guibas and A. M. Odlyzko, “String Overlaps, Pattern Matching, and Non-transitive Games,” ''Journal of Combinatorial Theory,'' Series A, vol. 30 (1981), pp. 183--208.<...") |
No edit summary |
||
Line 5: | Line 5: | ||
\newcommand{\secstoprocess}{\all} | \newcommand{\secstoprocess}{\all} | ||
\newcommand{\NA}{{\rm NA}} | \newcommand{\NA}{{\rm NA}} | ||
\newcommand{\mathds}{\mathbb}</math></div> Here is an elegant method due to Guibas and | \newcommand{\mathds}{\mathbb}</math></div> Here is an elegant method due to Guibas and Odlyzko<ref group="Notes" >L. J. | ||
Odlyzko<ref group="Notes" >L. J. | Guibas and A. M. Odlyzko, “String Overlaps, Pattern Matching, and Non-transitive Games,” | ||
Guibas and A. M. Odlyzko, “String Overlaps, Pattern Matching, and | ''Journal of Combinatorial Theory,'' Series A, vol. 30 (1981),pp. 183--208.</ref> to obtain the expected time to reach a pattern, say HTH, for the first time. Let <math>f(n)</math> be the number of sequences of length <math>n</math> which do not have the pattern HTH. Let <math>f_p(n)</math> be the number of sequences that have the pattern for the first time after <math>n</math> tosses. To each element of <math>f(n)</math>, add the pattern HTH. Then divide the resulting sequences into three subsets: the set where HTH occurs for the first time at time <math>n + 1</math> (for this, the original sequence must have ended with HT); the set where HTH occurs for the first time at time <math>n + 2</math> (cannot happen for this pattern); and the set where the sequence HTH occurs for the first time at time <math>n + 3</math> (the original sequence ended with anything except HT). Doing this, we have | ||
Non-transitive Games,” | |||
''Journal of Combinatorial Theory,'' Series A, vol. 30 (1981), | |||
pp. 183--208.</ref> to obtain | |||
the expected time to reach a pattern, say HTH, for the first time. Let <math>f(n)</math> | |||
be the | |||
number of sequences of length <math>n</math> which do not have the pattern HTH. Let | |||
<math>f_p(n)</math> be the | |||
number of sequences that have the pattern for the first time after <math>n</math> tosses. | |||
To each | |||
element of <math>f(n)</math>, add the pattern HTH. Then divide the resulting sequences | |||
into three subsets: the set where HTH occurs for the first time at time <math>n + 1</math> | |||
(for this, the original sequence must have ended with HT); the set where HTH | |||
occurs for the first time at time <math>n + 2</math> (cannot happen for this pattern); and | |||
the set where the sequence HTH occurs for the first time at time <math>n + 3</math> (the | |||
original sequence ended with anything except HT). Doing this, we have | |||
<math display="block"> | <math display="block"> |
Latest revision as of 23:45, 15 June 2024
Here is an elegant method due to Guibas and Odlyzko[Notes 1] to obtain the expected time to reach a pattern, say HTH, for the first time. Let [math]f(n)[/math] be the number of sequences of length [math]n[/math] which do not have the pattern HTH. Let [math]f_p(n)[/math] be the number of sequences that have the pattern for the first time after [math]n[/math] tosses. To each element of [math]f(n)[/math], add the pattern HTH. Then divide the resulting sequences into three subsets: the set where HTH occurs for the first time at time [math]n + 1[/math] (for this, the original sequence must have ended with HT); the set where HTH occurs for the first time at time [math]n + 2[/math] (cannot happen for this pattern); and the set where the sequence HTH occurs for the first time at time [math]n + 3[/math] (the original sequence ended with anything except HT). Doing this, we have
Thus,
If [math]T[/math] is the time that the pattern occurs for the first time, this equality states that
Show that if you sum this equality over all [math]n[/math] you obtain
Show that for any integer-valued random variable
and conclude that [math]E(T) = 10[/math]. Note that this method of proof makes very clear that [math]E(T)[/math] is, in general, equal to the expected amount the casino pays out and avoids the martingale system theorem used by Li.
Notes