21
$\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 $p < \frac{1}{2}$, he with probability $1-p$. 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 $p$ 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$
  • $\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$ – DisgruntledGoat Jun 17 '14 at 21:48
12
$\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$
  • 1
    $\begingroup$ You have justified the conjecture. Thanks. $\endgroup$ – Ross Millikan May 28 '14 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$ – Ross Millikan Mar 9 '15 at 16:37
  • $\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 '16 at 12:26
7
$\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}$


$$\begin{array}{l|l|l} p\lt & n & P \;\; \text{(chances of winning the game)}\\ \hline \\ \tfrac{1}{3} & 2 & p^2 \\ \tfrac{2}{5} & 4 & p^4+4p^3(1-p) \\ \tfrac{3}{7} & 6 & p^6+6p^5(1-p)+15p^4(1-p)^2 \\ \tfrac{4}{9}? & 8 & p^8 + 8p^7(1-p) + 28p^6(1-p)^2 + 56p^5(1-p)^3 \\ \end{array}$$

$\endgroup$
  • $\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 '14 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
    $\begingroup$ You are correct for $p < \frac{1}{3}$, but interestingly things change after that. $\endgroup$ – arshajii May 24 '14 at 21:02

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.