# Questions tagged [random-walk]

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

124 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 ...
566 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 ...
104 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

274 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?
954 views

350 views

172 views

### probability, random walk, Markov chain question

Let $P$ be a transition matrix for a regular Markov chain and let $w$ be it’s equilibrium vector. Show that $w$ has no zero entries.
3k views

The question is to find a purely probabilistic proof of the following identity, valid for every integer $n\geqslant1$, where $(S_n)_{n\geqslant0}$ denotes a standard simple random walk: E[(S_n)^... 1answer 484 views ### A random walk on a finite square with prime numbers This question is following two similar questions that you can find here and here. The idea is to walk on a square of length n\times n, following some rules. We will identify the opposite sides. ... 3answers 593 views ### A prime number random walk This question came to my mind thanks to this question which I found really interesting (and beautiful! Like the mathematician Philippe Caldero said in his book Histoires Hédonistes de Groupes et de ... 5answers 3k views ### Probability of two people meeting in a given square grid. Amy will walk south and east along the grid of streets shown. At the same time and at the same pace, Binh will walk north and west. The two people are walking in the same speed. What is the ... 2answers 4k views ### Random walk on a cube Start a random walk on a vertex of a cube, with equal probability going along the three edges that you can see (to another vertex). what is the expected number of steps to reach the opposite vertex ... 3answers 826 views ### Random walk on natural number Problem: You are standing at the position 0 on the line of natural numbers 0, 1, 2, ..., n. From this position you go to 1 with probability 1, but from any other position i you go to i+1 ... 2answers 1k views ### Random Walk on Clock Hands We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps. If you start at 1 what is the expected number ... 2answers 1k views ### Distribution of the Maximum of a (infinite) Random Walk Let S_0 = 0 and define S_n = \sum^n_{i = 1} X_i such that \begin{align*} \mathbb P(X_i = 1) &= p \\ \mathbb P(X_i = -1) &= 1 - p = q \end{align*} for p < \frac{1}{2}. Find the ... 2answers 954 views ### Random walk on vertices of a cube If a particle performs a random walk on the vertices of a cube, what is the mean number of steps before it returns to the starting vertex S? What is the mean number of visits to the opposite vertex T ... 1answer 1k views ### Expected number of times Random Walk crosses 0 line. Suppose we have a simple random walk: x_t = x_{t-1} + \epsilon_{t} $$Where$$ \epsilon_{t} = iid\ \mathcal{N} (0,1)  Assume that x starts at ...
Let the walking start be at $x=0$. With probability $p_1$ new $x=x+1$, with probability $p_2$: $x=x-1$ and with probability $1-p_1-p_2 \geq 0$ walking ends. The question is what is the probability of ...