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

learn more… | top users | synonyms

1
vote
0answers
15 views

Standard deviation of absolute distance of a 1D random walk

Given a 1D random walk (simple +1, -1 movements from the axis) I've seen proofs that the expected absolute distance tends to Sqrt(2*n/PI) and I've plotted graphs of 1D random walks along with this ...
0
votes
1answer
15 views

Boundary conditions for random walk

Consider a simple asymmetric random walk $S_n$ which goes up with probability $p$ and down with $1-p$. For $b<x<a$ let $$r(x) = P( S_n\text{ hits }a \text{ before }b |S_0 = x). $$ This ...
1
vote
0answers
25 views

Limit of a random walk

Suppose we have a simple random walk: $X_n\pm1$ with equal probabilities. For any finite $n$, $E[\sum_{k=1}^nX_k]=0$. Does it imply that $E[\lim_{n\rightarrow \infty}\sum_{k=1}^nX_k]=0?$ Thank's! ...
0
votes
1answer
12 views

Simple random walk in the limit

Consider simple random walk: $X_n=\pm1$ with equal probabilities. $S_n =\sum_{i=1}^nX_i$. For finite $n$ we can write $$S_n=\sum_{i=1}^nX_i=\sum_{i=1}^nX_i^+ -\sum_{i=1}^nX_i^-$$ So that ...
1
vote
1answer
31 views

Expected number of returns to zero in a symmetric random walk - closed form

The expected number of returns of a symmetric random walk is given by $\sum_{k=0}^n \binom{2k}{k} / 2^{2k} -1$ The exercise is to compute an explicit form for this. I tried to do this in the ...
1
vote
2answers
20 views

Symmetric Random walk on $\mathbb {Z}^d$

Consider the symmetric random walk on $\mathbb{Z}^d $. Symmetric means that the probability of going into any of the $2^d$ directions is $1/2^d$. Starting in 0, what is the probability of ...
0
votes
1answer
19 views

Random walk on $\mathbb{Z}$ (probability to be again in the starting point after n steps)

Consider the random walk on $\mathbb{Z}$, where the probability of going one step to the right from any given state shall be $p\in (0,1)$. Starting in 0, what is the probability of returning ...
0
votes
0answers
38 views

Random walks: number of crosses between $-\sqrt{x}$ and $\sqrt{x}$

Let $S_n = \sum_{k=1}^n X_i$ be a simple random walk, where $X_1, X_2, \dots$ are independent Bernoulli random variables, $\mathbb{P}(X_k = 1) = \mathbb{P}(X_k = -1) = \frac 1 2$. Let $T_1 = 1, ...
1
vote
0answers
17 views

Random Walk and strong law

I want to prove that a Random Walk in 1 dimension is transient when $p\neq\frac{1}{2}$ but i want to prove it by the strong law of large numbers, so i have this: Define a random variable $$X_i = ...
0
votes
2answers
32 views

About random walk 1D

I just don't understand why is betha expressed in this way. I don't understand the "conditioning on the initial transition" . Hope you help me thanks
0
votes
1answer
22 views

Probability of a Brownian Motion to fall in a bandwidth

Let $X_t$ be defined as $$ X_t = X_0+\int_0^t\sigma_{0}\,dW_s, $$ where $W_s$ is a Wiener process and $\sigma_0\in\mathbb{R}^{+}/{0}$. Which is the probability $$ ...
0
votes
1answer
17 views

Is there a name for the following random process?

I have a random process which seems to oscillate between extremes in terms of trending but which is locally like a Brownian motion or a fractional Brownian motion. Is there a name for such a ...
0
votes
1answer
21 views

What is the meaning $P[\frac{1}{n}\sum_{k=1}^{n}Z_k \le \frac{1}{2}\text{ for infinitely many }n]=0$

Let $Z_1, Z_2,\ldots$ be independent identically distributed (i.i.d) binary variables with $P[Z_i = 1] = 1-\alpha $ for some $\alpha > \frac{1}{2}$. Using the transformation $X_i=2Z_i-1$ together ...
1
vote
1answer
50 views

Random walk and Occupation measure

