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

learn more… | top users | synonyms

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
160 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
80 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
476 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
340 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
439 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
274 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
620 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
220 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
298 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
367 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
260 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
113 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
183 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
239 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
158 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
140 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
576 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
92 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
185 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
274 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
160 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
166 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
213 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
201 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
131 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
253 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
352 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
108 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" ...
1
vote
2answers
226 views

Random walk with reset?

Is there such a random walk, that "good times" it just looks like a random walk, while when "bad moment" comes, it will reset => jump to zero, afterwards continue doing random walk again? Thanks!
1
vote
3answers
966 views

Random walk problem

Two drunks start together at the origin at $t=0$ and every second they move with equal probability either to the right or to the left, each drunk independently from the other. What is the probability ...
0
votes
1answer
106 views

Random walk and powers of 2

I'm in trouble on the following problem: given a random walk starting at point N on the integer number line, how many steps should I wait before the walk hits a power of two at least once, with ...
12
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 following ...
3
votes
1answer
224 views

understanding a proof of the hitting time theorem for a right-continuous random walk using generating functions

This is particularly directed at those who have Grimmett & Stirzaker, Probability and random processes (2005), at hand. It pertains to the proof step prior to equation (10), p. 166. For others: ...
1
vote
1answer
370 views

Random (drunkard) walk distance after $n$ steps

I am tying to analyze a random walk on an integer lattice $\mathbb{Z}^k$. For $k=1$, what is the probability that after $n$ steps the drunkard's distance from the origin is lower than $\sqrt{n}$?
1
vote
0answers
229 views

Random walk with increasing step size

A random walk in the plane with step size $f(n)$ is cool if there is some constant $C$ such that it returns within a distance $C$ of the origin infinitely many times with probability $1$. At the ...
1
vote
1answer
215 views

Ergodic process and random walk

Is a gaussian random walk process an ergodic process? If Yes, does someone knows the proof? Thanks in advance
3
votes
2answers
316 views

Expected value of function of random walk

I am trying to calculate $\lim_{n \to \infty} {E[e^{i \theta \frac{S_n}{n}}]}$. Where $\theta \in \mathbb{R}$, and $S_n$ is simple random walk. I could simplify it to $\lim_{n \to \infty}E[\cos(\theta ...
0
votes
2answers
275 views

Gambler's Ruin with varying probabilities

Consider a random walk $X_j$ on $\mathbf{Z}$ that starts at $X_0 = k \in \{1, 2, \dots, N-1\}$. Let $T$ be the random time defined by $T = \min \{j | X_j \in \{0,N\}\}$ . Then if ...