2
$\begingroup$

Consider an oriented random walk on $\mathbb Z^2$ (i.e. only steps $\rightarrow$ and $\uparrow$ with equal probability.) Say we let the walk go $2m$ steps then start guessing sites at distance $2m$ from the origin until we pick up its trail. The best first guess is at $(m,m)$ which has probability $p^* = \binom{2m}{m} 4^{-m}$ of being included in the walker's trail. Say the walker was not at $(m,m)$, the next natural guess is $(m+1,m-1)$. Let $q_1$ be the probability the walker crossed $(m+1,m-1)$ given it didn't cross at $(m,m)$. I am looking for a proof that $$q_1 \geq p^*\text{.}$$ In general, take $A_i$ to be the event the walk crossed at $(m+i,m-i)$ and $B_{i-1}$ that the walk did not cross at $\{(m\pm j,m \mp j) \colon j=0,1,\cdots,i-1\}$. Define $q_i = \mathbf P[A_i \mid B_{i-1}]$. Pretty sure that $q_i$ can be written as $$q_i = \frac{\mathbf P[A_i \cap B_{i-1} ]}{\mathbf P[ B_{i-1}]}=\frac{ \binom{2m}{m+i} } { 4^m - \binom{2m}{m} - 2\sum_{j=1}^{i-1} \binom{2m}{m+j} }.$$ I'd like to show $q_{i+1} \geq q_i.$ Either via being good with binomial coefficients or with a probabilistic proof about conditioned random walk.

I'm also interested in the analogue for oriented walk on $\mathbb Z^d$. Thanks!

$\endgroup$
  • $\begingroup$ By the way, there's nothing genuinely two-dimensional about your setup. You could just use $\pm 1$ instead of $\rightarrow$, $\uparrow$, and then you have a 1D random walk. $\endgroup$ – Christian Remling Apr 12 '15 at 19:27
  • $\begingroup$ Sure. Just stating it in general since I want the analogue in $\mathbb Z^d$ for higher $d$. $\endgroup$ – mathjunge Apr 13 '15 at 2:02
2
$\begingroup$

I have a brute force calculation that establishes this. Your formula for $q_i$ is not completely correct; it should read $q_i=\binom{2m}{m+i}/A_i$ with $$ A_i = 4^m - \binom{2m}{m} - 2\sum_{j=1}^{i-1} \binom{2m}{m+j} . $$

To see that $q_1\ge p^*$, let's just write $$ \binom{2m}{m+1}=\binom{2m}{m}\frac{m}{m+1} , $$ so after rearranging the claim becomes $$ \binom{2m}{m}4^{-m} \ge \frac{1}{m+1} , $$ and this is true (induction on $m$ if all else fails).

Similarly, I can use that $\binom{2m}{m+i+1}=\binom{2m}{m+i}\frac{m-i}{m+i+1}$ to rewrite the other claim $q_{i+1}\ge q_i$ as $$ \frac{m-i}{m+i+1}A_i \ge A_i-2\binom{2m}{m+i} . $$ This I can rearrange some more to obtain $$ A_i \le \frac{2(m+i+1)}{2i+1}\binom{2m}{m+i} . \quad\quad\quad\quad (1) $$ Now $2\binom{2m}{m+i}$ is the new summand that gets added on when going from $A_i$ to $A_{i+1}$, so an equivalent form of (1) is $$ A_{i+1}\le \frac{2(m-i)}{2i+1}\binom{2m}{m+i} = \frac{2(m+i+1)}{2i+1}\binom{2m}{m+i+1} .\quad\quad\quad\quad (2) $$ We can now establish (2) by induction on $i$, starting at the maximum value $i=m$. Since $A_{m+1}=0$, (2) certainly holds for $i=m$. Now if I assume (2) for $i+1$ taking the role of $i$ (and with $i\le m-1$), then I have (1) for $i+1$, so to obtain (2) for $i$, it suffices to check that $$ \frac{2(m+(i+1)+1)}{2(i+1)+1}\le \frac{2(m+i+1)}{2i+1} . $$ This is straightforward.

$\endgroup$
  • $\begingroup$ We can also check $i=m-1$ by hand as well and then proceed with the induction (to avoid $\binom{2m}{2m+1}=0$, though this is not really necessary). $\endgroup$ – Christian Remling Apr 12 '15 at 19:18
  • $\begingroup$ Thanks. I'll see if I can duplicate this in $\mathbb Z^3$. Similar monotonicity really ought to hold in any dimension. Right? $\endgroup$ – mathjunge Apr 13 '15 at 2:05
  • $\begingroup$ @mathjunge: I really don't have much intuition on this, not even for the simple looking inequality $q_1\ge p^*$. $\endgroup$ – Christian Remling Apr 13 '15 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.