# A random walk with uniformly distributed steps

The following problem has bothered me for a long time.

Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the following way. For every step of the "walk", it will choose a real number $\Delta x$ uniformly from the interval $[-1,1]$, turn right, and move $\Delta x$ unit. Once it reaches the left side of the point $O$, it will "die" immediately.

Our task is find out the probability of the point is alive after $n$ steps of "walk" $P_n$. I guess that $P_n=\frac{(2n)!}{4^n (n!)^2}$, but I can't prove this or explain why it is true.

-
Why is this your guess? –  Steven Landsburg Apr 16 '12 at 16:36
Because I did some numeral calculation when n is small with Mathematica. Then the result I got seems to follow this formula. –  Lwins.Gafield Apr 16 '12 at 16:49
I hope it's ok, I've edited the question a bit and put a more descriptive title. –  Gjergji Zaimi Apr 17 '12 at 12:28
Thanks for your edit. –  Lwins.Gafield Apr 17 '12 at 13:54

Here is an argument that proves the conjecture. More generally, it shows that if $X_1,\dots,X_n$ is a "generic" sequence of positive real numbers, and we form a sum by permuting the terms randomly and putting random signs on the terms (uniform distribution over all possibilities), then the probability that all partial sums are positive is given by $P_n$ as expressed in the OP. By "generic" I mean that no nonempty signed subsequence sums to zero.

First consider a special case where the statement clearly holds: Assume that $X_1>>X_2>>X_3>>\dots >>X_n$ in the sense that the sign of any partial sum will depend only on the sign of the dominating term. A valid signed permutation (one where all partial sums are positive) of $n$ terms must then be formed by inserting the term $X_n$ into a valid signed permutation of $X_1,\dots,X_{n-1}$. Conversely if we insert $X_n$ into a valid signed permutation of $X_1,\dots,X_{n-1}$, then the only way we can turn this into a non-valid signed permutation is if we insert $X_n$ first and with a negative sign. Therefore the probability that a signed permutation of $n$ terms is valid is $$\frac12\cdot \frac34\cdot\frac56\cdots\frac{2n-1}{2n},$$ as required.

Next, let us move the point $(X_1,\dots,X_n)$ in $\mathbb{R}^n$ and see 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 me take a generic example: Suppose we pass through the hyperplane where the sum $X_3+X_5+X_6-X_2-X_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 $$(X_5+X_6-X_9+X_3-X_2) + \dots$$ goes from valid to invalid, then $$(X_2-X_3+X_9-X_6-X_5) + \dots$$ will go from invalid to valid.

The conclusion is that the probability of a signed permutation being valid (having all partial sums positive) will never change, and will therefore always be equal to the product given in the OP.

UPDATE: Instead of looking at what happens when we cross one of these hyperplanes, here is another way of seeing that $P_n$ is independent of $X=(X_1,\dots,X_n)$, which has the additional feature of showing that $$P_0P_n + P_1P_{n-1}+\cdots + P_nP_0 = 1.$$

Suppose that $X_1,\dots,X_n$ are generic as described above. Let $P_n(X)$ denote the probability that a random signed permutation will have all partial sums positive, and suppose for induction on $n$ that we have shown that $P_k(X) = P_k$ is independent of $X$ for $k=1,\dots,n-1$.

Now let $Y_1,\dots, Y_n$ be a random signed permutation of $X$, and consider the distribution of the $k$ for which the partial sum $Y_1+\dots+Y_k$ is minimized. I 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}+\dots+Y_m$ for $m>k$ must be positive, while similarly all sums of the form $Y_m + Y_{m+1}+\dots+Y_k$ for $m\leq k$ must be negative.

Since generically the minimum is unique, we have $$P_0P_n(X) + P_1P_{n-1}+\cdots + P_n(X)P_0 = 1,$$ which shows that $P_n(X)$ is independent of $X$.

I like this very much, since the equation $P_0P_n + P_1P_{n-1}+\cdots + P_nP_0 = 1$ is crucial for my proof in the Monthly December 2007 of the Wallis product formula for pi, http://www.math.chalmers.se/~wastlund/monthly.pdf. See also Don Knuth's 2010 christmas tree lecture "Why pi?" under "Computer musings" at http://scpd.stanford.edu/knuth/index.jsp. I did a proof by induction and some algebraic manipulation in the Monthly paper, and Knuth used power series and the binomial theorem some 20-25 minutes into his talk, but the argument motivated by this question is much nicer!

-
Wow! It's a wonderful proof. I'm sure you have solved this problem out perfectly. Thanks!^_^ And, I'm feeling grateful to all of you who viewed this problem especially who participate in the discussion about it. I'm wondering, if we change interval $[-1,1]$ to $[l,r]$, can this method work successfully? Or we can use other way to do it? –  Lwins.Gafield Apr 17 '12 at 2:56

