Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [random-walk]

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

A random walk is a type of stochastic process with random increments, and it is usually indexed by a continuous time variable or an equally spaced discrete time variable.

An elementary example of a random walk is the random walk on $\mathbb{N}_0$, which starts at $0$ and at each step moves $+1$ or $−1$ with equal probability. The path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be approximated by random walk models, even though they may not be truly random in reality.

2425 questions
2
votes
2 answers

Random Walk, Reflection Principle Question

Let $$S_n^* = \max_{1\leq m \leq n}S_m$$ $S_0 = 0$. Assume that $n$ and $a$ are even positive integers, $b$ is an even integer $b\leq a$, $a \leq n$, $ 2a - b \leq n$. Prove that $P(S_n^*\geq a, S_n=b)=P(S_n=2a-b)={n\choose ({n+b})/2-a}(1/2)^n$ 2)…
Raveesh
  • 135
2
votes
0 answers

Expected $\ell_1$ distance in $2D$ random walk

Suppose we have a random walk starting at the origin on $\mathbb{Z}_2$. Let $X$ denote the $\ell_1$ distance from the origin (i.e. $\vert x \vert + \vert y \vert$, where $(x,y)$ is the position of the walk). What is $\mathbb{E}X$? I'm sure this is…
vukov
  • 1,555
2
votes
1 answer

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$. Prove: $$E(T_a \times 1\{T_a<…
Bonnie
  • 43
2
votes
1 answer

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 like to know the average amount of time it would…
Matthew Matic
  • 457
1
vote
1 answer

SSRW hits *every* integer infinitely many times almost surely?

Consider the simple symmetric random walk (SSRW) on the 1D integer lattice. If we take any finite set of integers, say, $\{-N,-N+1,\ldots,N-1,N\}$, then, with probability one, it hits every integer in this set infinitely many times. But can we say…
jdods
  • 6,248
1
vote
0 answers

Number of visits of Wilson's algorithm may depend on the root but not on the labelling once a root is fixed

Let consider a finite graph $G$ with a fixed root $v_0$. Let $v_1,\ldots,v_n$ be a labelling of the vertices of $G$. Suppose we apply Wilson's algorithm following the labbelling $v_1,\ldots, v_n$ and sample the LERW by sampling SRW and erasing their…
3m0o
  • 783
1
vote
1 answer

Prove inequallity of number of steps in a simple random walk

Let $S_n$ be a simple random walk on $\mathbb{Z}$, starting from 0, and let $c>0$ be an integer. Show that $$ \mathbb{P}\left(\underset{1\leq j\leq n}{\max}|S_{j}|\geq c\right)\leq2\mathbb{P}\left(|S_{n}|\geq c\right) $$ I am struggling with this…
DirichletIsaPartyPooper
  • 609
1
vote
0 answers

choices between random walks

I just wonder if there is any model about the optimal path of multiple random walks. To be more specific, consider a decision maker with initial state $X_0=0$. The decision maker wants to hit either $X=-5$ or $X=15$ as fast as possible. He can…
Ilovetea
  • 31
1
vote
0 answers

Help on Metropolis-within-Gibbs (MCMC) on Bayesian variable selection (spike-and-slab prior) (random-walk Metropolis-Hastings)

There is a Bayesian linear model $Y$~$N\left(\beta_0\mathbf{1}+X\beta,\sigma^2I\right)$, and the setting for spike-and-slab prior is as follows: $\left.\beta_i\ \right|\ \gamma_i,\tau_i,\phi_i\ $~$\ \left(\gamma_i\right)\bullet Normal\left(0,\…
박정승
  • 11
1
vote
0 answers

Expected return time of random walk.

I'm currently reading Lovasz's survey on random walks. He claims without proof in Proposition 2.3 that the expected time taken for a simple random walk starting at a vertex $u$ to return to $u$ is equal to $2m/d_u$, where $m$ is the number of edges…
Emil Sinclair
  • 769
1
vote
0 answers

For a random walk in 3d with average step size a, what is the probability that a path of length L encloses a tube of radius R?

These sort of questions pop up regularly in the research of a colleague at work. He studies long polymer chains of length $L$ and carbon-carbon length $a$ that are in a liquid. What is the probability that such a polymer will go round a tube of…
KlausK
  • 131
1
vote
0 answers

Reaching time for a non symetric random walk.

Let $Y_1,..,Y_n$ random variables i.i.d. with $\mathbb{P}[Y_1=1]=p$ and $\mathbb{P}[Y_1=-1]=q$ and $Y_0=0$, consider the random walk $X_n=\sum_{i=0}^nY_i$ and the stopping time \begin{equation} \tau=\inf\{n\in\mathbb{N}| X_n=-a\,\,or\,\,…
Don P.
  • 313
1
vote
1 answer

3D random walk with complex phase

I'm trying to understand the properties of 3D random walks, but with an overall complex phase at each step (the phase is drawn from a uniform distribution between 0 and 2*pi). To be concrete and simplify things, I want to perform a random walk with…
quenderin
  • 43
1
vote
0 answers

Random Walk Exceeding Some Threshold

Let $Y_i = i$ w.p $1/2$ and $Y_i = -i$ w.p $1/2$. Define a martingale such that $T_n = \sum_{i}^{n}Y_i$ and let N be a stopping time where $min\{n| k \leq T_n\}$. Clearly $N$ is a defective stopping time due to zero mean expectation nature of the…
eet
  • 393
1
vote
0 answers

2D random walk crossing problem

On internet I have read multiple times that if you have a 2D random walk and the walk continous for some large amount of step, the probability is almost 1 that our walk will cross the starting point. What is the argument for that? I tried to look up…
kia1996
  • 21
1 2
3
4 5 6 7