Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks for the answer. As I asked a bit above, is there a more simple way to calculate the expected number of draws? If we cant use discrete stochastic processes. –  user7778 May 18 at 17:08
    
The answer by Byron Schmuland is far more efficient. But I cannot think of a way fundamentally different from the one above in general. For a larger number of states, one would want to express things in matrix terms, and use linear algebra machinery. –  André Nicolas May 18 at 17:20
add comment

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.

share|improve this answer
    
Thanks for the answer. Is there any other way to solve this problem? Without using the Markov-theory. I was thinking about fit a binomial distibution or just calculate the distribution and then the expected value by definiton but It seemed to be way harder. –  user7778 May 18 at 16:49
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.