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
1
vote
1 answer

Transience of the usual random walk on $\Bbb{Z}^3$ for non mathematicians.

The transience of the usual random walk on $\mathbb{Z}^3$ is a well known mathematical facts of which we know many proof, including using electrical networks, Fourier transform ... Those concepts while extremely useful are hard to communicate to…
Statistic Dean
  • 602
1
vote
1 answer

Modified Grid Walk

A man walks $n$ blocks north and $3n$ blocks east from his residence at $(0,0)$. How many routes are possible from his home to his office at $(3n, n)$ if he cannot walk two block north consecutively? It is obvious that the good paths are…
Puzzled123
  • 55
1
vote
0 answers

Further hint on solving Exercise 3.5 in First Steps in Random Walks by Klafter and Sokolov?

I'm working through First Steps in Random Walks by Klafter and Sokolov and I'm stuck at Exercise 3.5. The Question: Exercise 3.5. Show that the PDF of the particle's displacement in the ultra slow CTRW (Exercise 3.4) follows a two sided exponential…
sqg77
  • 11
1
vote
0 answers

Interpretation of the expected time of coming back to the origin for the random walk on ring.

When one move on a ring randomly, the expected time to coming back to the origin is equal to the perimeter according to this. At frist, the man is at the origin. For each second, he move left or right by 1 meter randomly. The perimeter of the ring…
ueir
  • 1,211
  • 5
  • 11
1
vote
1 answer

Enumerating 1-dimensional walks

I've invented a thought experiment for myself, which is defined below: A robot walks on a 1-dimensional number line, with stride length 1. In any instant, he may stay put (+0), walk left (-1), or walk right (+1). For $n$ movements of the robot,…
Benjamin Crawford Ctrl-Alt-Tut
  • 203
1
vote
0 answers

Kesten-Spitzer-Whitman Theorem - Recurrent random walk on $\mathbb{Z}$

Edit info : In the following we denote by "$1$" as the neutral of our group, hence "$1$"$=0$ for ($\mathbb{Z},+)$. A random walk on $\Gamma$ is an infinite sequence $X_0, X_1,\ldots$ of $\Gamma$−valued random variables, all defined on the same…
Thomas Lesgourgues
  • 4,685
1
vote
1 answer

Two-dimensional random walk, but with steps in $n$ directions (rather than just 4)

At each step, choose a (uniform) random number $i=1\ldots n$, and walk one unit (i.e., constant stepsize) in the direction $\theta=i\frac{2\pi}n$. Then $n=4$ reduces to the usual case, with steps parallel to the $x,y$-axes. And $n=2$ "collapses" to…
John Forkosh
  • 712
1
vote
0 answers

can we use random walk on disconnected graph?

Im stuck with the random walk. I tried to simulate the random on a graph but my graph consists of nbrVertex/2 components. So it is very sparse. 1- Does the random walk is suitable to such kind of graph? What should i want to add to get the random…
user2869180
  • 129
1
vote
0 answers

Signed process of simple symmetric random walk

$X_i$ be a simple symmetric random walk. $Y_i= \operatorname{sign}(X_i)$. Define $Z_n= \sum_{i=1}^{n} Yi$. What is an upper bound on $Var(Z_n)$? I feel the main issue is that $Y_i$ are not independent. Maybe there is some martingale hidden around…
pulpfictional
  • 481
1
vote
0 answers

First Step Analysis

Let (Sn)n∈N be a random walk process with increments that are independent. The value of the random walk increase by one in one time step with probability p and decrease by one in one time step with probability q = 1 − p. We denote the hitting time…
Brad
  • 11
1
vote
1 answer

For what range of $\beta$ is random walk heavy-tailed?

I have $\beta > 0$ and $S_0 = 0$, and $S_n = \varepsilon_1 + \cdots + \varepsilon_n, n \geq 1$, a random walk with i.i.d increments $\lbrace \varepsilon_n \rbrace$ having a common distribution $$ P(\varepsilon_1 = -1) = 1 - C_{\beta} \text{ and } P…
Jon Snow
  • 41
1
vote
1 answer

Expected time to reach final state for a random walk on a finite grid

I am not a mathematician, just a user of mathematics, so perhaps this is the wrong place to ask, but there is a problem I need some help with. You have a $n \times n$ grid, and you start at the $(1,1)$ square. You move randomly one square on the $x$…
user2345448
  • 21
  • 1
1
vote
1 answer

First hitting time distribution for a discrete random walk

Can anyone provide the first hitting time distribution for a discrete random walk? Edit: Specifically, a 1D random walk, starting at $k=0$. Each step moves either $-1$ or $+1$ without any boundaries. I require the distribution for the first hitting…
lemon
  • 3,548
1
vote
1 answer

Large deviation bound on 1-dimensional random walk

Let $X$ denote the distance from the origin of a $1$-dimensional unbiased random walk on $\mathbb{Z}$. Is there a reasonable bound on $P(X > t \sqrt{n})$ for some $t>1$? There are exact expressions for this, but they take the form of unwieldy…
vukov
  • 1,555
1
vote
0 answers

Random walk on a non-(hyper)cubic lattice

(In what follows, "cubic lattice" is short for "simple cubic lattice") In this book, chapter 12, the following expression is derived for the probability distribution of a random walk on a $D-$dimensional cubic lattice (hypercubic…
valerio
  • 881
1 2 3
4
5 6 7