2
$\begingroup$

I was asked this question at an interview and was stumped by it. The problem is as follows:

Alice is playing an online game. She wins the first round and loses the second. The probability she then wins subsequent rounds is proportional to the number of wins. Calculate the probability that after 100 games, the number of wins and losses are equal.

I am unsure of how to proceed. At the interview, I was originally thinking of using a simple sum of

$$\sum_i \alpha w_i \delta_i,$$

where $\alpha$ is normalisation constant, $w_i$ is the number of wins at the $i$th game and $\delta_i$ is either 0 or 1. However, I doubt this is a correct approach, and $w_i$ is dependent on the $\delta$’s for $j<i$.

I was discussing with a mathematician friend who said that this is a possible variation of Polya’s urn, but I can’t see the connection. Could anyone help me with this visualisation and provide hints on how to move forward? Thank you!

$\endgroup$
  • 1
    $\begingroup$ Saying the probability in subsequent rounds is proportional to the number of wins is not sufficient. It might be fixed at $0$. I think this is usually asked with the probability in each round being the fraction of wins up to that point, so for round $3$ she has $\frac 12$ chance to win and if she wins in round $3$ she has $\frac 23$ chance to win round $4$. $\endgroup$ – Ross Millikan Nov 18 '18 at 19:55
  • $\begingroup$ @RossMillikan I see – could you talk a bit more about that? I’m curious! $\endgroup$ – user107224 Nov 18 '18 at 19:57
  • $\begingroup$ This is exactly the Polya urn model. en.wikipedia.org/wiki/P%C3%B3lya_urn_model See the 2nd paragraph. Then interpret a black ball as WIN and a white ball as LOSE. $Prob(WIN) = $ exactly the fraction of black balls = fraction of previous wins. Having said this, I don't know how to solve this model but I suspect some googling would reveal quite a lot of resources. $\endgroup$ – antkam Nov 18 '18 at 20:14
5
$\begingroup$

Let $W_i$ and $L_i$ denote the number of wins and losses after the $i$-th rounds. Then, assuming that the probability of winning the $(i+1)$-th round is $W_i/(W_i+L_i)$, \begin{align} &\mathsf{P}(W_{100}=L_{100}\mid W_2=L_2) \\ &\qquad=\binom{98}{49}\frac{W_2(W_2+1)\cdots (W_2+48)\times L_2(L_2+1)\cdots (L_2+48)}{(W_2+L_2)(W_2+L_2+1)\cdots(W_2+L_2+97)} \\ &\qquad=\binom{98}{49}\frac{(1\cdot 2\cdots 48\cdot 49)^2}{2\cdot 3\cdots 98\cdot 99}=\frac{1}{99}. \end{align}

$\endgroup$

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.