Compute the expected value of the next step of a sorted random walk - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:45:41Z http://mathoverflow.net/feeds/question/71011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71011/compute-the-expected-value-of-the-next-step-of-a-sorted-random-walk Compute the expected value of the next step of a sorted random walk Random Walker 2011-07-22T18:08:38Z 2011-07-22T23:05:49Z <p>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.</p> <p>Start with an N step random walk:</p> <ul> <li>I have a random variable <code>$X$</code> with <code>$Prob\{X=+1\} = Prob\{X=-1\} = 1/2$</code>.</li> <li>Fix <code>$N$</code> and take <code>$N$</code> independent trials to get <code>$D_1,D_2,...,D_N$</code>, where <code>$D_i = +/- 1$</code>.</li> <li>Now the random walk is given by <code>$S_k = \sum_{i=1}^{k} D_i$</code>, where we take <code>$S_0 = 0$</code>.</li> </ul> <p>Now what I want to do is to sort the walk based on position:</p> <ul> <li>Let <code>$T = sort(S)$</code>, where ties are broken by taking the earlier instance.</li> <li>Let <code>$I$</code> be the sort permutation for getting <code>$T$</code> from <code>$S$</code> so that <code>$I_k = j$</code> means that <code>$T_k = S_j$</code>.</li> </ul> <p>Finally, the problem I have is that I want to compute the following:</p> <p><code>$E( D_{I_{j} + 1} )$</code></p> <p>and</p> <p><code>$Var( D_{I_{j} + 1} )$</code></p> <p>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!</p> <hr> <p>So I worked out some small cases. Here's the expected values for <code>$(1,2,...,N)$</code> (I factored out the <code>$2^N$</code>):</p> <ul> <li><code>$N = 1: (0)/2$</code></li> <li><code>$N = 2: (2,-2)/4$</code></li> <li><code>$N = 3: (6,-2,-4)/8$</code></li> <li><code>$N = 4: (12,2,-4,-10)/16$</code></li> <li><code>$N = 5: (26,4,4,-14,-20)/32$</code></li> <li><code>$N = 6: (52,14,8,-2,-28,-44)/64$</code></li> </ul> <p>I guess I just don't see the pattern. I checked OEIS but no matches.</p>