Winning an unfair game

Question

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.

Answer 1

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.

Answer 2

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$

Answer 3

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.