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.

Consider a null sequence $A=\{\}$. Each time I will include the output in $A$ after throwing a dice. I will stop when $\{1,2,3\} \subseteq A$. On average how many number of throws is required?

share|improve this question

2 Answers 2

up vote 0 down vote accepted

If you successively toss a biased coin with probability of heads $p$, the expected number of throws before you see the first success is $\frac{1}{p}$. Your question can be decomposed into three such games. Game 1: Keep throwing a dice until one of the three numbers $\{1,2,3\}$ occurs. This has a success probability of $1/2$ and hence the expected number of trials is $2$.

Game 2: Assume without loss of generality that you obtained $1$ when you succeeded in Game 1. Then you keep throwing dice until one of $\{2,3\}$ occurs. This has success probability $1/3$ and hence expected number of trials is $3$.

Game 3: Assume without loss of generality that you obtained $2$ when you succeeded in Game 2. Then you keep throwing dice until $3$ occurs. This has success probability $1/6$ and hence requires $6$ trials on average.

Thus the average number of throws required is (by linearity of expectation) $2+3+6=11$.

Note: To answer your inconsistency with experiments, let's compute the variance. Note that the 3 games are independent of each other. Therefore, variance is also linear. Variance of a geometric distribution is $\frac{1-p}{p^2}$. Hence variance of your game is $$\frac{1/2}{1/4}+\frac{2/3}{1/9}+\frac{5/6}{1/36}=2+6+30=38.$$ Hence the standard deviation is $\sqrt{38}\approx 6.1644$. Thus if you were to repeat the experiment $n$ times, the mean is $9$ and the standard deviation is $6.1644/\sqrt{n}$. Thus as long as your answer is within 3 standard deviations, your experiment is correct. To be more accurate, increase the number of trials $n$.

share|improve this answer

The expected value of the waiting time for an event occuring with probability $p$ is $\frac1p$. The event "found a new one" occurs with probability $\frac36=\frac12$ initially, with $\frac26=\frac13$ after I have collected one, with $\frac16$ after I have collected two of the target numbers. Therefore the total expected waiting time is $2+3+6=11$.

share|improve this answer
    
But experimentally I get 9.97. –  user89867 Aug 11 '13 at 22:13

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.