So, I'm a programmer and yesterday I was at a job interview and I was asked the following question:
A six-sided die is rolled until the number 1 is thrown. What is the probability that the sum of all previous outcomes (including the last one) is odd?
I'm reasonably OK with probability, but this question had me stumped. How can I calculate this probability without knowing how many times the die was rolled? I would appreciate any ideas on the best way to approach this kind problem.
Thanks!
On
For those that are left wanting for details on how this could be done bottom up by answers like the above, here's a first principles way to do it.
The probability of rolling the first time $1$ on the $N$-th dice roll is of course given by
$$q(N):=P(X_N=1|X_1,..,X_{N-1}\neq 1)=\left(\frac{5}{6}\right)^{N-1}\frac{1}{6}$$
Now, given that we had to roll $N$ times, the probability that $m$ odd numbers appear in the sequence of rolls $1,2,..., N-1$ is
$$r(m|N):=P(|\{i|X_i=1\mod 2\}|=m)={N-1\choose m}(2/5)^m(3/5)^{N-1-m}$$
since the probability to roll an odd number from $\{2,3,4,5,6\}$ is $2/5$ and is the same for every roll. In order for the sum to be odd, we need an even number of odd numbers to appear in the sum. Thus to obtain the total probability we need to sum the probabilities coming from the even m's:
$$P(S_N=1\mod 2)=\sum_{m~~ \text{even}}r(m|N)=\frac{1+(1/5)^{N-1}}{2}$$
so for the total probability for the sum to be odd we get
$$P(S=1\mod2)=\sum_{N=1}^\infty P(S_N=1\mod 2)q(N)=\frac{3}{5}$$
Let $p$ be the answer. $1-p$ is then the probability that the sum is even.
Consider the first toss. With probability $\frac 16$ you get a $1$, and the sum is sure to be odd. With probability $\frac 26$ you get an odd number other than $1$ and now you need an even sum in order to win. With probability $\frac 36$ you get an even number, which restarts the game.
Thus $$p=\frac 16 \times 1 +\frac 26\times (1-p)+\frac 36\times p\implies p=\frac 35$$