This is homework so no answers please I want to find for some $A\subset \mathbb{R}$ the limit $$\lim_{n\to \infty}\mu_{n}(A)=\lim_{n\to ...
0
votes
0answers
9 views

Cumulative minimum of an Ornstein-Uhlenbeck process

Assume we generate a sample path $X_t$ from an Ornstein-Uhlenbeck distribution (i.e. a mean-reverting random walk), where $dX_t = −\rho(X_t − \mu)dt + \sigma dW_t$. For concreteness, take $\mu = 0$, ...
0
votes
1answer
39 views

Random walk question

here is the problem that I have been trying to do: N+1 plates are laid out around a circular dining table, and a hot cake is passed between them in the manner of a symmetric random walk: each time it ...
5
votes
1answer
30 views

counting combinations of {+1, -1} with constraints

I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions: 1) the total has to sum to $N$ 2) no partial sum is ...
2
votes
2answers
43 views

Random sequence of $0$'s and $1$'s - what is the average 'in a row' succession

Let's say we create a sequence from coin tossing. Heads will be signified as $0$ and tails as $1$ Let's define $R$ as a successive elements(in the given sequence) of the same value. for example we ...
1
vote
1answer
34 views

Proof that random walk visits zero infinitely many times

Since the Green function $G(x,1)=\sum\limits_{n\in \mathbb{N}_0}P(S_n=x), x\in\mathbb{Z}^d$ gives the expected number of visits to $x$ in a random walk, I'm asked to prove the following: I have to ...
1
vote
2answers
30 views

One dimension symmetric random walk

We have person that starts at $x=0$ and at every step he goes left with probability $0.5$ and right with probability $0.5$. What is the probability he will arrive at $x=3$ at some time? I got ...
0
votes
4answers
128 views

Random walk on a finite square grid: probability of given position after 15 or 3600 moves

An ant is walking on the squares of a 5x5 grid - it starts in the center square. Each second, it will choose (with equal probability) to do one of the following: Move north one square Move south ...
3
votes
1answer
98 views

Expected time to get from bottom left to top right in a square

Consider a two dimensional random walk starting at the bottom left hand corner of an $n$ by $n$ square. At each step you take one step up, down, left or right distance $1$. Each choice has equal and ...
1
vote
0answers
15 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $P_{k,j}$ be the probability that the walker hits the point $k$ without returning to the origin in ...
2
votes
1answer
51 views

Intuition in Random walk

Suppose $X_i$ are i.i.d. r.v. $S_n=X_1+\cdots+X_n$ is random walk. Why $\mathcal{F}_n =\sigma(X_1,\cdots,X_n)$ are called the information known at time n? I think We only know the measurability of ...
1
vote
1answer
98 views

Problem about Random walk and Stopping time.

