11
$\begingroup$

Here is the problem setup:

Two people play a game of throwing balls at a pin. Sally hits the pin 70% of the times she throws, and Bill hits the pin 40% of the times he throws. The game is won by the person who hits the target first. If Bill throws first each time, find the probability he will win.

With simulation, I get Bill's probability of winning to be around 0.52 (rounding to two decimal places). How to solve this problem analytically?

$\endgroup$
  • 2
    $\begingroup$ In general, memoryless games can be modeled with Markov chains. This particular game is the classic example of using a recurrence relation. $\endgroup$ – qwr Feb 16 at 7:23
  • $\begingroup$ The notation that makes this much clearer is to denote 's': 'Sally misses' (= 1 - 0.7), 'b': 'Bill misses' (= 1 - 0.4), 'S': 'Sally hits', 'B': 'Bill hits. Then you're talking about summing the sequence B, bsB, bsbsB, bsbsbsB... you can see that sum is an arithmetic series with ratio $bs = (0.3)(0.6) = 0.18$ and initial value $B$. Yes, Markov chains are the general theory. $\endgroup$ – smci Feb 16 at 21:05
14
$\begingroup$

I think you may have Bill and Sally backwards in your sim. I find that Bill's probability of winning is $\approx 0.488$.

Bill's probability of winning on his first throw, call it $p_1$ is $0.40$. Bill's probability of winning on his second throw requires him to miss, Sally to miss, then Bill to hit, or

$p_2=(1-0.4)(1-0.7)0.4 = (0.18)(0.4)$

Similarly,

$p_3=(1-0.4)(1-0.7)(1-0.4)(1-0.7)0.4 = (0.18)^{2}(0.4)$

Or generally,

$p_i=(0.18)^{i-1}(0.4)$

Bill's overall probability of winning is $\Sigma p_i$.

Since the ratio of sequential probabilities is constant, this is a geometric series. The sum of an infinite geometric series can be found with the formula

$\Sigma r^{i-1}p_1 = \frac{p_1}{1-r}=\frac{0.4}{1-0.18}=\frac{0.4}{0.82}\approx0.4878$

| cite | improve this answer | |
$\endgroup$
11
$\begingroup$

The symmetric situation of Sally and Bill suggests we solve the problem for arbitrary probabilities.

So, let $s$ be Sally's chance of hitting the target and $b$ be Bill's chance. When it's Sally's turn, let $p(s,b)$ represent her chance of eventually winning. We seek a formula for $p(s,b).$ Because Sally and Bill play identical roles in this game, merely differing in their skills, any formula for $p$ will tell us that $p(b,s)$ is Bill's chance of eventually winning when it's his turn. This is the first simplification afforded by the symmetry.

We also know the turns in the game alternate between the players. Thus, when it's a player's turn, their chance of eventually winning equals their chance of hitting the target plus the chance that their opponent (who gets the next turn) eventually loses. That, of course, is given by subtracting the opponent's chance of winning from $1.$

This gives two symmetrical equations, one for each player:

