Combining Binomial Random Variables

Question

(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

Answer 1

[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.

Answer 2

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.