[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]

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?