Tagged Questions
20
votes
2answers
375 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 ...
16
votes
0answers
319 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:
$$
...
12
votes
3answers
264 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 ...
10
votes
1answer
277 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 ...
8
votes
1answer
150 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
256 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
1answer
139 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
1answer
383 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\, ...
6
votes
3answers
535 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 ...
6
votes
2answers
311 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 ...
5
votes
1answer
92 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
1k 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 ...
4
votes
1answer
262 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
168 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
...
4
votes
1answer
110 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 ...
