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
165 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 ...
9
votes
1answer
367 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
65 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 ...
2
votes
2answers
145 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
272 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
39 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
99 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
153 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
180 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
116 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
163 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 ...
0
votes
0answers
81 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 ...
22
votes
2answers
483 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
275 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
348 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
451 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
278 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
653 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
223 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
303 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
376 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
262 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
116 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
184 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
246 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
159 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
107 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
142 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
623 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
93 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
187 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
281 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
162 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 ...
0
votes
0answers
167 views

Expectation of the maximum consecutive subsequence sum of a random sequence

There is a problem from Programming Pearls 2nd edition (Problem 4 in Chapter 8.7): If the input elements in the input array are random real numbers chosen uniformly from [-1,1], what is the ...
5
votes
0answers
216 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
219 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
132 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
89 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 ...
2
votes
3answers
2k 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
261 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
361 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\}$, ...
1
vote
2answers
188 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
67 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
75 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
47 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
70 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 ...
1
vote
1answer
109 views

The probability of a discrete-time random process ever incurring a certain drop from “peak to bottom”

Background. Let $Y_1,Y_2,\ldots$ be i.i.d. random variables such that $$P(Y_i<-1) = 0,$$ $$P(Y_i<0) > 0,\quad P(Y_i>0)>0,$$ $$E[Y_i] = \mu > 0\qquad \text{($\mu$ is finite)}.$$ Now ...
1
vote
0answers
163 views

Random walk in a sphere

Given a sphere of radius $R$, divided in cubic cells of size $l$, the probability for a particle to jump from a cube to another adiacent is: $P=\frac{1}{6}$. If we define the probability to exit from ...
4
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" ...