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.

Start with an N step random walk:

- 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.

`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