7
$\begingroup$

(Disclaimer: This is not a homework question). I am trying to teach my self some elementary probability, and I thought of this following example: Imagine you are playing a game involving two coins. In order to win the game you must flip heads before your opponent. That is, if they flip heads first they win and you lose. Let's also assume the game is played in a turn based fashion and you are flipping the coin first. Also, the coins are 'unfair' with $P(X=heads)|_{coin 1}=p_1$ and $P(X=heads)|_{coin 2} = p_2$.

I am unsure how to compute on average how many turns it will take to win the game.

So far, I believe we can model this game with the following function $P(X=k) = p_1(1-p_1)^{k-1}(1-p_2)^{k-1}$ (which appears very similiar to a geometric distribution), because in order to win the game (assuming you flipped tails first) the opponent must flip tails with probability $(1-p_2)$ or you lose. This pattern repeats for each round of the game.

I believe the probability of winning is equal to $\sum_{k=1}^{\inf}p_1(1-p_1)^{k-1}(1-p_2)^{k-1}$ and the expected number of turns to win is given by $\sum_{k=1}^{\inf}p_1(1-p_1)^{k-1}(1-p_2)^{k-1} k$.

I wrote a Monte Carlo simulation to compute these values with the assumption of values for $p_1$ and $p_2$, but that is not satisfactory for me. I would like to know how to solve this problem mathematically as opposed to programmatically.

Two questions: 1) Am I on the right track with the probability of winning and the expected number of turns to win? 2) If so, can you assist me in solving these infinite series. Admittedly, I am not great with solving series.

Edit: The question has been answered, but I wanted to post my code in case anyone is interested. (I was originally thinking about this problem in terms of a naval battle, so that's why the comments and variable names are named that way).

from pylab import *
nSim = 100000
p_h1 = 0.5
p_h2 = 0.5
number_won = 0
total_shots = []
for i in range(nSim):
    won = False
    shots_fired = 0
    while not won:
        shots_fired += 1
        # simulate shot
        shot = rand(1)
        # if it hits, the game is over
        if shot <= p_h1:
            won = True
            number_won += 1
        # else, other player shoots
        else:
            shot = rand(1)
            if shot <= p_h2:
                won = True 
        total_shots.append(shots_fired)

print 'from monte carlo simulation:'
print 'P(win): ', float(number_won) / float(nSim)
print 'expected # of shots: ', np.array(total_shots).mean()

# testing
print 'from theory:'
denom = (1-p_h1)*(1-p_h2)
print 'P(win): ', p_h1 / (1 - denom)
pstar = (1 - (1-p_h1)*(1-p_h2))
print 'expected # of shots: ', 1. / pstar

and the output:

from monte carlo simulation:
P(win):  0.66706
expected # of shots:  1.33967131236
from theory:
P(win):  0.666666666667
expected # of shots:  1.33333333333
$\endgroup$
4
  • $\begingroup$ By "how many turns it will take to win" are you assuming that you win? Is this a conditional probability? $\endgroup$
    – Glen_b
    Jan 31, 2016 at 0:49
  • $\begingroup$ I am assuming the player flipping coin1 wins. The only condition seems to be that player2 must always flip tails in order for player1 to win. $\endgroup$
    – wsavran
    Jan 31, 2016 at 18:03
  • $\begingroup$ Terminology note: we don't 'solve' series. "Solving" is something we do with equations. We can calculate the sum of the terms (evaluate the series, sum the sequence of terms). Often people say "sum the series" (perhaps loosely since a series is formally a sum of terms -- but not ambiguously). $\endgroup$
    – Glen_b
    Jan 31, 2016 at 23:12
  • $\begingroup$ Thanks @Glen_b, that's a good point about "solving" series. It doesn't make much sense to say that. $\endgroup$
    – wsavran
    Feb 1, 2016 at 0:17

2 Answers 2

6
$\begingroup$

[I've put some material on how to sum geometric progressions and expectation of geometric random variables at the end; this answer relies on such results but they're fairly well known so I figured I wouldn't start with them. If any readers are not, then skip to the end to see one way to get them out. It's worth doing some of those yourself (without peeking) so you fix the idea in your mind.]

If you assume player 1 must win then you need to work out conditional probabilities. When you condition on player 1 winning your calculations are incorrect.

$P(A|B) = \frac{P(AB)}{P(B)}$

$P(\text{at toss }k\text{ player 1 wins}|\text{player 1 wins})= \frac{P(\text{player 1 wins on toss }k)}{P(\text{player 1 wins})}$

$=\frac{p_1(1-p_1)^{k-1}(1-p_2)^{k-1}}{\sum_{j=1}^\infty p_1(1-p_1)^{j-1}(1-p_2)^{j-1}}$

Now let's save ourselves some effort: Let $1-p^*=(1-p_1)(1-p_2)$

$=\frac{p_1(1-p^*)^{k-1}}{p_1\sum_{j=1}^\infty (1-p^*)^{j-1}}$

$=\frac{p^*(1-p^*)^{k-1}}{p^*\sum_{j=1}^\infty (1-p^*)^{j-1}}$

Now the numerator is the pmf of a geometric random variable and the denominator is the sum of that geometric pmf (which sums to 1):

$={p^*(1-p^*)^{k-1}}$

(with some thought you can arrive at the same answer directly, without any algebraic manipulation)

Now the conditional expectation comes out immediately to be

$E(\text{number of tosses until player 1 wins}|\text{player 1 wins}))=\frac{1}{p^*}$


Summing a geometric series:

$\qquad\qquad\quad\: S_0\:=\:p+p(1-p)+p(1-p)^2+p(1-p)^3+...$