Here is an example in "Probability with Martingales" My questions are: (1)Does equation (a) hold for $T=\infty$? (2)The equation:$$\mathbb{E}M_T^\theta=1=\mathbb{E}[(sech \theta)^Te ...
0
votes
0answers
32 views

Maximum of a Gaussian random walk with non-identical steps

Consider a sequence of independent normal random variable $X_1,...,X_n$ with (negative) means $\mu_1,...,\mu_n$ and standard deviation $\sigma_1,...,\sigma_n$. Define \begin{equation} S_k = ...
0
votes
1answer
29 views

Random walks on connected finite graphs

On a finite connected graph if a random walked is choosing the next vertex uniformly at random from among the edges of its current vertex, then it looks quite obvious to me that given an infinite walk ...
0
votes
1answer
123 views

Why is the expected average displacement of a random walk of N steps not $\sqrt N$?

Let $D_N$ be the expected average of the displacement of a random walk on $\mathbb Z$ from the origin, where $N$ is the number of steps, each of which is either $-1$ or $1$. We take the definition of ...
2
votes
0answers
18 views

Comparing hitting time of two random walks

There are two random walks, $S^t_i=S^{t-1}_i+ X_i^t$ for $i=1,2$, $X^t_i$ i.i.d they have boundaries $h_1$ and $h_2$ respectively. I'm wondering if it's possible to calculate the probability that one ...
1
vote
1answer
41 views

Invariant mesure of a reflected random walk

Let $(X_n), n \geq 0$ be a Reflected Random Walk defined by: $X_0 = 0$ and: $ X_{n+1}=\max( 0 , X_n + \xi )$ $\xi $ is a random variable such that $P(\xi=a)=\theta$ and $P(\xi=-b)=1-\theta$ for a ...
1
vote
0answers
30 views

Conditional return time of simple random walk

Consider a simple random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0 = 0$. The probability to jump to the right neighbour is $p \geq \frac{1}{2}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, ...
0
votes
0answers
35 views

Reflected random walk

Suppose that $X_n$ is a reflected (in 0) random walk with parameter $\theta$. So $X_{n+1}-X_n = 1$ with probability $\theta$ , and -1 with probability $1-\theta$ when $X_n \geq 1$, if $X_n=0$ then ...
7
votes
1answer
51 views

Random walk on cubic lattice

Suppose at every point of the cubic grid in n dimensions is a particle, and at every timestep every particle moves at random to one of its 2n neighbours. As time goes to infinity, what is the ...
0
votes
2answers
43 views

Non-Probabilistic Argument for Divergence of the Simple Random Walk

The simple random walk is one starting at $0$ with steps of $-1$ and $1$ with equal probability. Is there a proof not involving (too much) probability - preferably number-theoretic - of why this walk ...
0
votes
0answers
39 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
1
vote
0answers
60 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
0
votes
1answer
30 views

Distributions of local times of a single excursion of 1D random walk

Consider Simple Random Walk in one dimensions, starting from $x \in \mathbb{Z}^+$. The walker jumps to the right with probability $p$ and to the left with probability $1-p$. Assume $p \leq ...
1
vote
1answer
51 views

Random walks with finite chance of escape

In a recent answer I gave a combinatorial interpretation for the sum $\sum_{n=1} \binom{2n}{n}\frac{4^{-n}}{n+1}=1$: namely, that it corresponded to the probability of all outcomes adding to $1$. A ...
2
votes
2answers
57 views

Limit value of a product martingale

This question came from a problem i was solving for self-study. I'll state the problem first: Let $Y_n \sim \mathcal N(0,\sigma^2)$ be independent normally distributed variables, $X_n = ...
0
votes
0answers
32 views

1-dimensional random walk with barrier

Let $X$ be a random walk on $\mathbb{Z}_{\ge 0}$ starting at $0$, with step size 1, and there is a barrier at 0 so that if one tries to move to -1 it stays at 0 (non-reflecting). If we fix the number ...
2
votes
1answer
59 views

Lattice Path Spaces.

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to ...
3
votes
1answer
75 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
32 views

Random walk on free group on two elements

Let $F_2$ be the free group on two elements, generated by $\{a, b\}$. We perform a random walk on $F_2$, starting at the identity element $e$ and uniformly at random selecting one of ...
1
vote
1answer
71 views

Proving a property of hitting times of a simple random walk on $\mathbb{Z}$

I'm reading the course notes of a probability course about martingales currently and I'm trying to solve some of the exercises, however I'm very much stuck with the following exercise: Let $\left\{ ...
0
votes
1answer
48 views

Are random walk variations Markov-Chains?

Let $S_{n}:= S_0 + \sum_{i=1}^{n}X_i$ be a simple random walk, $X_i$ are independent random variables with $P[X_i=1] = p, P[X_i = -1] = 1-p$. Let $M_n:=\max\{S_0, \dots, S_n\}$. The task at hand is ...
0
votes
0answers
42 views

Probability of Stopping Time Taking specific value - Random Walk 1d

We are considering a simple random walk $(X_n)_{n\in\mathbb{N}}$ starting at $X_0=0$ with $X_n=\sum_{i=1}^nY_i$ where $Y_i$ are iid and $\mathbb{P}(Y_i=1)=\mathbb{P}(Y_i=-1)=\frac{1}{2}$. We want to ...
3
votes
0answers
29 views

Self-avoiding random walk on $\mathbb{Z}^2$ getting stuck

Let $W_n$ be a self-avoiding random walk (SAW) on $\mathbb{Z}^2$, starting at the origin. Formally, $W_0=0$ and for $n\ge 0$, $W_{n+1}$ is chosen uniformly from the neighbours of $W_n$ which were not ...
0
votes
1answer
36 views

Writing down the transition matrix of a discrete Markov chain

Please consider the following scenario: One person is walking along a discrete circle induced by $\mathbb{Z}/n\mathbb{Z}$ In each round we roll a dice with $w\in\left\{2,\ldots n\right\}$ sides If ...
0
votes
1answer
27 views

Simple Random Walk probability of first visit

Consider a particle that moves according to a simple random walk. Denote by $X_n$ the position of the particle immediately after step $n$. Assume that $X_0 = 0$ and that, at each step, the ...
0
votes
0answers
25 views

Weighted random walk in 1-dimension

Suppose we have random walker on a line, he can only stay on sites which are, say, a distance $a$ from each other. At each step he can go left or right. Every time he steps on a site, makes the ...