24
$\begingroup$

I came across the following interesting problem today:

A game consists of a sequence of plays; on each play either you or your opponent scores a point, you with probability 𝑝 < 1/2, he with probability (1 - 𝑝). The number of plays is to be even (2, 4, 6, ...). To win the game, you must score more than half the points. You are allowed in advance to choose the number of plays. How many plays should you choose in terms of 𝑝 to optimize your chances of winning?

The problem is much less trivial than I thought at first glance. I know the answer, but will refrain from posting it unless the problem goes unsolved for an extended time.

$\endgroup$
2
  • $\begingroup$ To be clear, when you say p<1/2, do you mean a fixed probability or is it a random probability on each play? $\endgroup$ Jun 17, 2014 at 21:48
  • $\begingroup$ Problem was from "50 Challenging Problems in Probability", by Mosteller. $\endgroup$ Nov 5, 2020 at 22:23

3 Answers 3

13
$\begingroup$

This is really a comment on Ross Millikan's answer, but too cumbersome to enter that way. I have verified the $ p= \frac{n-1}{2n-1}$ threshold, although it really should be called $\frac{n/2}{n+1}$ (there is some confusion between $n$ and $2n$ in Ross's answer). The derivation is roughly as follows. For even $n$, let $P_n =$ the probability of winning a match when the probability of winning a game is $p$.

$ P_n = {n \choose 0} p^n (1-p)^{0} + {n \choose 1}p^{n-1}(1-p)^{1}+ \cdots + {n \choose m}p^{n-m}(1-p)^m$

where $m=n/2-1$.

This is just a restatement of Ross's table in general form. If you want to solve for $P_8 >P_6$, say, where $0<p<1$, then we need to find the roots of $P_8-P_6$. In general,

$P_{2k+2}-P_{2k} = (-1)^k C_k \,p^{k+1} (1-p)^{k}(p-\frac{k}{2k+1})$

which has multiple roots at $0$ and $1$ and one root at $p=\frac{k}{2k+1}$ ($=\frac{n/2}{n+1}$ if we call $n=2k$).

$C_k$ is the $k$th Catalan number.

$\endgroup$
3
  • 1
    $\begingroup$ You have justified the conjecture. Thanks. $\endgroup$ May 28, 2014 at 15:43
  • $\begingroup$ I think I have the $n$'s right. Taking $n=2$ I say you should play $4$ games instead of $2$ when $p \gt \frac {2-1}{2\cdot 2 -1}=\frac 13$ $\endgroup$ Mar 9, 2015 at 16:37
  • 1
    $\begingroup$ I agree that Ross's answer appears to use n consistently to mean the number of pairs of games rather than the number of games. I don't see the confusion IJK complains of. $\endgroup$
    – Gareth McCaughan
    Apr 12, 2016 at 12:26
10
$\begingroup$

If you play two games, your chance is $ p^2$. If you play four, your chance is $p^4+4p^3(1-p)$, which becomes greater when $p\gt \frac 13 $. If you play six games, your chance is $p^6+6p^5(1-p)+15p^4(1-p)^2$, which is better than four games when $p \gt \frac 25$ It is tempting to conjecture that you should play $2n$ games (instead of $2n-2$) when $p \gt \frac {n-1}{2n-1}$


p < n P (chances of winning the game)
$\frac{1}{3}$ 2 $p^2$
$\frac{2}{5}$ 4 $p^4+4p^3(1-p)$
$\frac{3}{7}$ 6 $p^6+6p^5(1-p)+15p^4(1-p)^2$
$\frac{4}{9}?$ 8 $p^8 + 8p^7(1-p) + 28p^6(1-p)^2 + 56p^5(1-p)^3$
$\endgroup$
1
  • $\begingroup$ I checked the next one up with Wolfram Alpha: $p^8 + 8p^7(1-p) + 28p^6(1-p)^2 + 56p^5(1-p)^3 > p^6 + 6p^5(1-p) + 15p^4(1-p)^2$ if $p>\tfrac{3}{7}$. $\endgroup$
    – SQB
    May 26, 2014 at 11:14
0
$\begingroup$

Let's look at the number of plays vs the number of games he has to win:

2: 2/2 + 1 = 2
4: 4/2 + 1 = 3
6: 6/2 + 1 = 4
n: n/2 + 1

Or in relative terms: 1, 3/4, 2/3, 1/2 + 1/n. So the more they would play, the easier it would be for the first player to get more than half wins. This does not take into account the handicap though. For that, one would need to maximise the combined probability, but I'm not skilled enough to write that here or be certain of its correctness (binomial distribution of n over k for values of k from n/2 + 1 to n?).

So I'll just cheat through induction. For p=1/4, there's a ~6% chance of winning 2/2 games, ~5% of winning 3 or more of 4, ~4% for 4-6/6 ... So it seems the extra combinations do not offset the exponents and the best choice is the unintuitive 2 games.

$\endgroup$
1
  • 2
    $\begingroup$ You are correct for $p < \frac{1}{3}$, but interestingly things change after that. $\endgroup$
    – arshajii
    May 24, 2014 at 21:02

Your Answer

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

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