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

learn more… | top users | synonyms

42
votes
1answer
2k 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: $$ ...
25
votes
2answers
369 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 ...
23
votes
2answers
537 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 ...
17
votes
1answer
159 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 ...
13
votes
2answers
1k 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 ...
12
votes
3answers
277 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
294 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 ...
11
votes
3answers
311 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$ ...
11
votes
1answer
5k 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 ...
11
votes
1answer
402 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 ...
11
votes
1answer
270 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
415 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 ...
10
votes
1answer
405 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
2answers
1k 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 ...
9
votes
1answer
207 views

Probability that multiple random walks are back at the origin

Consider a uniformly chosen random very long vector $A$ with $A_i \in \{-1,1\}$ and a uniformly chosen random vector $B$ of length $n$ (assume $n$ is even) with $B_j \in \{-1,1\}$. For a given $i$, ...
9
votes
0answers
123 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$: ...
8
votes
6answers
346 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
1answer
111 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
1answer
192 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
155 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 ...
7
votes
3answers
605 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$ ...
7
votes
1answer
675 views

Question about random walk with fixed endpoint, and a reference request

We have a random walk of length $n$, starting at $0$ and ending at $-6\,\sqrt{n}$. Can we give any sort of high probability bound on the number of steps before we first reach the value $-2\, ...
7
votes
1answer
92 views

Random walk on cubic lattice

Suppose at every point of the cubic grid in n dimensions is a particle, and at every timestep every particle moves at random to one of its 2n neighbours. As time goes to infinity, what is the ...
7
votes
1answer
152 views

Two people are looking for each other. Is it faster for both to actively search, or for one to search while the other stays still?

Choose among two actors randomly and place the chosen actor at the origin. Place the other actor in the unit circle uniformly at random. Both actors move at the same speed. Both actors are said to ...
7
votes
0answers
74 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) = ...
7
votes
0answers
277 views

Is there a connection between the 3D random walk constant and the partition function?

In thinking about this question, I took a look at Pólya's random walk constants and was struck by the fact that an expression for the constant for a three-dimensional random walk, ...
7
votes
1answer
170 views

Recurrence of a certain class of $2$-$d$ random walks

As is well known, a symmetric random walk on $\mathbb{Z}^d$ (the lattice of $d$ dimensional vectors with integer components) is recurrent if and only if $d=1,2$. In particular it is transient for ...
6
votes
1answer
70 views

A number-theoretic random walk on the integers

Suppose a random walker starts at $S_0 = 2$, and walks according to the following transition probabilities: If the walker is on the $n$th prime number $p_n$, she moves to either $p_n + 1$ or ...
6
votes
2answers
846 views

A question on calculating probabilities for the random walk

I am currently working on a high school project revolving around the 'Cliff Hanger Problem' taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller. The problem ...
6
votes
1answer
156 views

Colored path in a randomly colored grid

A friend of mine asked this question a while ago which I couldn't find any appropriate answer for it. I'd appreciate any comment or help. If one colors each unit square with black/white of an $m ...
6
votes
1answer
54 views

If I wanted to randomly find someone in an amusement park, would I be faster roaming around or standing still?

Assumptions: The other person is constantly and randomly roaming Foot traffic concentration is the same at all points of the park Field of vision is always the same and unobstructed Same walking ...
5
votes
2answers
151 views

How can we directly see that the number of random walks starting and ending at the origin is ${n\choose n/2}^2$?

In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step ...
5
votes
1answer
102 views

What's the easiest way to show that a random walk can go arbitrarily far?

Let's consider the simplest situation. On the one dimensional line of integers, and we starts from the origin. Each time we either move left or right (at the same probability) for 1 unit. How do I ...
5
votes
1answer
282 views

Asymptotic behavior for the return to zero of a simple random walk

I got stuck today trying to understand an argument of the Frank den Hollander Book's. The problem is described below. Let $S_n=\sum_{i=1}^n X_i$ be the simple random walk in $\mathbb{Z}^d$, that is ...
5
votes
1answer
2k views

Probability of a biased random walk hitting an absorbing barrier in some number of steps

Let's say I have a biased random walk over the integers in some interval [0, L] where the endpoints of the interval ('0' and 'L', respectively) are fully absorbing. The walker starts at some position ...
5
votes
1answer
198 views

Probability of random walk returning to 0

Given a symmetric 1-dimensional random walk starting at 0 -- what is the probability of the walk returning $k$ times to 0 after $2N$ steps? I know that the total number of paths it can take is ...
5
votes
1answer
1k 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" ...
5
votes
1answer
268 views

Walks of Even Length on a Bipartite Graph

Given a random walk on a simple $d$-regular bipartite graph $G$. The adjacency matrix $A'$ of $G$ may be split into blocks $$ A'=\pmatrix{ 0 &A^T\\ A&0 }, $$ The propagation operator $M=A'/d$ ...
5
votes
1answer
581 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 ...
5
votes
1answer
36 views

counting combinations of {+1, -1} with constraints

I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions: 1) the total has to sum to $N$ 2) no partial sum is ...
5
votes
1answer
111 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
5
votes
1answer
249 views

The random walk of two drunks

The problem is such: two drunks start at either end of an alleyway of length n. Apart from at the ends, they each move one step forwards or one step backwards randomly. At the ends of the alley they ...
5
votes
0answers
72 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
5
votes
0answers
166 views

Intuition for the optimality of bold play

There is a standard result (I think originally by Dubins and Savage) that if one wants to maximise the probability of winning a certain amount in an unfair game of chance then an optimal strategy is ...
5
votes
0answers
233 views

Where does directed random walk hit the boundary?

I have a problem that I more or less know the answer to, but would really like to see it done in a systematic, rather than ad hoc way. In spite of this, I will pose the question in a very concrete ...
4
votes
1answer
523 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?
4
votes
2answers
167 views

better expression for simple random walk

Let $P_{k,j}$ be the probability that a simple symmetric random walk starting from the origin reaches the point $k \in \mathbb{N}$ precisely in $j$ steps without ever returning to the origin. ...
4
votes
1answer
105 views

Expected time to get from bottom left to top right in a square

Consider a two dimensional random walk starting at the bottom left hand corner of an $n$ by $n$ square. At each step you take one step up, down, left or right distance $1$. Each choice has equal and ...
4
votes
1answer
340 views

Circular random walk

Suppose we have a circumference divided in N arcs of the same length. A particle can move on the circumference jumping from an arc to the adjacent, with probability $P_{k \to k-1}=P_{k\to ...
4
votes
1answer
64 views

A random walk question: what is the given probability?

Let $\{X_n\}_{n\in\Bbb N_0}$ be a simple random walk, given $n\in \Bbb N$ what is the probability $$ \mathbb P(X_1\ge0,X_2\ge0,\ldots, X_{2n-1}\ge0,X_{2n}=0) $$ I think that I should benefit from ...