How long will it take random number generator to produce certain strings?
Sebastian Wright 
Suppose an ideal random number generator generates an infinite string of digits (0-9) at a rate of 1000 digits per second.
How long, on average, will it take for the generator to produce a 9? How long, on average, will it take to produce two 9's (not necessarily in a row, just the first two 9's)? How long for any unique $n$ digit string?
I know to use expectation here, given that each digit is equally probable. My thought process is that I want to find the expectation value in each case for how many digits it will take to produce the desired result, then multiply by the rate (seconds/digit). I'm not sure how to do this for each case though.
$\endgroup$ 111 Answer
$\begingroup$Denote $p = 1/10$ to keep the formulas short.
Let $E$ be the expected number of digits the generator produces before we see the first $9$. Then$$ E = p \cdot 1 + (1-p) \cdot (1 + E) $$because if we see a $9$ right away, the number of digits we needed was $1$, and if we don't, then we need one plus the number of additional digits. This additional number of digits has the same expected value $E$ as the original, because the generator is "memoryless": seeing a non-$9$ doesn't make a $9$ on the next steps any more or less likely. When we solve the equation, we get $E = 1/p$, which is $10$.
Then you want to compute the expected number of digits before seeing $n$ nines, not necessarily as a contiguous string (so something like $0 9 0 7 5 9 9 3 9$ would count as a success for $n = 4$). Seeing $n$ nines is precisely the same as seeing one nine, then one nine after that, then one nine after that, and so on $n$ times. The number of digits needed is the sum of the number of digits in these $n$ processes, and they are independent because the generator is memoryless. The expected number of digits is $E + E + E + \cdots + E = E n = 10 n$ where there are $n$ copies of $E$ in the sum.
For any sequence $s$ of $n$ digits, the expected number of digits produced before $s$ occurs as a possibly non-contiguous subsequence is $10 n$, for the same reason.
For a contiguous sequence of $n$ nines, the computations are still pretty simple. Let $E_n(k)$ be the expected number of additional digits the generator needs to produce before we see $n$ nines, given that we have just seen $k$ consecutive nines. For example, if the generator has produced $4 5 9 2 2 9 9$, we'd be looking at $E_n(2)$. Then $E_n(n) = 0$ because we don't need any more digits after $n$ nines, and for $0 \leq k < n$ we have$$ E_n(k) = p(1 + E_n(k+1)) + (1-p)(1+E_n(0)) $$because seeing a $9$ makes the just-seen sequence one digit longer, but seeing anything else resets it. Now we have a finite system of linear equations in the $E_n(k)$ that we can solve. By induction we can prove $E_n(0) = E_n(k) + \frac{p^{-k} - 1}{1 - p}$, and at $k = n$ this means $E_n(0) = \frac{p^{-n}-1}{1-p} = 10 (10^n - 1) / 9$.
$\endgroup$ 2
