User random walker - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:20:49Z http://mathoverflow.net/feeds/user/16663 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> http://mathoverflow.net/questions/71011/compute-the-expected-value-of-the-next-step-of-a-sorted-random-walk Comment by Random Walker Random Walker 2011-07-22T23:40:21Z 2011-07-22T23:40:21Z @Barry: I am sorting deterministically, taking the earliest case of a value first. That is, if <code>$S&#95;i = S&#95;j$</code> and <code>$i&lt;j$</code>, then <code>$S&#95;i$</code> appears before <code>$S&#95;j$</code> in the sort order. http://mathoverflow.net/questions/71011/compute-the-expected-value-of-the-next-step-of-a-sorted-random-walk Comment by Random Walker Random Walker 2011-07-22T23:08:06Z 2011-07-22T23:08:06Z @Barry: For <code>N=4</code>, there are four expected values to compute. The expected step after the &quot;smallest&quot; position is <code>12/16</code>; the expected step after the &quot;second smallest&quot; position is <code>2/16</code>; ...; the expected step after the &quot;largest&quot; position is <code>-10/16</code>. Does that make sense? http://mathoverflow.net/questions/71011/compute-the-expected-value-of-the-next-step-of-a-sorted-random-walk Comment by Random Walker Random Walker 2011-07-22T22:20:43Z 2011-07-22T22:20:43Z @Jeremy: Of course! Thanks for catching that.