Using your Head is Permitted

June 2017 solution

This is a question first posted by Lian Wang on Math Overflow.

The solution below is essentially a direct copy of the solution given on the same URL, originally posted by Johan Wästlund.

My many thanks to both Lian and Johan.

The answer is 1-Pn, where

Pn=(2n)!/(4n (n!)2).    (1)

We will show the following more general claim, equivalent, essentially, to our original claim being true not only for Δ values picked from a uniform distribution over [-1,1] but also for ones picked from any other distribution defineable by a symmetric probability density function, constant over all random walk steps, that has a continuous cumulative density function.

Let Δ1,..., Δn be any "generic" sequence of positive real numbers (in the sense that no non-empty subset of them sums to zero. This is something that in our problem statement will happen only with probability zero, so can be ignored in probability calculations.)

Consider the partial sums created by permuting the terms randomly and putting random signs on each term (with a uniform distribution over all possibilities).

We claim that the probability that all partial sums are positive is given by Pn.

The proof is divided into two parts. First, we show for a special case of a {Δi} sequence that it holds this property. Then we will show that the probability is independent of the choice of sequence.

Regarding the first part, consider the special case where Δi=2i. This sequence was chosen so that each element is larger than the sum of all elements preceding it, so the sign of any partial sum depends only on the sign of the dominating term.

Let a valid signed permutation be one where all partial sums are positive.

If a particular signed permutation of Δ1,..., Δn is valid, one can always remove from it Δ1 and it will remain valid.

Conversely, if the sequence is invalid, removing Δ1 will only result in a valid sequence if Δ1 was chosen to be first in the permutation and assigned a negative sign.

We conclude that Pn=Pn-1*(2n-1)/(2n), proving the general equation given for Pn.

Next, we want to show that this result is independent of our choice of a {Δi} sequence. Johan Wästlund presented two separate ways to prove this.

Method 1:

Let us move the point (Δ1,..., Δn) in ℝn and consider how the probability of a valid signed permutation might change.

We need only consider what happens when we pass through a hyperplane given by a signed subsequence being equal to zero. Instead of introducing double indices let us take a generic example:

Suppose we pass through the hyperplane where the sum Δ35629 changes sign. At the moment where the sign change occurs, the only signed permutations that go from valid to invalid or the other way are those where this particular sum occurs as the five first terms (in some order). Now for every signed permutation that goes from valid to invalid, there will be a corresponding one that goes from invalid to valid, by reversing those five first terms and changing their signs. For instance, if


goes from valid to invalid, then


will go from invalid to valid.

The conclusion is that the probability of a signed permutation being valid (having all partial sums positive) can never change.

Method 2:

We will prove that for any n,


Because this equation allows Pn to be computed by means of a recursive formula (with known starting point P0=1), it cannot depend on {Δi}.

Let Y1,..., Yn be a random signed permutation of {Δi}, and consider the distribution of the k for which the partial sum Y1+...+Yk is minimised. We claim that the probability that this occurs for a particular k is PkPn-k, since it means that all consecutive sums of the form Yk+1+Yk+2+...+Ym must be positive for all m>k, while similarly all sums of the form Ym+Ym+1+...+Yk must be negative for all mk.

Since generically the minimum is unique, we have

P0Pn+P1Pn-1+...+PnP0=1,    (2)

as desired.

Though there are many ways to prove that Equation (2) leads to Equation (1), Lin Jin sent a particularly elegant proof, based on generating functions. Here is its essence (with a big "thank you" to Lin):

Let C(x)=P0+P1x+P2x2+....

The value of C2(x), i.e. the value of C(x) squared, can be calculated based on polynomial multiplication equations. If




However, by the assumption of Equation (2) all Qn equal 1, so


where the final equality is valid in (-1,1), so in an open segment that includes zero. It follow then that


(It cannot be its negative, as this would cause Pn to take negative values, which probabilities cannot.)

The value of each Pn can now be determined by calculating the n'th derivative of C(x) at x=0, leading immediately to Equation (1).

Back to riddle

Back to main page