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

learn more… | top users | synonyms

34
votes
1answer
996 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: $$ ...
22
votes
2answers
453 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
135 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 ...
12
votes
3answers
274 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
253 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
1answer
347 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 ...
9
votes
2answers
769 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 following ...
9
votes
3answers
347 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 ...
9
votes
1answer
341 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 ...
8
votes
3answers
811 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 ...
8
votes
1answer
3k 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 ...
8
votes
1answer
177 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
149 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
6answers
315 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 ...
7
votes
1answer
500 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
138 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 ...
6
votes
2answers
523 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
0answers
123 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
0answers
265 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, ...
5
votes
2answers
110 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
98 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
233 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
97 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
81 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 ...
5
votes
1answer
245 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
375 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
176 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
137 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
207 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
374 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
1answer
247 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
336 views

Covariance of Brownian-motion-like processes

We know that $\operatorname{Cov}(B_s,B_t)=\min(s,t)$ if $B_t$ is Brownian motion. What is $\operatorname{Cov}(B_{f(s)},B_{f(t)})$ for some injective $f$? How can I write $B_{f(t)}$ in an Ito ...
4
votes
1answer
94 views

Drunk problem involving probability of being in a circle.

This is the typical drunk problem wherein the person is confined to moving either to the North, South, East, or West but never diagonally with just one step. A step has a length $L$. What is the ...
4
votes
1answer
77 views

random walk in a certain environment

Consider the following random walk in one dimension, starting from $r(0)=0$. $$ r(i+1) = r(i) + \xi, $$ where $\xi(i, r(i))$ is an increment with distribution $P(\xi=1) = \frac{c^{r(i)}}{i-r(i)+1}$ ...
4
votes
1answer
400 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 ...
4
votes
2answers
392 views

Random walk on lollipop graph

Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
4
votes
1answer
125 views

Chance of being able to quit while ahead in a betting game (Markov chain with gambler's ruin)

Suppose a player starts with $N$ chips, and is playing a game with odds $O$, betting 1 chip in each iteration. When the player reaches 0 chips the betting must end. What is the probability that at ...
4
votes
1answer
170 views

Biased lower bounded random walk

I have a random walk with the following rules: It starts at 2 At each step it goes up by 1 with chance .4, down by one with chance .4 and up by 2 with chance .2 The walk ends if it reaches 0 I ...
4
votes
1answer
86 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 ...
4
votes
1answer
185 views

Random walk on $\mathbb{Z}^d$

Problem Let $\{X_n\}_{n=0}^{\infty}$ be a random walk on $\mathbb{Z}^d$ such that; $X_0=(0,0,\cdots,0)$ and $\{X_n-X_{n-1}\}_{n=1}^{\infty}$ are mutually independent, identitically distributed ...
4
votes
2answers
117 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
4
votes
1answer
881 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" ...
4
votes
2answers
112 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
4
votes
1answer
186 views

Random Walk on Z

Let $S_n$ be the symmetric random walk on $\mathbb{Z}$. How do i calculate $P(\limsup_{n\rightarrow\infty} S_n=\infty)$? I already know that the probability is 1 but I don't really know how to start? ...
4
votes
1answer
175 views

The probability of a “double supremum” of random variable

Let $X_1,X_2,X_3,\ldots$ be IID r.v. with \begin{equation} P(X_i<-1)=0 \end{equation} \begin{equation} P(X_i<0)>0 \end{equation} \begin{equation} P(X_i>0)>0. \end{equation} Define ...
4
votes
0answers
62 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let ...
4
votes
0answers
210 views

Random walk on $\mathbb{Z}$ with more than two possible steps

Let be $\{X_n\}_{n\in \mathbb{N}}$ random walk on $\mathbb{Z}$. Let be $$P(X_{n+1} = k + a| X_n = k)= p_a$$ for $a\in \mathcal{A} \subset \mathbb{Z}$. Let say that $X_0 = 0$. I am interested in ...
4
votes
0answers
62 views

random walk on real line

Suppose I start at $A>0$ and every period I either move a distance $B$ to the right with probability $p$ or a distance $C$ to the left with probability $1-p$. The expected move is positive: ...
4
votes
2answers
145 views

Speculating on the stock exchange

Imagine you model each stock as a random walk (fractal) and also that you can buy and sell at any price. Suppose also that it 'walks' with the pace of 1. If you buy, for example, 1000 shares of ...