Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-walk]

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

54
votes
9answers
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 ...
53
votes
1answer
3k views

Identity for simple 1D random walk

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)^...
34
votes
4answers
9k views

±1-random walk from 5 until 20 or broke [closed]

You play a game where a fair coin is flipped. You win 1 if it shows heads and lose 1 if it shows tails. You start with 5 and decide to play until you either have 20 or go broke. What is the ...
34
votes
1answer
810 views

Probability of completing a self-avoiding chessboard tour

Someone asked a question about self-avoiding random walks, and it made me think of the following: Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it ...
29
votes
2answers
647 views

Random Walk Without Repetitions

Suppose that we simulated a random walk on $\mathbb Z$ starting at $0$. At each step, we transition from position $x$ to position $x-3,\,x-2,\,x-1,\,x+1,\,x+2,$ or $x+3$ with equal probability. If we ...
29
votes
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. ...
27
votes
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 ...
26
votes
3answers
5k views

Random walk on $n$-cycle

For a graph $G$, let $W$ be the (random) vertex occupied at the first 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 ...
25
votes
2answers
892 views

Random walk: police catching the thief

This is a problem about the meeting time of several independent random walks on the lattice $\mathbb{Z}^1$: Suppose there is a thief at the origin 0 and $N$ policemen at the point 2. The thief and ...
21
votes
1answer
439 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = v\}$ ...
19
votes
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 ...
18
votes
1answer
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 ...
17
votes
1answer
1k views

Number of steps the path-avoiding snail must take before a step size of $(2n - 1)/2^k$?

Suppose the path-avoiding snail walks along the grid according to the following algorithm: At each step, the snail steps unit distance if doing so will not collide with its trail. If a step of unit ...
17
votes
1answer
188 views

height of domino tower

Suppose you are building a domino tower using identical pieces of unit length. You place a new domino piece, one at a time, on the top of the tower. However there is a random error in the placement of ...
14
votes
0answers
338 views

