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

learn more… | top users | synonyms

0
votes
1answer
2k views

Probability distribution of a Hitting Time in simple random walk

In order to solve a puzzle in correspondence with a friend, I am using a simple random walk hitting time calculation based upon the reflection principle as it is expressed in this University of ...
2
votes
0answers
107 views

Equilibrium distributions for a finite urn scheme

Given an urn with $n$ (fixed) balls that can be red or black, and given two parameters $0 < p, \, q < 1$, keep doing the following: Flip a $p$-coin. If heads come up, remove a black ball or ...
1
vote
2answers
290 views

A question about random walk in 1 dimension

For a simple random walk problem in 1 D, the expected position of the particle in $n$ step is $E(X_n)=n(p-q)$ so the distance from origin should be $=E(X_n)$ but according to Mean distance from ...
0
votes
1answer
200 views

Recurrent, strongly aperiodic random walk

Assume $(X_n)_{n\geq1} \subseteq \mathbb {Z}$ and $(Y_n)_{n\geq 1} \subseteq \mathbb {Z}$ to be iid, $X_i \sim Y_i$ and such that $S_n=\sum_{i=1}^n(X_i-Y_i)$ is a strongly aperiodic, recurrent random ...
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 ...
1
vote
1answer
67 views

Absorbing time in $0$ of a simple left-drifted Markov chain on non-negative integers

Let $M$ denote the Markov chain on states $\{0, 1, 2, ...\}$ with absorbing state $0$. For $i \geq 1$, let the transition probabilities be $p$ for $(i, i-1)$ and $1-p$ for $(i, i+1)$. Further, assume ...
1
vote
1answer
35 views

Off-lattice Brownian bridges in R^3

Start at a point $(0,0,z_0)$ and take $n$ steps of unit length in a random direction (for each step) in $\mathbb{R}^3$. Let such a walk be valid if the position of the last step, and only the last ...
3
votes
2answers
184 views

Mixing time for a random walk on an interval

I take a random walk on a bounded one-dimensional interval of length $N$, with possible walker positions $1$ through $N$. If I start at position $1$, how many steps should it take before my walker is ...
0
votes
2answers
300 views

How to check that a sequence of numbers is random? [duplicate]

I have a sequence of numbers like 1,7,22,45,12,96,21,45,65,36,85,14,51,16,18,17,16....65... IS there any formula to check whether the sequence is random or not ? In my case odd numbers are ...
0
votes
0answers
40 views

Find for a given distribution a random walk

Let $\{Z_i\}$ be i.i.d. $\mathbb{R}^d$ valued random variables. Then we define $S_n:=\sum_{i=1}^n Z_i$ and call the process $\{ S_n\}$ random walk on $\mathbb{R^d}$. Let $\mu$ be a distribution on ...
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 ...
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 ...
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 ...
2
votes
0answers
131 views

Repeated reflection

This is a problem from Feller's book introduction to probability theory and its application, Vol 1, Chap 3 problem 3. Let $a$ and $b$ be positive, and $-b <c<a$. Prove the number of paths to ...
0
votes
3answers
176 views

Probability of landing on a particular point in an infinite 1D random walk

