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
Δ_{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
*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^{i}.
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 *P*_{n}=*P*_{n-1}*(2*n*-1)/(2*n*), 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.

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 Δ_{3}+Δ_{5}+Δ_{6}-Δ_{2}-Δ_{9} 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.

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

Let *Y*_{1},..., *Y*_{n}
be a random signed permutation of {Δ_{i}}, and consider the distribution of the *k* for which the partial sum
*Y*_{1}+...+*Y*_{k} is minimised.
We claim that the probability that this occurs for a particular *k* is
*P*_{k}*P*_{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*_{0}+*P*_{1}*x*+*P*_{2}*x*^{2}+....

The value of *C*^{2}(*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).