Consider a random walk on $\mathbb{Z}^2$, starting at $(0,0)$. Each step it moves rightwards with probability $p$ and upwards with probability $q=1-p$. The random walk terminates when it hits the right boundary $x=T$ or top boundary $y=T$ for some threshold $T$. The question is to find the probability that the random walks hit the right boundary and the probability that it hits the top boundary.

I feel this may be a classical problem but I cannot find any reference. It is easy to see that $$ \Pr\{\text{hitting right boundary}\} = \sum_{i=0}^T \binom{i+T}{T} q^i p^{T+1} $$ and $$ \Pr\{\text{hitting top boundary}\} = \sum_{i=0}^T \binom{i+T}{T} p^i q^{T+1}. $$ There seems no simple closed expression for the probabilities.

Question 1. Is there a simple proof to show that the two probabilities above sum up to $1$?

Question 2. Consider the random walk in a $d$-dimensional space, starting at $x=0$. Each time we have $x\gets x+e_i$ with probability $p_i$, where $e_1,\dots,e_d$ are the canonical basis vectors and $\sum_i p_i=1$. The random walk terminates when $\|x\|_\infty=T$. Similarly we can express the probability $\Pr\{x_i = T\}$ in terms of multinomial coefficients.

What is an asymptotic upper bound for $\Pr\{x_i = T\}$ for each $i$ upon termination?

I feel these are probably standard questions so perhaps somebody can point me to literature.


Your Answer

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

Browse other questions tagged or ask your own question.