I'm trying to formally write out the problem: Light bulb color problem when I come up with the following equation


where it is supposed to hold for all $k\geq1$. Let's forget the original light bulb problem for a while. If we just want to prove the above equation, how shall we do it? I tried induction and it seemed difficult and baffling... Is there any idea or perhaps tricks one can use to establish it? What is the general approach for establishing these kind of complex combinatorial equations? (By the way, I know from the light bulb problem that it must be true for $0\leq p\leq1$, but does it also hold for any $p$ beyond that domain?)

Edit: I vaguely remember there's a theorem or something that says if the above equation holds for any $0\leq p\leq1$ then it must hold for any $p\in\mathbb{R}$. Does any one know what that theorem is?

  • $\begingroup$ How would you interpret $C_{2k}^k$? What would selecting $2k$ items from $k$ items mean? Should this term not be $0$? $\endgroup$ – varty Nov 26 '11 at 5:06
  • $\begingroup$ @varty:$C_{2k}^k$ is the situation when there're equal numbers of flashes of red and blue (where each color has k flashes). Left hand side is the probability you guess correctly under best strategy when you decide to observe $2k-1$ times; RHS is the probability you when you decide to observe $2k$ times. $\endgroup$ – Eric Nov 26 '11 at 5:49
  • $\begingroup$ Are you using $C_{2k}^k$ to mean the number of ways we select $k$ items from $2k$ items? $\endgroup$ – varty Nov 26 '11 at 5:53
  • 1
    $\begingroup$ @varty: This is the alternative notation to ${2k \choose k}$, used for instance in French textbooks. $\endgroup$ – Xi'an Nov 26 '11 at 7:41

About the combinatorial question: the proof follows from the identity $$ {2k-1 \choose i-1} + {2k-1 \choose i} = {2k \choose i} $$ Thus $$ \sum_{i=0}^{k-1} {2k\choose i} p^{2k-i} (1-p)^i = \sum_{i=0}^{k-1} {2k-1 \choose i} p^{2k-i} (1-p)^i + \sum_{i=0}^{k-1} {2k-1 \choose i-1} p^{2k-i} (1-p)^i $$ which implies $$ \sum_{i=0}^{k-1} {2k\choose i} p^{2k-i} (1-p)^i = \sum_{i=0}^{k-2} {2k-1 \choose i} p^{2k-1-i} (1-p)^i + {2k-1 \choose k-1} p^{k+1} (1-p)^{k-1} $$ and $$ \frac{1}{2}{2k\choose k} = {2k-1\choose k-1} $$ implying that $$ {2k-1 \choose k-1} p^{k+1} (1-p)^{k-1} + \frac{1}{2}{2k\choose k} p^{k} (1-p)^{k} = {2k-1\choose k-1 } p^{k} (1-p)^{k-1} $$ which establishes your identity.

About your "Edit" question, I think you mean the theorem in complex calculus that states that, if an analytic function is constant over an interval, it is constant everywhere.

  • 2
    $\begingroup$ Even better, for any fixed $k$ it's a univariate polynomial (in $p$) which has infinitely many zeroes, and thus is zero. No complex calculus necessary! $\endgroup$ – Erik P. Dec 1 '11 at 5:07

A coin has a chance $p$ of landing heads. Among an odd number ($2k-1$) of tosses, what are the chances there are more heads than tails?

Let's look at two solutions.

  1. The number of heads is $k$, $k+1$, $k+2$, $...$, or $2k-1$. Sum the chances of each of these events.

  2. Toss the coin one more time!

    If the number of heads is now $k+1$, $k+2$, $...$, or $2k$, then originally there were at least $k$ heads. Sum these chances.

    If the number of heads is now exactly $k$, it's uncertain whether there were $k-1$ or $k$ heads among the original $2k-1$ tosses. It all depends on whether the last toss was a head: there were $k$ heads originally if and only if the last toss was a tail. Do the following: randomly write down all $2k$ results--of which $k$ are heads and $k$ are tails, by assumption. One of them represents the last toss, but which? We don't know, but we do know it has equal chances of being in any of the $2k$ positions. Since $k$ of those are tails, there is a $k/(2k)=1/2$ chance the last toss was a tail.

In solution (1), the chance of exactly $i$ tails, equivalent to $2k-1-i$ heads, is given by the Binomial Distribution for $2k-1$ tosses,

$${\Pr}_{2k-1}(2k-1-i) = \binom{2k-1}{i}p^{2k-1-i}(1-p)^i = C_{2k-1}^{2k-1-i}p^{2k-1-i}(1-p)^i.$$

The sum goes from $i=0$ to $i=k-1$. That's the left hand side of the equation in the question.

In solution (2), the chance of exactly $i$ tails is equivalent to $2k-i$ heads, given by

$${\Pr}_{2k}(2k-i) = \binom{2k}{i}p^{2k-i}(1-p)^i = C_{2k}^{2k-i}p^{2k-i}(1-p)^i.$$

Totaling these for $i=0, 1, \ldots, k-1$ gives the summation to the right of the equation in the question. The chance that the last toss is a tail and all $2k$ tosses are heads is the product

$${\Pr}_{2k}\left(\text{last toss is tail}\,|\,k\text{ heads}\right){\Pr}_{2k}\left(k\text{ heads}\right) = \frac{1}{2}\binom{2k}{k}p^{2k-k}(1-p)^k = \frac{1}{2}C_{2k}^kp^k(1-p)^k.$$

This is the extra term at the right of the equation. Solution (2) therefore produces the formula on the right hand side.

Thus, the equation holds for all $k$ because it gives two ways of expressing the chance of observing a majority of heads in any odd number of tosses.

The general approach exemplified here is to count the same thing in two different ways. It's a powerful method, advocated particularly by combinatorialists (people who specialize in counting things). Many complicated formulas turn out to have simple, illuminating proofs of this nature. For details, see Richard Stanley's Enumerative Combinatorics. (Volume 1 is available on the Web--Google it.)

Let's address the last part of the question. Both sides of the equation are obviously polynomials in $p$. Their difference is a polynomial of degree at most $2k$. It is zero for all valid probabilities $p$. There are more than $2k+1$ probabilities (there are infinitely many of them in the interval from $0$ to $1$). Since a polynomial of degree $n$ is completely determined by its values at any $n+1$ numbers, the difference is the zero function--and in particular equals zero for any number $p$.


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.