# Questions tagged [random-walk]

For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.

125 questions
24k views

### Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1

How does one prove that a simple (steps of length $1$ in directions parallel to the axes) symmetric (each possible direction is equally likely) random walk in $1$ or $2$ dimensions returns to the ...
9k views

### Hitting probability of biased random walk on the integer line

Lets say we start at point 1. Each successive point you have a, say, 2/3 chance of increasing your position by 1 and a 1/3 chance of decreasing your position by 1. The walk ends when you reach 0. ...
5k views

### Random walk on $n$-cycle

For a graph $G$, let $W$ be the (random) vertex occupied at the ﬁrst time the random walk has visited every vertex. That is, $W$ is the last new vertex to be visited by the random walk. Prove the ...
4k views

### Mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space.

I am looking for a formula that evaluates the mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space. Such a formula was given by "Henry" to a question by "Diego" (q/...
22k views

### Expected Value of Random Walk

Can someone very simply explain to me how to compute the expected distance from the origin for a random walk in $1D, 2D$, and $3D$? I've seen several sources online stating that the expected distance ...
574 views

### Random walk $< 0$

Suppose ${X_t}$ is a random walk with mean zero. (either discrete or continuous time) Fix a time $T$. What is: $P[X_t < 0 \text{ for all } t \leq T]$? In words, what's the probability the random ...
109 views

### Potential uses for viewing discrete wavelets constructed by filter banks as hierarchical random walks.

I have some weak memory that some sources I have encountered a long time ago make some connection between random walks and wavelets, but I am quite sure it is not in the same sense. What I was ...
3k views

278 views

1k views

### Expectation of $TS_T$ where $T$ is the absorption time at $\{a,-a\}$ of a simple symmetric random walk $\{S_n\}$

I was trying to calculate the expectation of $T^2$ using some martingale and got that I needed the expectation of $TS_T$. Any idea?
964 views

2k views

### Markov property in a simple random walk

How can I prove that a random walk satisfies the Markov property? I have the simple random walk defined as $S_n = \sum_{k=1}^n X_k$ where $X_i$'s are independent and identically distributed random ...
4k views

### Expected number of steps till a random walk hits a or -b. [duplicate]

On wikipedia I read that the expected number of steps till a 1D simple random walk hits either $a$ or $-b$ is equal to $ab$. (I have seen this result also on other websites.) However, no proof or ...
178 views

### (Random Walk) Compute average ratio for the number of right cookies to total cookies eaten in a single cycle

This question is a continuation of this post. Currently I am reading the paper Excited Random Walk in One Dimension. At page $8$ right column, the authors obtain equation $(33)$. The joint ...
367 views