How do you solve random walk problems with time or step limits?

Question

Assume you have some random walk, what's the general approach to solving a problem where the question asks for the probability of reaching a certain point given a maximum of "n" steps? Is this type of problem still a random walk problem?

I'm self learning random walks.

Answer 1

A good resource for this sort of thing is ME Fisher's "Walks, Walls, and Wetting":

https://link.springer.com/content/pdf/10.1007/BF01009436.pdf

The basic idea is to:

1. Calculate the probability that you instead don't reach the point in $n$ steps.

2. Find this probability by summing over the probabilities of all walks that never reach the point.

3. In the crucial step, realize that, starting at $0$ and reaching $n-a$ without ever passing through $n$ is equal to the probability of reaching $n-a$ minus the probability of reaching $n+a$. The idea is that each path that reaches $n-a$ after passing through $n$ can be mapped one-to-one with a different path that instead goes to $n+a$.

Answer 2

Perhaps spectral graph theory would be a good tool. In spectral graph theory, graphs are given as random walk matrix and probability distributions on graphs are given as vectors.

For graph $G=(V,E)$, the random walk matrix $M$ of it is defined as $M_{ij}$ being the probability that walking start from vertical $i$ and reach $j$ in one step. Let $u$ be the uniform distribution on $G$, the $u=(1/|V|,\cdots,1/|V|)$. One defines $$ \lambda(G) = \max _{\pi} \frac{\|\pi M-u\|}{\|\pi-u\|}=\max _{x \perp u} \frac{\|x M\|}{\|x\|} $$ where the first max is taken over all the probability distributions while the second one is taken over all vectors perpendicular to $u$. It is interesting that $\lambda(G)$ equal to $|\lambda_2|$ where $\lambda_2$ is the eigenvalue of $M$ with second largest absolute value. And for a regular graph and any initial distribution $\pi$, we have the following result $$ \left\|\pi M^{t}-u\right\| \leq \lambda(G)^{t} \cdot\|\pi-u\| \leq \lambda(G)^{t} $$ It is easy to see that $\pi M^t$ is the distribution that we starting with $\pi$ and walking for $t$ steps. For non-regular graphs, we can make it regular by adding self-loops and if doesn't increase the hitting probability of any vertical in any steps.

This does give a lower bound of probability of "reaching a certain point of maximum 'n' steps".

References:

1. Salil P. Vadhan. Pseudorandomness, https://people.seas.harvard.edu/~salil/pseudorandomness/