0
$\begingroup$

Four people, each with a fair six-sided die, play a game. In each round, they simultaneously roll they dice once. If exactly one of the players gets 1, he is eliminated. Otherwise, everyone advances to the next round. The game ends when there is only one player left. Find the expected value of $N$, the numder of rounds in a completed game.

Attempt:

Assume that a completed game ends in $k$ rounds. This game corresponds to a sequence $(a_1=4,a_2,\dots,a_k=2,1)$ of length $k+1$ with alphabet from $\{2,3,4\}$ and $a_j\geq a_{j+1}$ for $1\leq j\leq k$. The sequence records the number of players left after each round of rolling. For $i=2,3,4$, let $m_i$ be the number of $i$'s in that sequence. Then we have that $$\mathbb{P}(N=k)=\sum_{m_4+m_3+m_2=k}(1-\alpha)^{m_4-1}\alpha(1-\beta)^{m_3-1}\beta(1-\gamma)^{m_2-1}\gamma$$ where $$\alpha=\binom{4}{1}\cdot\frac{1}{6}\cdot\left(\frac{5}{6}\right)^3$$ is the probability of exactly one of the four players gets 1; $$\beta=\binom{3}{1}\cdot\frac{1}{6}\cdot\left(\frac{5}{6}\right)^2$$ is the probability of exactly one of the three players who were not eliminated after the first elimination took place gets 1; $$\gamma=\binom{2}{1}\cdot\frac{1}{6}\cdot\frac{5}{6}$$ is the probability of exactly one of the two players who were not eliminated after the first two eliminations took place gets 1

How do I simplify the result and go on to compute the expected value $\mathbb{E}N$ from here? Am I on the right track? Thanks for any advice!

$\endgroup$
1
$\begingroup$

In a sequence of Bernoulli trials with probability of success $p,$ the expected number of trials until the first success is well-known to be ${1\over p}$ So once you have computed the probability with $4$ players you know the expected number of trials until the first player is eliminated. Repeat the process to find the expected number of trials until the second and third players and third players are eliminated. (I mean the expected numbers of trials in the three- and two-player games, of course.)

The sum of these is the number you seek, by linearity of expectation.

EDIT

Let $X_1$ be a random variable whose value is the number of rounds until the first player is eliminated. Let $X_2$ be a random variable whose value is the number of rounds after the first player is eliminated until the second player is eliminated, or what is the same thing, the number of rounds played by exactly three players. Let $X_3$ be random variable equal to the number of rounds played by exactly two players.

Let $X$ be the random variable whose value is the total number of rounds played. Clearly $X=X_1+X_2+X_3,$ so by linearity of expectation, $$E(X)=E(X_1)+E(X_2)+E(X_3),$$ and you need only find the expectation of those three geometric distributions.

$\endgroup$
  • $\begingroup$ Thanks! But I'm not sure if I fully understood the remark. So we have three geometric distributions. The expected value of trials to eliminate one player from four is $\alpha^{-1}$, where $\alpha$ is as above. And similarly, we get $\beta^{-1}$ and $\gamma^{-1}$. Why are we supposed to use linearity here (might be a dumb question)? Could you please elaborate on that part? Thanks a lot! $\endgroup$ – InTheSea Feb 25 at 22:02
  • $\begingroup$ @InTheSea Glad to. Give me a few minutes. $\endgroup$ – saulspatz Feb 25 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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