How do you solve random walk problems with time or step limits? 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.
 A: 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:

*

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


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


*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$.
A: 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:

*

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