Expected range of simple random walk in $\mathbb{Z^2}$

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: $$R_n=|\{...
13
votes
1answer
872 views

Is there an intuitive way to see this property of random walks?

For an $n$-step symmetric simple random walk (start at origin 0 and each step 1 unit towards left or right with equal probability,) an interesting fact is that the probability that you stop exactly at ...
13
votes
1answer
203 views

How can I prove this bijection between random walks?

Let $R_n$ be the set of simple random walk paths such that $S_n=0.$ $P_n$ be the set of simple random walk paths such that $\forall i \in \{1,2,...,n\},$ $S_i > 0$. $N_n$ be the set of paths ...
12
votes
3answers
828 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$ ...
12
votes
3answers
302 views

Select a new value from last $N$ values; how long until the last $N$ are all the same?

Say first we have N distinct numbers in a line, like 1,2,3,...,N, in each round, we choose a ...
12
votes
1answer
606 views

Does this modified random walk (2D) return with probability 1?

Pólya showed that a random walk (with the directions at each step uniformly distributed) on the integer lattice returns with probability 1. What if instead we consider the random walk where we are ...
12
votes
1answer
209 views

Random walk on thin ice?

My Question: Is the stochastic process which is described below a (special case of a) well-studied model? What kind of properties are known under which assumptions? Let's think of a random walker on ...
12
votes
1answer
455 views

Random walks and diffusion limits

Imagine a long and narrow cylinder of radius r and a point particle that moves in the region bounded by the cylinder. The motion is specified as follows: starting at a point on the inner wall of the ...
12
votes
0answers
2k views

Does the “prime ant” ever backtrack?

A few mathematical questions have come up from the question "The prime ant 🐜" on the Programming Puzzles & Code Golf Stack Exchange. Here is how the prime ant is defined: Initially, we have ...
11
votes
3answers
753 views

Probability of landing on the nth stair.

Initial Question: We begin climbing a staircase beginning at stair zero. We choose to take either 1,2, or 3 steps at a time, where each number of steps have an equal chance of being chosen. What is ...
11
votes
2answers
3k views

Biased Random Walk and PDF of Time of First Return

I have a random walk process where each step the probability of $+1$ is $p$ and $-1$ is $q$, with $p+q=1$. $p$ may not equal $q$. The walker starts at zero. I want to know the probability that the ...
11
votes
3answers
522 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...
11
votes
1answer
289 views

How to combine the four Theorems in order to prove the statement?

I have a question concerning a statement about Random Walks on $\mathbb{Z}$. Let $F$ be a distribution on $\mathbb{Z}$ which has mean $0$ and finite variance. Let $\left\{X_1,X_2,\ldots\right\}$ be an ...
10
votes
3answers
2k views

Random solving of a Rubik cube .

After playing a little with a Rubik cube I thought of the following problem : Suppose we start with a solved Rubik cube (a general one , with $n^3$ cubes) . Then we choose one of the moves , each ...
10
votes
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 ...
10
votes
0answers
235 views

A generalization of simple random walk

Suppose $S_n, n\geq 0$ is a martingale on $\mathbb{R}$ such that $S_0=0$ and $|S_{n+1}-S_{n}|\in [\frac{1}{2}, 1]$. Prove that there exists $c,C>0$ s.t. $$ \frac{c}{\sqrt{n}} \leq P( S_1\geq 0,\...
9
votes
3answers
2k views

Probability a random walk is back at the origin

I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put. After $n$ ...
9
votes
3answers
13k views

1D random walk-probability to go back to origin

Suppose There is a random walk starting in origin while probability to move right is 1/3 and probability to move left 2/3.What is the probability to return to the origin. Thank you
9
votes
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 ...
9
votes
4answers
419 views

Martha has a fair die with the usual $6$ sides…What is the probability that she stops at a cumulative sum of $13$?

Martha has a fair die with the usual six sides. She throws the die and records the number. She throws the die again and adds the second number to the first. She repeats this until the ...
9
votes
3answers
613 views

Simple Random Walk: two questions

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 ...
9
votes
1answer
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/...
8
votes
3answers
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. ...
8
votes
6answers
412 views

simplify summation of factorial (random walk)

I suspect that the expression $$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$ simplifies to $$\frac{2^N}{(N-1)!}$$ But I cannot find the intermediate steps. Can someone give me a hint how I can deduce ...
8
votes
3answers
203 views

Random walk with 3 cases.

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 ...
8
votes
2answers
663 views

Drunkards walk on a sphere.

I simulated the following situation on my pc. Two persons A and B are initially at opposite ends of a sphere of radius r. Both being drunk, can take exactly a step of 1 unit(you can define the unit, i ...
8
votes
2answers
215 views

Probability of finding a random mass

Suppose we have a list of distinctive elements: $$X_0=\{x_1,x_2,x_3,\cdots,x_n\}$$ Each element has mass 1. Suppose we take two elements at random and make a new element with appropriate mass. For ...
8
votes
1answer
921 views

Last vertex visited by the symmetric random walk on a discrete circle

$n$ cats form a circle, indexed from $0$ to $n-1$. At first, there is a ball at the cat $0$. We throw a coin with the probability of $p$ heads up. If the coin is heads up, we pass the ball clockwise, ...
8
votes
1answer
498 views

Expected travel of random walk in arbitrary game with multiple payouts

As explained here, the average distance or 'travel' of a random walk with $N$ coin tosses approaches: $$\sqrt{\dfrac{2N}{\pi}}$$ What a beautiful result - who would've thought $\pi$ was involved! ...
8
votes
1answer
247 views

First player to win k matches

A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking for a probabilistic description of the outcome when looking at ...
8
votes
1answer
92 views

Bounding survival probability of an asymmetric random walk by a symmetric one

Consider two random walks that start from point $x=0$ and time $t=0$ and move either to right $x+1$ or left $x-1$: 1) Walker 1's first move is with equal probability to the right/left. However, ...
8
votes
1answer
348 views

Jump Process - Random Walk

A 1-D random walker strarting at time $t=0$ and location $x=0$, moves to the right ($x+1$) or the left ($x-1$) according to independent random variables $R_1,R_2,\ldots$ and $L_1,L_2,\ldots$, such ...
8
votes
1answer
176 views

How long until everyone has been in the lead?

Earlier, I asked a question about a series of competitions: A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking ...
8
votes
0answers
166 views

Is the following series consisting of $\pm 1$ bounded? [closed]

(Link to cross-post to MathOverflow) Let $b=\frac{\sqrt{5}-1}2$ and $a_n:=(-1)^{[nb]}$ where $[\cdot]$ denotes the floor function. Are the partial sums $A_N=\sum\limits_{n=0}^N a_n$ bounded? The ...
8
votes
0answers
189 views

Brownian Motion in Confined space, any results?

I am searching for work regarding Brownian motion in a confined space, like a sphere or a cylinder, where the wall will serve as reflection boundary. I am wondering if it is possible to derive results ...
8
votes
0answers
498 views

Random matrices, eigenvalue distribution.

I just investigated randn(1024) + 1i*randn(1024), a 1024x1024 complex valued matrix with elements both real part and imaginary part drawn from $\mathcal{N}(\mu = 0, \sigma = 1)$. I was a bit surprised ...