# Compute the expected value of the next step of a sorted random walk

Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. Similarly, if you're at the minimum, then the next step you take is +1 with probability 1. I'm wondering if these are special cases of a more general phenomenon. My guess is that if you're near the maximum of the walk, then the expected value of the next step is negative and if you're near the minimum of the walk, then the expected value of the next step is positive. I'm trying to make this intuition rigorous. Here's what I've got so far.

• I have a random variable $X$ with $Prob\{X=+1\} = Prob\{X=-1\} = 1/2$.
• Fix $N$ and take $N$ independent trials to get $D_1,D_2,...,D_N$, where $D_i = +/- 1$.
• Now the random walk is given by $S_k = \sum_{i=1}^{k} D_i$, where we take $S_0 = 0$.

Now what I want to do is to sort the walk based on position:

• Let $T = sort(S)$, where ties are broken by taking the earlier instance.
• Let $I$ be the sort permutation for getting $T$ from $S$ so that $I_k = j$ means that $T_k = S_j$.

Finally, the problem I have is that I want to compute the following:

$E( D_{I_{j} + 1} )$

and

$Var( D_{I_{j} + 1} )$

I've gotten this far with setting the problem up, but I'm completely stuck on how to solve it. Anybody have any ideas? Thanks so much!

So I worked out some small cases. Here's the expected values for $(1,2,...,N)$ (I factored out the $2^N$):

• $N = 1: (0)/2$
• $N = 2: (2,-2)/4$
• $N = 3: (6,-2,-4)/8$
• $N = 4: (12,2,-4,-10)/16$
• $N = 5: (26,4,4,-14,-20)/32$
• $N = 6: (52,14,8,-2,-28,-44)/64$

I guess I just don't see the pattern. I checked OEIS but no matches.

-
Have you computed what you're after for the first few small values of N? If so, can you post the results? –  Barry Cipra Jul 22 '11 at 20:15
Should the random walk be $S_k = sum_{i=1}^k D_i$? –  Jeremy West Jul 22 '11 at 22:07
@Jeremy: Of course! Thanks for catching that. –  Random Walker Jul 22 '11 at 22:20
I'm sorry, I don't understand the notation you're using to report the small cases results. Am I just being dense? –  Barry Cipra Jul 22 '11 at 22:59
@Barry: For N=4, there are four expected values to compute. The expected step after the "smallest" position is 12/16; the expected step after the "second smallest" position is 2/16; ...; the expected step after the "largest" position is -10/16. Does that make sense? –  Random Walker Jul 22 '11 at 23:08