Here is a somewhat different way from Johan's of looking at this problem. At each stage of the walk, choose a number $x$ uniformly from $[0,1]$ and then walk either a distance $x$ to the right or $1-x$ to the left. This does not affect the probability of becoming negative since there is still a uniform probability of taking a step whose length belongs to the interval $[-1,1]$. However, it does have the property that after taking $n$ steps and choosing $0\leq x\leq 1$, the two possible locations following the next step are the same modulo 1. Hence the walk can be described as follows. Choose $n$ numbers $0\lt x_1\lt \cdots\lt x_n\lt 1$, a sequence $\epsilon=(\epsilon_1,\dots,\epsilon_n)$ of signs $\pm 1$, and a permutation $w$ of $1,2,\dots,n$. Let the location be $y_k$ after the $k$th step. If $\epsilon_k=1$ then step to the least real number $y_{k+1}\equiv x_{w(k+1)}$ (mod 1), $y_{k+1}>y_k$. If $\epsilon_k=-1$ then step to the greatest real number $y_{k+1}\equiv x_{w(k+1)}$ (mod 1), $y_{k+1}\lt y_k$. But the question of whether any $y_k$ is negative depends only on $\epsilon$ and $w$, not the choice of $x_1,\dots,x_n$. There are $2^n n!$ ways to choose $\epsilon$ and $w$. Is there a simple combinatorial argument that the number of choices such that each $y_k>0$ is $(2n-1)!!=1\cdot 3\cdot 5\cdots (2n-1)$? Then the probability of success is $(2n-1)!!/2^nn! = (2n)!/4^nn!^2$.

Here is a reformulation of the combinatorial result that needs a simple direct proof.

Let $f(n)$ be the number of pairs $(a_1a_2\cdots a_n, b_1b_2\cdots b_{n-1})$ such that (a) $a_1 a_2\cdots a_n$ is a permutation of $1,2,\dots, n$, (b) $b_i=0$ or $1$ if $a_i\lt a_{i+1}$, (c) $b_i=0$ or $-1$ if $a_i>a_{i+1}$, and (d) $b_1 +b_2+\cdots+b_j\geq 0$ for all $1\leq j\leq n-1$. Then $f(n)=(2n-1)!!$.

Update. The combinatorial result is proved bijectively by O. Bernardi, B. Duplantier, and P. Nadeau in Séminaire Lotharingien de Combinatoire, B63e (2010). In their citation [1] they use this result for the same purpose as above, i.e., to compute the probability $P_n$ (though they state the result a little differently).

Second update. The method above can be applied to the $[l,r]$ generalization mentioned by Lwins in his comment. By rescaling we may assume $l=-1$. If we are at $y$ sometime during the walk, choose a number $x$ uniformly from $[0,1]$. With probability 1/2 step from $y$ to $y+\frac{r-1}{2}+\frac{r+1}{2}x$. With probability 1/2 step from $y$ to $y-1-\frac{r+1}{2}x$. This gives a uniform probability of stepping from $y$ to a point in the interval $[y-1,y+r]$. It has the property that once $x$ is chosen, the value of $y$ is determined modulo $\frac{r+1}{2}$. Thus the walk can be described as follows: pick uniformly and independently $0\lt x_1\lt \cdots\lt x_n \lt \frac{r+1}{2}$, pick a permutation $w$ uniformly from the symmetric group $S_n$, and a sequence $\epsilon=(\epsilon_1,\dots,\epsilon_n)$ of independently distributed signs, with a probability of $\frac{r}{r+1}$ for a plus sign and $\frac{1}{r+1}$ for a minus sign. Go through the same procedure as above, working mod $\frac{r+1}{2}$ instead of mod 1. Again a proper walk (i.e., one which never becomes negative) depends only on $w$ and $\epsilon$, and we get the following result:

Theorem. The probability $P_n(r)$ that the walk is proper is given by $$P_n(r) = \frac{1}{(1+r)^nn!}\sum r^{1+f(w,\beta)},$$ summed over all pairs $w=a_1a_2\cdots a_n\in S_n$ and $\beta=(b_1,\dots, b_{n-1})\in \lbrace 0,\pm 1\rbrace^n$ satisfying the conditions (b) and (c) above, where $f(w,\beta)$ is the number of integers $1\leq i\leq n-1$ for which either $a_i\lt a_j$ and $b_i=0$, or $a_i\gt a_j$ and $b_i=1$.

