# Hitting probabilities for conditioned oriented random walk monotonic?

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!

• 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. Apr 12, 2015 at 19:27
• Sure. Just stating it in general since I want the analogue in $\mathbb Z^d$ for higher $d$. Apr 13, 2015 at 2:02

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.
• 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). Apr 12, 2015 at 19:18
• Thanks. I'll see if I can duplicate this in $\mathbb Z^3$. Similar monotonicity really ought to hold in any dimension. Right? Apr 13, 2015 at 2:05
• @mathjunge: I really don't have much intuition on this, not even for the simple looking inequality $q_1\ge p^*$. Apr 13, 2015 at 2:29
{"ft_lang_label":"__label__en","ft_lang_prob":0.8546255,"math_prob":0.99994373,"size":1220,"snap":"2022-05-2022-21","text_gpt3_token_len":423,"char_repetition_ratio":0.118421055,"word_repetition_ratio":0.0,"special_character_ratio":0.3614754,"punctuation_ratio":0.099631,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999931,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-28T19:52:31Z\",\"WARC-Record-ID\":\"<urn:uuid:c21fde11-841c-404c-b87a-b2aaf156f728>\",\"Content-Length\":\"108137\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9849251f-f4b4-4ee1-9c58-b99313f11da3>\",\"WARC-Concurrent-To\":\"<urn:uuid:e9935ea1-5487-4c40-9c20-aa4037f5af38>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/202717/hitting-probabilities-for-conditioned-oriented-random-walk-monotonic\",\"WARC-Payload-Digest\":\"sha1:FGUSGCLDIJRVUDRMD47U2ZUCLKKCMZJ4\",\"WARC-Block-Digest\":\"sha1:OQJJDE5YZ42NHIEUGE7IY6JKNZJWZI3O\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652663019783.90_warc_CC-MAIN-20220528185151-20220528215151-00034.warc.gz\"}"}