0

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.

  • 1
    Well, if you have an event with probability $p=\frac{1}{10}$, then the expected waiting time for it to happen is of course $10$ repeats. If you do $1000$ repeats a second, then in seconds that's $\frac{10}{1000}= \frac{1}{100}~\text{seconds}$ – Matti P. Oct 25 '19 at 12:01
  • Ah, thanks. So for two 9's, it which just be $2/100$ seconds? And for any digit $n$, it would be $10^n/1000$? –  Oct 25 '19 at 12:09
  • 1
    So let's say that "success = number 9 appears" and then the probability of success is $\frac{1}{10}$. So now we ask "what is the expected number of trials before the first success" - the answer is $10$. Explanation is here: https://www.geeksforgeeks.org/expected-number-of-trials-before-success/ – Matti P. Oct 25 '19 at 12:12
  • 1
    As for "expected number of trials before second success" - that's a bit trickier question. https://math.stackexchange.com/questions/102673/what-is-the-expected-number-of-trials-until-x-successes – Matti P. Oct 25 '19 at 12:13
  • Thanks. That makes sense, it's geometric. But for any string, say the string "999", that has a 10^3 chance of occurring, so would it take $10^3/1000$, or 1 second, to produce (on average)? –  Oct 25 '19 at 12:18
  • 1
    Not exactly, for e.g. the string 999 -- the expected waiting time will be a bit more than 1 second, because of the overlaps between initial and final substrings of 999. But the expected waiting time for e.g. 774 would be 1 second. – Ned Oct 25 '19 at 12:22
  • 1
    I agree with @Ned. In the case of "999", we cannot just take $p=\frac{1}{10^3}$. So that's wrong. Instead, we should consider single digits with $p=\frac{1}{10}$ and think about the first occurrance of three consequtive successes – Matti P. Oct 25 '19 at 12:24
  • 1
    Also, the expected waiting time for the $k$-th "9" will be $k/1000$ by linearity of expectation. – Ned Oct 25 '19 at 12:27
  • Is this for $k$ nines in a row, or $k$ nines total? –  Oct 25 '19 at 12:42
  • 1
    Total. This is by noting that the total time waited for $k$ nines in a row can be described as the amount of time waited until the first nine added to the amount of time between the first and second nine, added to the amount of time between the second and third nine, and so on... each of which are effectively the same calculation. – JMoravitz Oct 25 '19 at 13:13
  • How could the wait time be calculated for two 9's in a row? (as opposed to two 9's total) –  Oct 25 '19 at 13:55

1 Answers1

0

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$.

Ilkka Törmä
  • 799