For instance, $P_2(r)= (r+2r^2)/2(r+1)^2$ and $P_3(r) =(r+8r^2+6r^3)/6(r+1)^3$. I conjecture that the numerator $N_n(r)$ of $P_n(r)$ is just the polynomial $\sum B_{n,i}r^i$ defined by equation (4) of http://math.mit.edu/~rstan/pubs/pubfiles/29.pdf. This paper gives some additional information about the polynomials $\sum B_{n,i}r^i$. Much additional information can be found in the literature on Stirling permutations, e.g., Bona proves in http://wenku.baidu.com/view/dfa70012cc7931b765ce15e4.html that all zeros of this polynomial are real.

Third update. Alas, the conjecture in my second update is false. Unless there is an error in my code, the sequence of coefficients of $N_n(r)$ for $2\leq n\leq 7$ are $(1,2)$, $(1,8,6)$, $(1,25,55,24)$, $(1,69,361,394,120)$, $(1,176,1999,4416,3083,720)$, $(1,426,9836,41019,52193,26620,5040)$. It is easy to see why the leading coefficient of $N_n(r)$ is $n!$.

-
Thanks for the reference! –  Johan Wästlund Apr 24 '12 at 3:59

The classic (and beautiful) argument for the discrete analogue is based on the so-called "reflection principle". Look that up in say Feller or online. I believe there is a very natural continuous version.

Alternatively, you could also do the brute force approach. Let $n$ be fixed, and let $\chi(x) : \mathbb{R}^n \to \{0,1\}$ be the characteristic function for the set $[-1, 1]^n$. Then the probability $P_n$ is given by

$$P_n = 2^{-n} \cdot \int_{0} ^{1} \int_{-t_1} ^{1} \int_{-t_1-t_2} ^{1} \cdots \int_{-t_1 - t_2 - \cdots -t_{n-1}} ^{1} \chi(t_1, t_2, \ldots , t_n) dt_n dt_{n-1} \cdots dt_1.$$

This sort of integral can probably be simplified with Fourier transforms.

-

The Computation Below is incorrect, but is left up as a learning tool. Please read the comments for details.

Let $X_i$ be i.i.d. uniform r.v.'s on $[-1,1]$. If I compute $P_n$ for $n=3$, I don't get your value. Am I doing something wrong in my computation? I get the following: \begin{align} P_3 & = \mathbb{P}(X_1 > 0, \; X_2+X_1 > 0, \; X_3+X_2+X_1 > 0 ) \newline & = \frac{1}{8}\int_{-1}^1 \int_{-1}^1 \int_{-1}^1\mathbf{1}{\{x>0,\;y>-x,\;z>-(x+y)\}} dz\;dy\;dx \newline &= \frac{1}{8}\int_{0}^1 \int_{-x}^1 \int_{-(x+y)}^1 dz\;dy\;dx \newline &= \frac{1}{8}\int_{0}^1 \int_{-x}^1 (1+x+y) dy\;dx \newline & = \frac{1}{8}\int_{0}^1 (\frac{3}{2}+2x+\frac{x^2}{2}) dx \newline & = \frac{1}{3}. \end{align} This disagrees slightly with your formula, which gives $P_3 = \frac{5}{16}$.

Let me know if I have misunderstood the problem or made an error, and I will remove this immediately. Otherwise, it seems like a possible answer to your question is to generalize this computation by an inductive argument.

-
Yes, this is wrong. $z$ should go from $\max(-1,-(x+y))$ to $1$, not from $-(x+y)$ to $1$. –  Robert Israel Apr 16 '12 at 21:55
The mistake is that on the third line, $z$ should not necessarily go from $-(x+y)$ to 1. If $x+y>1$, $z$ goes only from $-1$ to 1. You should not feel too embarrassed to have made a mistake. Leaving the answer might help others avoid the same confusion. –  Johan Wästlund Apr 16 '12 at 21:59
...in other words I agree with what Robert Israel just said. –  Johan Wästlund Apr 16 '12 at 22:03
Robert and Johan, thanks for the error check, I see the problem. As Johan said, I will leave this up for people to see the mistake and avoid it. –  Jeremy Voltz Apr 16 '12 at 22:08
Although (or maybe because) Jeremy's integral, generalized in the obvious way, doesn't answer the original problem, it's of interest to ask what sequence of fractions it does produce. It's hard to tell from the numbers 1/2, 3/8, 1/3, but Paul Zorn has kindly calculated the next three cases, obtaining 125/384, 27/80, and 16807/46080, from which it's fairly easy to guess a general answer. (I don't have a proof. Also, I'm leaving my guess unstated in case anyone wants to amuse themselves by ignoring Paul's numbers and seeing if indeed the numbers 1/2, 3/8, 1/3 suggest anything obvious.) –  Barry Cipra Apr 17 '12 at 22:09

Me too, or the first hitting time for $(-\infty,0)$, and I think what he says is right & the distribution is the same for all symmetric continuous r.v.s. I'd look it up if I were home, the ideas are circle of wiener hopf factorization & I think are probably in Feller vol 2., the renewal theory chapter.

-