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!



Hitting probabilities for conditioned oriented random walk monotonic?
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.


