5

Here is problem 6 from chapter 2 of Introduction to Probability by Bertsekas and Tsitsiklis:

The Celtics and the Lakers are set to play a playoff series of $n$ basketball games, where $n$ is odd. The Celtics have a probability $p$ of winning any one game, independent of other games. For any positive integer $k$, find the values for $p$ for which $n = 2k + 1$ is better for the Celtics than $n = 2k-1$.

When I read this problem statement, I quickly felt certain based on intuition that a longer series is better when $p > 1/2$. Question: Is there a short proof that allows us to see this result at a glance?

Here is a solution to the problem which seems overly complicated, given how obvious the result is intuitively. The calculation below is surely not what my brain did in order to be certain that the answer must be $p > 1/2$.

Imagine that the two teams play $2k + 1$ games, and let the random variable $N$ be the number of games won by the Celtics during the first $2k -1$ games. The probability $p_{2k+1}$ of the Celtics winning the "best of $2k+1$" series (which requires winning at least $k + 1$ games in the series) is $$ \tag{1}p_{2k+1} = P(N \geq k+1) + P(N = k)(1 - (1-p)^2) + P(N = k-1)p^2. $$ On the other hand, the probability $p_{2k-1}$ of the Celtics winning a "best of $2k - 1$" series is $$ \tag{2} p_{2k-1} = P(N \geq k + 1) + P(N=k). $$ Notice that $P(N=k) = \binom{2k-1}{k}p^k(1-p)^{k-1}$ and $$ P(N = k-1) = \binom{2k-1}{k-1}p^{k-1}(1-p)^k = \binom{2k-1}{k}p^{k-1}(1-p)^k. $$ Comparing $(1)$ and $(2)$, we see that \begin{align} p_{2k+1} > p_{2k-1} &\iff P(N=k-1)p^2 > P(N=k)(1-p)^2 \\ &\iff p^{k+1}(1-p)^k > p^k(1-p)^{k+1} \\ &\iff p > \frac12. \end{align}

If there is no simpler proof, then why are we so certain at the outset of what the answer must be?

littleO
  • 51,938
  • 1
    The intuition (and mathematics) is the same as Condorcets jury theorem. Of course, the jury theorem requires proof, but it's a useful general result for justifying intuition. It's rather like the law of large numbers in that way. – Elle Najt May 20 '18 at 20:34
  • 3
    There's an intuitive argument here: https://en.m.wikipedia.org/wiki/Condorcet%27s_jury_theorem – Elle Najt May 20 '18 at 20:35
  • What AreaMan calls an intuitive argument is actually a fine proof. – Jalex Stark May 20 '18 at 21:24
  • 1
    I think the fact that games are i.i.d. is a key fact. Indeed if games are not i.i.d, we can have a longer series being BAD for the better team. Inspired by the OP, I have set up a new question requesting interesting examples of such: https://math.stackexchange.com/questions/2793166/when-is-a-longer-series-bad-for-the-better-team – antkam May 23 '18 at 16:10
  • Related: https://math.stackexchange.com/questions/2038603/find-probablity-of-winning – David K Mar 18 '19 at 12:28

1 Answers1

2

It's the "central limit theorem". If a single event has any probability distribution with finite mean, $\mu$, and finite standard distribution, $\sigma$, then the average, over n trials, has approximately a normal distribution with mean $\mu$ and standard distribution $\frac{\sigma}{\sqrt{n}}$. The larger n is, the smaller the standard distribution is. That means that the larger n is the less variation from the mean there is likely to be.

user247327
  • 18,710
  • Thanks. This was probably part of my intuition, but I also felt certain that the result was true for small values of $k$. And in any case, how do we convert the intuition into a simple but rigorous proof? – littleO May 20 '18 at 20:47
  • It works for small $k$ because $\mu > 1/2$ and $\sigma$ keeps shrinking, so the Prob of the worse team winning decreases with $k$. In other words, in this version of applying the CLT, not only does the distribution converge, it converges "monotonically" in some sense. Of course, this isnt a proof of the OP either, but rather, just a comment on why CLT (with monotonic convergence) may be applicable. – antkam May 23 '18 at 16:15