2
$\begingroup$

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.

$\endgroup$

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.