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

learn more… | top users | synonyms

4
votes
1answer
929 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
218 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
896 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
102 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 ...
9
votes
2answers
784 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
209 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
338 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
223 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
192 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
308 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
264 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
192 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 ...
8
votes
1answer
3k 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
378 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 ...
0
votes
0answers
119 views

Nonexistence of invariant probability with respect to random walk

We have a random walk process $X_{k+1} = X_{k} + Y_{k}$, where $Y_k$ are independent random values with the same distribution, $X_{0}$ have some fixed distribution $\pi$. Let $P^{k,s}(x,B)$ be a ...
3
votes
0answers
64 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
616 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
170 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 ...
6
votes
0answers
267 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
349 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
281 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
273 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
333 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
117 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
169 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
174 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
71 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
97 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 ...
1
vote
1answer
62 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
639 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
691 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
129 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 ...
1
vote
2answers
765 views

What are some martingales for asymmetric random walks?

Here are some examples for symmetric ones: http://mathoverflow.net/questions/55092/martingales-in-both-discrete-and-continuous-setting/55101#55101 Is there a similar list for asymmmetric random ...
4
votes
1answer
376 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?
3
votes
1answer
310 views

Expectation of absorption time for a random walk which remains at n with probability 1/2

A random walk moves from k to k+1 with probability 1/2 and to k-1 with probability 1/2, except when k=n, in which case it remains at n with probability 1/2 and moves to n-1 with probability 1/2. ...
3
votes
1answer
220 views

Solving a maze by taking a random walk

I vaguely recall a result like the following from one of my complexity theory classes in school: given a 2d maze (which I guess we can think of as a directed graph with a fixed start node and exit ...
5
votes
1answer
237 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 ...
0
votes
1answer
39 views

Cardinals arising from random walks in the limit

A random walk $X$ is a sequence of elements of the set $\{-1, 0, 1\}$ and $X_i$ denotes the $i^{th}$ element of $X$. Consider the set $C_n$ of all random walks of length $n$ and the set $C_\infty = ...
1
vote
0answers
526 views

Help needed solving for bounded random walk expectation; problem involves strange (to me) Factorial/Gamma-function summation

Posted this at math overflow, but they redirected me here. I'm currently trying to solve for the expectation of a bounded Gaussian random walk. That is to say, each step is a random variable with ...
8
votes
2answers
836 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 ...
7
votes
1answer
507 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\, ...
2
votes
1answer
235 views

considering the minimum in random walk

Grimmett and Stirzaker's "Probability and Random Processes" gives a nice discussion about random walk, for example, it considers $M_n=\max\{S_i,0\le i \le n\}$ where as usual ...
2
votes
1answer
96 views

$1$D bidirectional random walk question

In a $1$D random walk on x axis a particle can turn left with probability $\frac{3}{4}$ and right with probability $\frac{1}{4}$. What is the probability that $|x|\leq 1 $ for $1\leq ...
5
votes
1answer
2k 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 ...
2
votes
1answer
449 views

Hitting time for a random walk where step probabilities linearly depend on the distance to an absorbing wall

Consider the case where I have a discrete random walk on the integers over an interval $[0, M]$, where I start at some position $0 < k < M$, and both endpoints (i.e. $0$ and $M$) are fully ...
1
vote
1answer
190 views

analogy to ruin problem against infinitely rich adversary

I realized that an earlier question I'd posted was actually different than what I was actually asking. My question is: say we have a game where you win 2 dollars, or lose 1 dollar, both with ...
3
votes
1answer
217 views

Random Walk - If $m$ is odd, probability of no equalization in the last $m$ steps in path of length $2m$ is 1/2

I am trying to solve the problems in the Chapter 12 Random Walks of Introduction to Probability by Grinstead and Snell. I am stuck at Problem 6(b) which I quote below (page 482) Problem 6 (a) Show ...
3
votes
1answer
371 views

Random walk $< 0$

Suppose ${X_t}$ is a random walk with mean zero. (either discrete or continuous time) Fix a time $T$. What is: $P[X_t < 0 \text{ for all } t \leq T]$? In words, what's the probability the random ...
3
votes
1answer
320 views

Analysis of a biased random walk related to median finding

Imagine a process with two variables min and max, and two counters hi and lo. We initialize min and max by selecting two random numbers (assume a uniform (0,1) distribution for convenience), and ...