Expected value of number of draws

Question

We have $5$ number in a bag: $(1,3,5,7,9)$. We draw one from the bag and then put it back. We do this until the sum of the numbers can be divided by $3$. Whats the expected value of the number of draws?

My idea was to solve it with Markov-chains: States: $0,1,2$. So numbers$\mod 3$.

The matrix will be: $\begin{pmatrix} 2/5 & 2/5 & 1/5 \\ 1/5 & 2/5 & 2/5 \\ 2/5 & 1/5 & 2/5 \end{pmatrix}$

Then we have an equation system: $k_1=1+2/5k_1+2/5k_2$, $\ k_2=1+1/5k_1+2/5k_2$ and $k_3=0$.

Even if I solve this, I'm not sure how to continue. Thanks for help.

Answer 1

We use your idea, but partly for ease of typing we use different notation. Say that we are in State $1$ if the sum so far is congruent to $1$ modulo $3$, and that we are in State $2$ if the sum is congruent to $2$. Let $m$ be the mean waiting time. Let $a_1$ be the additional mean waiting time, given we are in State $1$, and $a_2$ the additional mean waiting time given that we are in State $2$.

On the first pick, we either get something divisible by $3$, in which case we have spent $1$ pick, and our additional waiting time is $0$. Or else we get a $1$ or a $7$, and our mean additional waiting time is $a_1$. Or else we get a $5$, and our mean additional waiting time is $a_2$. Thus $$m=1+\frac{2}{5}a_1+\frac{1}{5}a_2.\tag{1}$$ Suppose we are in State $1$, and do another trial. If we get a $3$ or a $9$, we stay in State $1$, and our additional expected time remains at $a_1$. If we get a $1$ or a $7$, our additional expected waiting time becomes $a_2$. And if we get $5$, we are finished. Thus $$a_1=1+\frac{2}{5}a_1+\frac{2}{5}a_2.\tag{2}$$ Similarly, $$a_2=1+\frac{1}{5}a_1+\frac{2}{5}a_2.\tag{3}$$ Solve the last two equations for $a_1$ and $a_2$, and substitute in Equation (1).

Answer 2

Since $P$ is a doubly stochastic matrix, the invariant measure is uniform, i.e., $\pi=(1/3,1/3,1/3)$. Therefore the expected number of steps to return to state $0$ is $\mathbb{E}_0(T_0)=1/\pi_0=3$.

This is a method well worth knowing, and I've used it before on this site here, here, and here, for example.

Answer 3

We may also consider an absorbing markov chain:

$$ A=\left(\begin{array}{rrrr} 0 & \frac{1}{5} & \frac{2}{5} & \frac{2}{5} \\ 0 & \frac{2}{5} & \frac{1}{5} & \frac{2}{5} \\ 0 & \frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\ 0 & 0 & 0 & 1 \end{array}\right) $$

Expected time to absorbing state is then given by

$$(I-Q)^{-1}\cdot c$$ where $$ I=\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right), Q=\left(\begin{array}{rrr} 0 & \frac{1}{5} & \frac{2}{5} \\ 0 & \frac{2}{5} & \frac{1}{5} \\ 0 & \frac{2}{5} & \frac{2}{5} \end{array}\right), c= \left(\begin{array}{r} 1 \\ 1 \\ 1 \end{array}\right)$$

which is 3.