$\qquad\:(1-p)S_0\:=\:\:\:\quad p(1-p)+p(1-p)^2+p(1-p)^3+...$

$(1-(1-p)) S_0=\:p+\quad\, 0\quad\:\: +\quad\: 0\qquad +\quad\: 0\qquad +...$

So $pS_0=p$, or $S_0=1$.

If you need to see how to get the expectation of a geometric($p$) random variable, we can use the same trick as above - write out the terms in $S_1=\sum_{k=1}^\infty kp(1-p)^{k-1}$ one by one, and then under it write out the terms in $(1-p)S_1$, but shifted so that the second set of terms are all moved one to the right.

Then take differences term by term and this time you're left with a geometric series (rather than a single value and totally cancelled terms), but we already know how to sum geometric series, we did it with $S_0$ above.

$\endgroup$
3
  • $\begingroup$ Thanks for such an informative answer. The theory checks out with the Monte Carlo simulation. I'm going to post my code in the question in case anyone is interested. $\endgroup$
    – wsavran
    Feb 1, 2016 at 1:16
  • $\begingroup$ Im kind of late reviewing this, but I am working through the algebra and shouldn't the sum go to infinity in Eq.2 and Eq.3? I only get the correct answer when I have the sum go to all possible rounds. $\endgroup$
    – wsavran
    Feb 5, 2016 at 1:27
  • $\begingroup$ Yes, the upper limits on the sums should definitely be $\infty$ everywhere. Sorry, that was a typo that then got copied down. $\endgroup$
    – Glen_b
    Feb 5, 2016 at 1:43
2
$\begingroup$

Let us define a round of tosses as two tosses; the first toss by A who tosses a coin with $P(\text{Heads}) = p_1$ and the second toss by B who tosses a coin with $P(\text{Heads}) = p_2$.

The outcomes of a round and the corresponding probabilities are $$\begin{matrix} HH & &p_1p_2\\ HT & &p_1(1-p_2)\\ TH & &(1-p_1)p_2\\ TT & &(1-p_1)(1-p_2) \end{matrix}$$ where, if either of the first two outcomes occurs, A wins (with probability $p_1$); in fact, it does not matter in the least whether B tosses a coin at all once A has tossed a Head. Call this event $\mathcal A$ If the third outcome $TH$ occurs, B wins (with probability $(1-p_1)p_2 = p_2 - p_1p_2$; we call this $\mathcal B$. If the fourth outcome $TT$ occurs, nobody wins, and a new round is initiated. This is event $\mathcal C$. Thus, one of the three (disjoint) events $\mathcal{A, B, C}$ can occur on a round. The game ends on a round with probability $p^* = p_1 + p_2 - p_1p_2$ and continues for the next round with probability $1-p^*$.

A wins the game if the outcomes of the rounds are any of the following disjoint sequences of events: \begin{align} &\mathcal{A}\\&\mathcal{CA}\\&\mathcal{CCA}\\&\mathcal{CCCA}\\ &\quad\vdots\\&\mathcal{C}^{k-1}\mathcal{A}\\&\quad\vdots \end{align} Thus, $$P(\mathcal A) = p_1 + (1-p^*)p_1 + (1-p^*)^2p_1 + \cdots = \frac{p_1}{p^*}$$ and similarly, \begin{align}P(\mathcal B) &= (1-p_1)p_2 + (1-p^*)(1-p_1)p_2 + (1-p^*)^2(1-p_1)p_2 + \cdots \\ &= \frac{(1-p_1)p_2}{p^*} \\ &= \frac{p^*-p_1}{p^*}\\ &= 1-P(\mathcal A).\end{align}

Note that conditioned on the event that the game ended on the round under consideration, the probabilities of the players winning are $$P(\text{A wins}) = \frac{p_1}{p_1 + p_2 - p_1p_2} = \frac{p_1}{p^*}, \quad P(\text{B wins}) = \frac{p_2 - p_1p_2}{p_1 + p_2 - p_1p_2} = \frac{p^*-p_1}{p^*}.$$ These are the same as the unconditional probabilities of $\mathcal A$ and $\mathcal B$

Let $X$ denote the number of rounds till the game ends. $X$ also denotes the number of times that the winner of the game tosses the coin. Then, $X$ is a geometric random variable with parameter $p^* = p_1 + p_2 - p_1p_2$. But, the previous paragraph shows that conditioned on the occurrence of the event $\{X = k\}$, the conditional probability of $\mathcal A$ is the same as the unconditional probability, that is, _for each $k, k =1,2,3,\ldots$, the event $\{X = k\}$ and the event $\mathcal A$ are mutually independent events. Indeed, the random variable $X$ is independent of the event $\mathcal A$. Now, the expected value of $X$ is \begin{align} E[X] &= 1\cdot p^* + 2\cdot (1-p^*)p^* + 3\cdot (1-p^*)^2p^* + \cdots\\ &= p^*\left[1 + 2\cdot (1-p^*) + 3\cdot (1-p^*)^2 + \cdots \right]\\ &= p^* \cdot \frac{1}{(1-(1-p^*))^2}\\ &= p^* \cdot \frac{1}{(p^*)^2}\\ &= \frac{1}{p^*} = \frac{1}{p_1 + p_2 - p_1p_2} \end{align} and this expected value is supremely indifferent to the occurrence or the non-occurrence of $\mathcal A$. In short, the expected number of tosses when A wins the game is $\frac{1}{p^*}$ which is the same as the expected number of tosses when B wins the game.

$\endgroup$
1
  • $\begingroup$ Thanks for positing the alternate approach to the problem. $\endgroup$
    – wsavran
    Feb 1, 2016 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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