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
772 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
94 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
200 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
334 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
166 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
227 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
240 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
144 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
108 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
328 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
401 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
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
71 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
78 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
49 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
73 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
110 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
176 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 ...
5
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
253 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
1k 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
109 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
283 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
411 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
245 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
247 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
341 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
306 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 ...
1
vote
0answers
211 views

Non-uniform random walk

I'm searching a solution for this problem: Given a segment of length $L$, from $0$ to $L$ divided in $N$ subsegments of the same length, a particle, starting from the subsegment in $x_k$ has a ...
10
votes
1answer
5k 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 ...
2
votes
1answer
443 views

Biased random walks in 2d

I'm looking at a random walk on a square lattice with a bias toward the origin. Any step away from the origin occurs with probability a probability p, which is less than the unbiased value of 1/4. I'd ...
3
votes
0answers
70 views

Diffusion on a graph and its dual

Is there a relation between the diffusion of a random walker on a planar graph and that on the dual of the graph? It seems perhaps intuitive that if the diffusion on the graph is slow (in comparison ...
3
votes
2answers
725 views

Random walk probability/expected value

With what probability, starting at node $g$, does node $d$ get hit before node $e$ in the graph below? What is the expected value of number of steps you need to hit $\{d,e\}$ (at least one of them) ...
4
votes
1answer
192 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 ...
7
votes
0answers
276 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, ...
11
votes
1answer
391 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 ...
2
votes
2answers
397 views

What does it mean for MCMC to converge?

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will ...
2
votes
2answers
347 views

Are probabilities proportional to the distance traveled in a random walk? What if the initial position is a bit biased?

A marker is placed at zero on the number line and a fair coin is flipped. On each flip we move one unit to the right. If it lands on heads, the marker is moved one unit up. If it lands on tails, the ...
0
votes
1answer
408 views

Probability mass function of a random walk process

Let $Y_n$ be a random walk process defined as $Y_n = Y_{n-1} + X_n$; $n = 1,2\ldots$ and $Y_0 = 0$, where $X_k = +1$ with probability $p$ and $-1$ with probability $1-p$. Write down the pmf for $Y_n$, ...
2
votes
1answer
127 views

1D random walk with infinite crossings

Let $x_i$ be a uniformly random real in $(-1,1)$. And let $f(x)$ be a strictly increasing positive and unbounded function. Let $S_j(f)=x_0/f(0)+x_1/f(1)+x_2/f(2)+\cdots+x_j/f(j)$ Does $S_j(f)$ ...
0
votes
2answers
176 views

Question from section 1.5 of Chung's Spectral Graph Theory

I'm (slowly) reading Fan Chung's Spectral Graph Theory. At the moment, I'm in section 1.5 which is about eigenvalues and random walks. There's a small technical point that puzzles me. The context ...
1
vote
1answer
196 views

Returning Paths on Cubic Graphs

Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin? Or putting it differently: What is "Pólya's Random Walk Constant" on ...
1
vote
1answer
72 views

Degree of girraphs

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent. The random walk on the square grid returns to the origin with probability 1, and for the cubic grid ...
2
votes
1answer
108 views

Restricted random walk in $\mathbb Z^3$

What is the proability to return to the origin, for a uniform random walk on the integer lattice in $\mathbb Z^3$, if we are restricted to $x \geq 0$? I.e. if we try to step into a negative ...
2
votes
1answer
70 views

What is the lowest dimension $d$ for which the simple random walk on $\mathbb Z^d$ is transient?

By "transient" I think they mean that the probability of returning to the initial point is $<1$.
1
vote
2answers
780 views

Expectation of Random Walk

At each time step, I have 1/2 probability of walking one step to the right, and the same probability of walking one step to the left. Let X be the random variable corresponding to the final ...
3
votes
2answers
969 views

Definition: transient random walk

What exactly does a "transient random walk on a graph/binary tree" mean? Does it mean that we never return to the origin (assuming there is one as for the tree) or just any vertex of the graph or ...
2
votes
1answer
148 views

Expectation of $T^2$ where $T$ is the absorption time at ${a,−a}$ of a simple random walk $\{S_n\}$

I asked a very similar question before: Expectation of $TS_T$ where $T$ is the absorption time at $\{a,-a\}$ of a simple symmetric random walk $\{S_n\}$ But this time I have an ASYMMETRIC random ...