Using your Head is Permitted

June 2017 solution

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-P_n, where

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 Δ₁,..., Δ_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 P_n.

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=2ⁱ. 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 Δ₁,..., Δ_n is valid, one can always remove from it Δ₁ and it will remain valid.

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

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

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:

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 Δ₃+Δ₅+Δ₆-Δ₂-Δ₉ 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:

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

Let Y₁,..., Y_n be a random signed permutation of {Δ_i}, and consider the distribution of the k for which the partial sum Y₁+...+Y_k is minimised. We claim that the probability that this occurs for a particular k is P_kP_n-k, since it means that all consecutive sums of the form Y_k+1+Y_k+2+...+Y_m must be positive for all m>k, while similarly all sums of the form Y_m+Y_m+1+...+Y_k must be negative for all m≤k.

Since generically the minimum is unique, we have

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)=P₀+P₁x+P₂x²+....

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

then

However, by the assumption of Equation (2) all Q_n 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 P_n to take negative values, which probabilities cannot.)

The value of each P_n 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