Simple Random Walk: two questions

Question

I am having difficulty in finding right resource to review. I am preparing interview on probability. One particular topic that I struggle the most is Simple Random Walk. I just want to know the following:

1) finding the first $n$ for which $S_n$ reaches a defined threshold $\alpha$.

2) the probability that $S_n$ reaches $\alpha$ for any given value of $n$.

3) Expected number of steps to reach an end point.

I am wondering where I can find examples specifically for these 3 types of question?

Thanks.

-------

---

Maybe I can try to answer my questions. Assume symmetric. Assume we start from 0.

1) the probability of first n for which $S_n$ reaches 10 is P($S_{10} =10) = 1/2^{10}$

2) for given value of $n$, we want to know the probability that $S_n$ reaches $\alpha$. This is equivalent as if asking $\max(S_1,S_2,S_3,\dots, S_n) \geq \alpha$. And the maximum of this probability formula is given by here : http://www.randomservices.org/random/bernoulli/Walk.html

3) This is simply the gambler ruin's problem, and you can look up the expected time for a player to ruin, which is $\alpha / (\alpha + \beta)$

Answer 1

One useful book could be Probability and Random Processes 3rd ed, by Grimmett and Stirzaker. Sections 3.9 and 3.10 have material on Simple random walks. For the three questions:

1) I think you can use the hitting time theorem, p.79.

2) Here, you could use theorem (10), p. 78.

3) Eq. (9) on p. 74 gives a formula for the mean number of steps $D_k$, starting from $k$ before hitting one of the absorbing barriers at $0$ and $N$, for $p=1/2$, it is $D_k = k(N-k)$.

Answer 2

• You might want to scroll through Simple random walks by Sven Erick Alm. Look at the examples there and if they are considered to be useful, I would like to put the focus on the first reference of the paper, which is called a goldmine if someone likes to get more insight into simple random walks.

  I fully agree and recommend to read the roughly $30$ pages of Chapter III: Fluctuations in Coin Tossing and Random Walks of the classic An Introduction to Probability Theory and Its Applications, Vol. I by W. Feller.

• Nice, easy-to-read examples are presented in this MIT paper titled Random Walks.

Answer 3

It seems to me that your questions are related to one-dimensional simple random walk with absorbing barriers. A popular application is gamblers ruin problem.

I hope the following resources will be helpful, for a quick start:

1. Markov Processes for Stochastic Modeling By Oliver Ibe; Chapter-8
2. Elements of Random Walk and Diffusion Processes By Oliver Ibe
3. Introduction to Probability Models, By Sheldon M. Ross