$$\left\{\eqalign{p(s,b) = s + (1-s)(1-p(b,s))\; \\ p(b,s) = b + (1-b)(1-p(s,b)).}\right.$$

That's the second simplification due to symmetry--and it's enough to go directly to the answer, because plugging the second equation into the first (to eliminate $p(b,s)$) gives an equation relating $p(s,b)$ to $s$ and $b.$ Use algebra to solve it:

$$p(s,b) = \frac{s}{1 - (1-s)(1-b)}.$$

With $s=7/10$ and $b=4/10,$ this gives

$$p(7/10, 4/10) = \frac{7/10}{1 - (3/10)(6/10)} = \frac{70}{82}\approx 85.37\%$$

for Sally to win if it's her turn and

$$p(4/10, 7/10) = \frac{4/10}{1 - (3/10)(6/10)} = \frac{40}{82} \approx 48.78\%$$

for Bill to win if it's his turn.


Another solution method notes this is a Markov chain on the four states "Sally's turn," "Bill's turn," "Sally wins," and "Bill wins." You can set up the $4\times 4$ transition matrix

$$\mathbb{P} = \pmatrix{0 & 3/10 & 7/10 & 0 \\ 6/10 & 0 & 0 & 4/10 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1}$$

and turn the Markov chain theory crank. Because the largest size of the non-unit eigenvalues of $\mathbb{P}$ is $\sqrt{(1-s)(1-b)},$ or approximately $0.4242641,$ whose common logarithm is $-0.37,$ and double-precision arithmetic doesn't quite achieve $16$ decimal places, taking a power of $\mathbb P$ greater than about $16 / 0.37 = 43$ will reveal the answers (in its $(1,3)$ and $(2,4)$ entries). That is,

$$p(s,b) = \lim_{n\to \infty} (\mathbb{P}^n)_{\text{Sally's turn},\text{Sally wins}}= \lim_{n\to \infty} (\mathbb{P}^n)_{1,3}$$

and

$$p(b,s) = \lim_{n\to \infty} (\mathbb{P}^n)_{\text{Bill's turn},\text{Bill wins}}= \lim_{n\to \infty} (\mathbb{P}^n)_{2,4}$$

both converge exponentially rapidly.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ One could also argue more directly that $$p (s,b) = s + (1-s)(1-p) p(s,b) $$ The 'probability to win if it is your turn' equals the 'probability to win directly in one turn' plus the 'probability to win if it is your turn' times the 'probability to get two turns further'. $\endgroup$ – Sextus Empiricus Feb 14 at 17:30
  • $\begingroup$ Or another. In a particular turn (of two steps) either the first person wins with probability $s$, the second person wins with probability $(1-s)b $ or nobody wins with probability $(1-s)(1-b) $. The probability that the first person wins *conditional* on the game ending in the particular turn (of two steps) is $$\frac {s}{s + (1-s)b} $$ and since this is independent from whatever turn the game ends it equals the probability to win the game in any turn. $\endgroup$ – Sextus Empiricus Feb 14 at 17:44
  • $\begingroup$ @Sextus Thank you for sharing those thoughts. I agree that these approaches will work here and may be the shortest, most elegant route to solving the present problem. For generalizations to games with more than two states, though, such as Penney's game (and other Markov chains), the straightforward method of considering each state is what generalizes. $\endgroup$ – whuber Feb 14 at 17:45
  • $\begingroup$ I get that the Markov chain approach is more general. But the symmetry approach with the elimination seemed a bit counterintuitive (cumbersome) to me. I did find it a fun approach however. Would there be problems when that works better? $\endgroup$ – Sextus Empiricus Feb 14 at 18:27
  • $\begingroup$ @Sextus It's a natural way to solve the problem after you have drawn a graph of the states and the transitions. I sketched this approach at stats.stackexchange.com/a/12196/919. One finds the numbers on the nodes (the expected times to reach a terminal node) by solving a comparable set of simultaneous equations, with one variable per node. $\endgroup$ – whuber Feb 14 at 22:57
7
$\begingroup$

For the first round, Bill wins with probability 0.6. For he to win on the second round, Sally needs to lose. Let $B_i$ be the event that Bill wins at $i$-th trial; same for Sally (i.e. $S_i$). So, for the second trial, we can write: $$P(B_2)=P(B_1')P(S_1'|B_1')P(B_2|B_1',S_1')=0.6\times0.3\times0.4$$

This goes on similarly for each $i$, ending up with: $$P(\text{Bill wins})=0.4(1+0.18+0.18^2+\dots)=\frac{0.4}{1-0.18}$$

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

It seems easiest to do it as a recurrence relation.

Bill and Sally are going to alternate throwing. When Bill goes first, he will win immediately 40% of the time. The other 60% is like saying Sally goes first. In that case, Sally will win 70% of the time and the other 30% (of the 60%), we're back to the probability of Bill winning if he goes first.

p = 0.4 + 0.6 ( 0.3 * p)

Solve for p, get p = 0.4 / 0.82 = 48.8%

Something's up with your simulation, or @CFD and I don't understand your problem statement.

| cite | improve this answer | |
$\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.