$50\%$ of the time you walk right one unit, and $n$ units to the left o.w. The probability in question is ever landing one unit to the right of where you start at (as your number of moves goes to ...
1
vote
0answers
90 views

Martingale with reflecting barrier

I am not very familiar with the theory of martingales or random walks, perhaps someone could point me in the right direction or give me some help with the following problem. Consider a random ...
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 ...
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 ...
0
votes
1answer
391 views

Why is a random walk a time-homogeneous Markov process?

Why is a random walk on $\mathbb{R}^d$ (see below) a time-homogeneous Markov process? Specifically, why does it satisfy requirement #2 of definition 17.3 that the map ...
2
votes
1answer
601 views

Random Walk Expected Number of Visits

I'm having a bit of trouble with a question involving a random walk with five vertices. The graph is shown below. The problem I can't figure out reads: Suppose a walker starts in vertex C. What ...
3
votes
2answers
293 views

Boundary conditions on asymmetric random walk recursion formula

A random walker moves at each step two units to the right or one unit to the left, with corresponding probabilities $p$ and $q = 1-p$. The allowed range is $[-A, B]$ and the starting position is $0$. ...
6
votes
2answers
844 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 ...
2
votes
1answer
255 views

Random walk on finite graph

I know that the stationary distribution of a random walk on the graph is given by, (degree of the node)/($2\times$ total number of links in graph). My question is, how do we get this solution?
3
votes
2answers
330 views

Drunk person walking in 1D desert

Given $f(x)$, a strictly positive monotonically decreasing sequence, converging to 0. How to check whether a one dimensional random walk with stepsize $f(n)$ in random direction at the $n$-th step, ...
2
votes
2answers
429 views

one-dimensional random walk

Consider a one-dimensional random walk whose steps are $+2$ and $-1$ with probabilities $p$ and $1-p$ respectively, starting from $0$ and in the interval {$-n$, $n$}. The walk ends at $-n$ or $n$ or ...
3
votes
2answers
273 views

Random walk and its expectation

Let $S_n=X_1+X_2+...+X_n$, where $X_i=1$ with probability $p$ and $X_i=-1$ with probability $q=1-p$, for all $i$ and independently of each other. Assume that $S_0=0$ and $0<p<\frac{1}{2}$. ...
2
votes
3answers
177 views

Derivation of Wiener process first passage times using probability generating function?

I would like to find the distribution of first passage times in a simple Wiener process using the idea of probability generating functions. Thus there will be, at certain point, a limiting step to go ...
4
votes
1answer
191 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 ...
2
votes
0answers
310 views

Probability distribution of a self avoiding walk

Preliminary: Consider a walk on the lattice $\mathbb{Z}_d$ lattice of length $N$. In a normal random walk, if we let $N$ get large the end position has a probability distribution (PDF) that looks ...
1
vote
1answer
178 views

Wiener process question

When I look up the definition of 'Wiener process' at Wikipedia, it tells me: $W(0) = 0$ and $W(t) - W(s) \sim N(0, t-s)$. When I try to simulate this in matlab, I get different results when I define ...
3
votes
1answer
108 views

what is the behaviour of moving dot with 50% chance to go left or right?

If a dot is moving (from zero) left or right, by one, with 50% chance to go left or right - is it going to go to the +inf or -inf when it has infinite moves?
3
votes
1answer
146 views

A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$ T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0 $$ Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
0
votes
1answer
806 views

Stopping time and random walk: Proof that Stopping time of reaching a certain value is finite a.s. [duplicate]

Possible Duplicate: Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1 This is a basic question but I was wondering if there was a simple proof (I ...
0
votes
1answer
96 views

A random walk on $\mathbb{Z}$ with a twist

I am trying to decide whether the following random walk is recurrent or not. Intuitively, I think it is - but I am not familiar with techniques of proving it. My random walk is the following: on each ...
1
vote
1answer
202 views

Variation of a simple random walk

Consider the following problem. A particle takes discrete steps $\sigma_1, \sigma_2, \sigma_3, \ldots, \sigma_n$ which take on values $+1$ or $-1$. However, $P(\sigma_i = +1) = p$ if $i$ is odd and ...
4
votes
1answer
339 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 ...
0
votes
1answer
172 views

A problem about the expectation of maximum rise up for a random walk.

Give such a random walk moving on the x-axis: Start from $x_0=0$; After the $i^{th}$ step, the location is $x_i$. The length for the $i^{th}$ step $x_i-x_{i-1}$ is a uniformly generated real number ...
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 ...
2
votes
1answer
254 views

Biased alternating random walk on a lattice in 1D

Let's consider a random walk on a fixed lattice with step size 1 in 1 dimensions. In variation to the broadly discussed basic case, with a probability p the next step will be in the opposite direction ...
2
votes
1answer
147 views

A problem about symmetric random walk

Consider a symmetric random walk $P(X_i=1)=P(X_i=-1)=1/2$, $S_0=0$, $T_a=\min(n:S_n=a)$ We already know that $P(T_a>T_{-b})=1-P(T_{-b}< T_a)=\frac{b}{a+b}$ and $E(\min\{T_a,T_{-b}\})=ab$. ...
4
votes
0answers
110 views

Completeness of random walks in multiple dimensions?

I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
3
votes
3answers
3k views

biased random walk on 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. ...
0
votes
1answer
337 views

Random walk on infinite line - can it be stationary?

Suppose a random walk on an infinite line $[...-3,-2,-1,0,1,2,3,...]$, starting from 0. Probability to go right or left are equal. Does such a process stationary? I think that it is NOT, since the ...
2
votes
1answer
408 views

Non-symmetric simple random walk stopping time

Say there is a random walk $\{S_n\}$ with $S_0=0$ and $0<p=P(S_1=1)<\frac{1}{2}$. We know such a random walk would go to $-\infty$ eventually. Define the stopping time $T=\inf\{n: S_n=-\infty\}$, ...
3
votes
2answers
211 views

Exponential ergodicity of biased random walk confined to the positive integer quadrant

I am looking at a discrete-time random walk on $(\mathbb{Z}^{+})^n$, where $\mathbb{Z}^{+}:=\{0,1,2,\dots\}$ and $n\in\mathbb{N}$. At any time, the random walk chooses a uniformly random co-ordinate ...
1
vote
2answers
191 views

Is this random walk well studied?

Suppose that we have an ergodic finite Markov chain $C$ with a fintie state space $S$, and we have random variables $X_s$ where $s\in S$. Consider the following random walk $S_0=0$ and $S_{i+1}=S_i ...
2
votes
1answer
72 views

Is there an unbiased random walk on a colored plane for any number of colors?

So I was trying to motivate the fundamental postulate of statistical mechanics (i.e. all microstates are assumed to be equally probable $-$ even if we can't practically measure them, but only their ...
1
vote
2answers
81 views

Random Walker Problem - Help Needed

I need some help solving this problem. A man is about to perform a random walk. He is standing a distance of 100 units from a wall. In his pocket, he has 10 playing cards: 5 red and 5 black. He ...
1
vote
1answer
50 views

question on graphs and expected steps

So we have an undirected graph with vertices labeled 0,1...n. We start at 1 and we can go either left or right . We want to know the # of steps expected to get to 0. I figured that half the time you ...
2
votes
1answer
75 views

random walks question

The probability that a simple random walker is at 0 after $2n$ steps is $P(S_{2n}=0)=\binom{2n}{n}2^{-2n}$. What is the probability that a random walker is at integer $2j$? Well, I understand ...