exercise:A6a5ee3e19: 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> Assume that an experiment has <math>m</math> equally probable outcomes. Show that the expected number of independent trials before the first occurrence of <math>k</math> consecutive occurrences of one of these outcomes is <math>(m^k - 1)/(m - 1)...") |
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> Assume that an experiment has <math>m</math> equally probable | \newcommand{\mathds}{\mathbb}</math></div> Assume that an experiment has <math>m</math> equally probable outcomes. Show that the expected number of independent trials before the first occurrence of <math>k</math> consecutive occurrences of one of these outcomes is <math>(m^k - 1)/(m - 1)</math>. | ||
outcomes. | |||
Show that the expected number of independent trials before the first occurrence | '' Hint'': Form an absorbing Markov chain with states 1, 2, ..., <math>k</math> with | ||
of | |||
<math>k</math> consecutive occurrences of one of these outcomes is <math>(m^k - 1)/(m - 1)</math>. | |||
'' Hint'': Form an absorbing Markov chain with states 1, 2, | |||
state <math>i</math> representing the length of the current run. The expected time until | state <math>i</math> representing the length of the current run. The expected time until | ||
a run of <math>k</math> is 1 more than the expected time until absorption for the chain | a run of <math>k</math> is 1 more than the expected time until absorption for the chain | ||
Latest revision as of 22:46, 15 June 2024
Assume that an experiment has [math]m[/math] equally probable outcomes. Show that the expected number of independent trials before the first occurrence of [math]k[/math] consecutive occurrences of one of these outcomes is [math](m^k - 1)/(m - 1)[/math].
Hint: Form an absorbing Markov chain with states 1, 2, ..., [math]k[/math] with state [math]i[/math] representing the length of the current run. The expected time until a run of [math]k[/math] is 1 more than the expected time until absorption for the chain started in state 1. It has been found that, in the decimal expansion of pi, starting with the 24,58,01st digit, there is a run of nine 7's. What would your result say about the expected number of digits necessary to find such a run if the digits are produced randomly?