Conditional expectation of random variable

Question

I have this home assignment in Introduction to Probability, and I'm not comfortable with definitions and heuristics. I really need someone to check if I'm even in the right direction.
The question: Ben chooses random numbers from 0,1,...,9 independently and with uniform probability, and arranges them in a sequence by the order of picking. What is the expectation of the amount of distinct numbers between the first two appearances of the number 0.

My way to start: define random variable $X$ for the amount of distinct numbers between first two appearances of 0. Define another random variable $Y$ that will return the number that's adjacent to the first $0$, now $$E[X]=E[E[X|Y]]=E[P(Y=0)E[x|Y=0]+P(Y\neq0)E[X|Y\neq0]]$$ since $Y=0 \implies X=0$ we got $E[X]=E[P(Y\neq0)E[X|Y\neq0]]=P(Y\neq0)E[X|Y\neq0]$, of course $P(Y\neq0)=\frac{9}{10}$, and starting counting from the index $Y$ as if we are "starting fresh" we get $E[X|Y\neq0]=E[X+1]$. So: $$\array{{E[X] = \frac{9}{10}E[X+1]}\\{\Downarrow}\\{E[X]=9}}$$ Which is kind of makes sense but I'm not sure at all.

Answer 1

I am going to assume that you don't count $0$ as one of the distinct digits seen between the first and second $0$s in the sequence. So for instance if the sequence is $3,5,3,3,0,7,3, 7,0$, I would say there were $X=2$ distinct digits between the first and second $0$s (namely $7$ and $3$).

With this interpretation, the expected number of distinct digits seen between the first two zeros should be $4.5$.

To see this, imagine that after seeing the first $0$, Ben keeps picking until he has seen every digit at least once (including a second $0$), and writes down the order in which distinct digits only appear after the first $0$. For instance he might write down $3,5,4,8,0,9,7,1,2,6$ (he does not list repeats). In the example just given, he would have $X=4$ since the four digits $3,5,4,8$ occurred between zeros.

The value of $X$ is completely determined by the position of $0$ on this revised list. And $0$ has an equal chance of being in any of the ten positions of the revised list; and so there is a $\frac{1}{10}$ probability that $X$ takes on each of the values $0, 1,2,\dots,9$.

Answer 2

Edited:   (I missed the key point on the first reading: we're counting distinct digits.)

---

Ah!   Everything makes sense until you say "we are starting fresh."   That would be true if we were counting the number of non-zero digits until the next $0$, which would be a geometric distribution.   However, we wish to count the number of distinct non-zero digits, so we don't have a memoryless situation.

As you did, we begin by partitioning on the event that we encounter (or don't) no other digits before the next zero.

$$\begin{align} \mathsf E(X) &= \mathsf P(X=0)\mathsf E(X\mid X=0) + \mathsf P(X>0)\mathsf E(X\mid X>0) \\ &= 0+ \tfrac 9{10}\mathsf E(X\mid X>0) \end{align}$$

However, this process is not memoryless, so $\mathsf E(X\mid X>0)\neq 1+\mathsf E(X)$ .   To evaluate this we need to partition on whether or not we encounter a second distinct digit before the next zero, given we've encountered one such.

The probability of not encountering another distinct digit (after the first) is the probability of encountering 0 or more of that first digit, then encountering the zero. $$\mathsf P(X=1\mid X>0)=\tfrac 1{10}\left(\sum_{n=0}^\infty \big(\tfrac 1 {10}\big)^n\right) = \tfrac 1 9$$

Similarly the probability of not encountering a third distinct digit (given we've encountered two) is the probability of encountering 0 or more of those two digits, then encountering the zero. $$\mathsf P(X=2\mid X\geq 2)=\tfrac 1{10}\left(\sum_{n=0}^\infty \big(\tfrac 2 {10}\big)^n\right) = \tfrac 1 8$$

And in general:$$\mathsf P(X=r\mid X\geq r)=\tfrac 1{10}\left(\sum_{n=0}^\infty \big(\tfrac r {10}\big)^n\right) = \tfrac 1 {10-r} \qquad \text{for }r < 10$$

So we have:

$$\begin{align} \mathsf E(X\mid X\geq r) & = \mathsf P(X=r\mid X\geq r)\cdot\mathsf E(X\mid X=r)+\mathsf P(X>r\mid X\geq r)\cdot\mathsf E(X\mid X>r) \\ & = \tfrac r{10-r}+\tfrac {9-r} {10-r}\mathsf E(X\mid X\geq r+1) \end{align} $$

Thus: $$\begin{align} \mathsf E(X) & = \tfrac 9{10}( \tfrac 1{9}+\tfrac {8} {9} ( \tfrac 2{8}+\tfrac {7} {8} ( \tfrac 3{7}+\tfrac {6} {7} ( \tfrac 4{6}+\tfrac {5} {6} ( \tfrac 5{5}+\tfrac {4} {5} ( \tfrac 6{4}+\tfrac {3} {4} ( \tfrac 7{3}+\tfrac {2} {3} ( \tfrac 8{2}+\tfrac {1} {2} ( \tfrac 9{1}+\tfrac {0} {1} ))))))))) \\ ~ & = \tfrac 1{10}( 1+ (2+ (3+ (4+(5+(6+(7+ (8+ (9 ))))))))) \\ ~ & = \tfrac 9 2 \end{align}$$

---

What you were doing was counting failures before the next success (the occurrence of a 0).   That is, you were treating it as dealing with a geometric distribution.

Partitioning on the first trial's result is one classic way of obtaining this.

Let $Y$ be the count of failures before the next success, where, on any arbitary trial, the probability of success is $p$; independent of any previous trial results (the process has no memory).   Then we have

$\begin{align} \mathsf E(Y\mid Y>0) & = 1+\mathsf E(Y) \tag{memoryless} \\[1ex] \mathsf P(Y>0) & = (1-p) \tag{failed first trial} \\[1ex] \mathsf E(Y\mid Y=0) & = 0 \tag{obviously} \\[2ex] \mathsf E(Y) & = \mathsf P(Y=0)\mathsf E(Y\mid Y=0)+\mathsf P(Y > 0)\mathsf E(Y\mid Y>0) \\[1ex] & = 0 + (1-p)\cdot(1+\mathsf E(Y)) \\[2ex] \therefore \mathsf E(Y) & = \frac{1-p}{p} \end{align}$