Uniform digit generator

Question

The question goes as follows:

Let there be a random digit generator, generating the numbers $0,1,2,...,9$ uniformly and independently. The generator writes the numbers from left to right.

a) What is the expected value for the number of different digits appearing between two zeroes?

b) What is the distribution of the number of times the number $0$ appeared between two appearances of $9$?

c) Assuming the first digit is 8. What is the expected value of the number made up from the first four digits?

Well, 'c' was pretty simple, and is just $8000 + 4.5*100 + 4.5*10 + 4.5*1 = 8499.5$, since the expectation of the digit generated is $4.5$ and they are independent.

I had problems with solving 'a' and 'b', and would be happy to see both rigorous approach and simple approach if there are.

Thanks.

Answer 1

For a, the probability that a $1$ comes up between two zeros is $\frac 12$ because it just comes down to which comes first, the next $1$ or the next $0$. Make an indicator variable of the fact that a $1$ is there. Its expected value is $\frac 12$. By linearity of expectation, the expected number of different digits between two zeros is $9 \cdot \frac 12=4.5$

For b, the chance we have no zeros is $\frac 12$ because a $9$ has to come before the next zero. Once that $0$ comes, it is again $\frac 12$ that the next $0$ comes before the next $9$, so the chance of $n$ zeros is $\frac 1{2^{n+1}}$

Answer 2

One rigorous solution for b) can be this:

Let $d$ be the number of (not necessarily distinct) digits betweens two appearances of number 9, and $x$ the number of zeroes that appear in these digits, then $$P(x=k|d) = \frac{{d \choose k} 8^{d-k}}{9^d}$$ because that's the number of ways you can accomodate $k$ zeroes and $d-k$ other digits (distinct from zero or nine) in $d$ slots, and the universe has $9^d$ posibilities (any digit distinct from 9 in any of the $d$ places).

Since $d$ can be viewed as the number of trials you have to do before getting another 9, $d$ follows a geometric distribution with $p = \frac{1}{10}$ $$P(d) = (\frac{9}{10})^d \frac{1}{10}$$

Now, by the law of total probability

$$P(x = k) = \sum_{d=k}^{\infty} P(x=k|d) P(d) = \sum_{d=k}^{\infty} \frac{{d \choose k} 8^{d-k}}{9^d} (\frac{9}{10})^d \frac{1}{10}$$

If you opperate this equation using $u = d-k$ instead of $d$, you get

$$P(x = k) =\frac{1}{10^{k+1}} \sum_{u=0}^{\infty} {{u+k} \choose k} (\frac{4}{5})^{u} = \frac{5^{k+1}}{10^{k+1}} = \frac{1}{2^{k+1}}$$