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

2011-07-22T18:08:38Z

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.

Comment by Random Walker

2011-07-22T23:40:21Z

@Barry: I am sorting deterministically, taking the earliest case of a value first. That is, if $S_i = S_j$ and $i<j$ , then $S_i$ appears before $S_j$ in the sort order.

Comment by Random Walker

2011-07-22T23:08:06Z

@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?

Comment by Random Walker

2011-07-22T22:20:43Z

@Jeremy: Of course! Thanks for catching that.

User random walker - MathOverflow

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

Comment by Random Walker

Comment by Random Walker

Comment by Random Walker