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 ...
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. ...
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 ...
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/...
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 ...
3
votes
1answer
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 ...
5
votes
0answers
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 ...
3
votes
1answer
3k views

Probability of asymmetric random walk returning to the origin

Consider the random walk $S_n$ given by $ S_{n+1} = \left\{ \begin{array}{lr} S_n+2 & with & probability & p\\ S_n - 1 & with & probability & 1-p \end{array} \...
2
votes
3answers
326 views

Probability that random walk will reach state $k$ for the first time on step $n$

We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to ...
2
votes
3answers
1k views

Symmetric random walk with bounds

can anyone help me with this: We are considering a symmetric random walk that ends if level 3 is reached or level -1 is reached. Start=0 What is the expected number of walks? So I am looking for: $E[{...
0
votes
1answer
278 views

Asymmetric Random Walk / Prove that $T:= \inf\{n: X_n = b\}$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time

Given random variables $Y_1, Y_2, ... \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \...
0
votes
1answer
115 views

Brownian Motion problem 22

For a standard Brownian motion $\{W_t, t\geq 0\}$, find $\mathbb{P}(\max_{ t \in [0,1]}|W_t| <x)$. Page 79-80 of Billingsley, P., Convergence of probability measures, New York-London-Sydney-...
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 ...
13
votes
1answer
884 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 ...
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$ ...
4
votes
1answer
3k views

Expected number of steps in a random walk with a boundary

Let's say I am trying to climb a flight of $N$ stairs. Each time I want to take a step, I flip a fair coin. Heads means I take a step up; tails means I take a step down. If I'm at the bottom of the ...
1
vote
1answer
281 views

Returning Paths on Cubic Graphs

Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin? Or putting it differently: What is "Pólya's Random Walk Constant" on ...
5
votes
1answer
2k views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
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 ...
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
4
votes
1answer
446 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t &...
4
votes
1answer
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?
3
votes
2answers
964 views

Limit value of a product martingale

This question came from a problem i was solving for self-study. I'll state the problem first: Let $Y_n \sim \mathcal N(0,\sigma^2)$ be independent normally distributed variables, $X_n = Y_1+\cdots+...
2
votes
3answers
3k views

Exact Probability of Collision of Two Independent Random Walkers After N Steps

Two drunks start together at the origin at $t=0$ and every second they move with equal probability either to the right or to the left, each drunk independently from the other. What is the probability ...
3
votes
0answers
3k views

Reflection principle for simple random walk

Let $(X_n)$ be a sequence of independent random variables, such that $P(X_i=1) = P(X_i=-1) = 1/2$. Then, the reflection principle states that for all $a > 0$, $$P(\max_{1\leq k\leq n} S_k \geq a) =...
2
votes
2answers
3k views

What are some martingales for asymmetric random walks?

Here are some examples for symmetric ones: https://mathoverflow.net/questions/55092/martingales-in-both-discrete-and-continuous-setting/55101#55101 Is there a similar list for asymmmetric random ...
1
vote
2answers
861 views

Showing stopping is finite almost surely

Consider a discrete random walk taking values +1 or -1 with probabilities p and q, respectively. Let $S_n = \sum_{k=1}^{n}X_k$. Let $[-A,B]$ be an interval, $A,B \geq 1$. Now define $$\tau =\min(n:n \...
1
vote
2answers
4k views

Stationary distribution of random walk on a graph

If you do a random walk on an undirected, connected graph, is the stationary distribution for the probability that you have just traversed edge $e$ uniform over all edges no matter what the graph ...
6
votes
1answer
6k views

Random walk as a martingale?

Let $S_0$, $Z_1$, $Z_2$, $\ldots$ be independent random variables. $S_n=S_0+Z_1+\cdots+Z_n$, $n=0,1,2,\ldots$ $S_n$ is a random walk starting in a random point, $S_0$ I need to find out, when it is a ...
3
votes
4answers
2k views

Random walking and the expected value

I was asked this question at an interview, and I didn't know how to solve it. Was curious if anyone could help me. Lets say we have a square, with vertex's 1234. I can randomly walk to each ...
3
votes
0answers
117 views

Markov chains and Random walks on top of biological data

I'm coming from biology's field and thus I have some difficulties in understanding (intuitively?) some of the ideas of that paper. Initially, I posted this question to the StackOverflow, but they ...
2
votes
1answer
489 views

Asymmetric Random Walk / Prove that $E[\inf\{n: X_n = b\}] < \infty$

Given random variables $Y_1, Y_2, \ldots \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
367 views

Asymmetric Random Walk / Prove $E[T] = \frac{b}{p-q}$ / How do I use hint?

Given random variables $Y_1, Y_2, \ldots \stackrel{\mathrm{iid}}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}...
0
votes
1answer
174 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.
0
votes
2answers
575 views

Non-Probabilistic Argument for Divergence of the Simple Random Walk

The simple random walk is one starting at $0$ with steps of $-1$ and $1$ with equal probability. Is there a proof not involving (too much) probability - preferably number-theoretic - of why this walk ...
0
votes
1answer
154 views

Symmetric Random Walk / Prove $S = \inf\{n : X_n = 7\}$ and $T = 10^{12} \wedge S$ are $\{\mathscr F_n^Y\}$-stopping times.

Given a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$ where $\mathscr F_n = \mathscr F_n^Y$, let $Y_1, Y_2, ...$ be iid random variables w/ $P(Y_n = ...
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)^...
29
votes
1answer
487 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
605 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 ...
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 ...
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 ...
12
votes
3answers
838 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$ ...
2
votes
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 ...
4
votes
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 ...
2
votes
2answers
961 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 ...
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 ...
8
votes
2answers
676 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 ...