I encountered this question in an interview for graduate admission. I have shared the question below. I am not clear about how to model the dependency among the trials (i.e elimination constraints). And it would be of great use to me if someone could point me to good resources where I can learn and practice such problems.

3 persons A,B and C each have a biased coin whose probability of getting head is P. It is said that the event of flipping coins are independent. A,B and C decide to play a game where a person gets eliminated if he gets head on flipping his coin and the last person remaining is termed the winner. Having defined the rules for the game answer the following

1> What is the probability of A getting eliminated exactly on Nth round. 2> What is the probability of A getting eliminated before N rounds. 3> What is the probability of C winning on Nth round.

  • $\begingroup$ So they flip simultanuously, and may all be eliminated, if the current survivors all get head? $\endgroup$ – André Nicolas May 16 '14 at 22:35
  • $\begingroup$ Yes @AndréNicolas it includes that case too. $\endgroup$ – Priyesh Vijayan May 17 '14 at 5:41

We assume that in Round $1$, the three players flip their coins simultaneously. Then in the next round, the surviving players flip their coins simultaneously, and so on. Possibly after a certain number of rounds there are more than $1$ surviving players, and they all get eliminated in the next round. We also assume that if there are more than $1$ player participating in Round $n$, and exactly $1$ survives Round $n$, then the game is over.

$1.)$ Player A gets eliminated in the $N$-th round if she gets tails on the first $N-1$ rounds, head on the $N$-th, and at least one of the other players survives rounds $1$ to $N-1$. Now we can calculate. The probability A gets tails in the first $N-1$ rounds and head on the $N$-th is $(1-p)^{N-1}p$. The probability that B or C or both survive rounds $1$ to $N-1$ is $(1-p)^{N-1}+(1-p)^{N-1}-(1-p)^{2N-2}$. Thus the required probability is $$(1-p)^{N-1}p\left(2(1-p)^{N-1}-(1-p)^{2N-2} \right).$$ Some simplification can be made.

$2.)$ For $2.)$, we interpret "before $N$ rounds" as meaning she gets eliminated in rounds $1$ to $N-1$. In $1.)$ we have found an expression which with a letter change gives us the probability $a(k)$ that A is eliminated in Round $k$. One answer is for $2,)$ is then $a(1)+a(2)+\cdots +a(N-1)$. We can find a closed form for this by using a few times the formula for the sum of a finite geometric series. There is probably a faster way.

$3.)$. Player $C$ wins on the $N$-th round if she has an unblemished record of tails, and at least one of A or B survives into the $N$-th round, but is eliminated in that round.

The unblemished record part for C has probability $(1-p)^{N}$. The probability A survives until the $N$-th round but dies there is $(1-p)^{N-1}$. We have the same probability for B. The probability that at least one of A or B survives until the $N$-th round but dies there is therefore $2(1-p)^{N-1}p-(1-p)^{2N-2}p^2$. Thus our required probability is $$(1-p)^N \left(2(1-p)^{N-1}p-(1-p)^{2N-2}p^2 \right).$$


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.