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

learn more… | top users | synonyms

2
votes
0answers
25 views

How to analyse a random walk with random transition probabilities

Consider a $1$-dimensional random walk with discrete time steps. We start at the origin and at each integer position there is possibly different probability of moving right one step, or left one step. ...
1
vote
1answer
25 views

Simple Markov Chain: Random Walk on $\mathbb{Z}$

We are given a random walk on $\mathbb{Z}$, where $p_{i, i+1}= p < \frac{1}{2}$ and $p_{i,i-1}=1-p > \frac{1}{2}$, starting at $0$. Now we have to compute the probability that we eventually ...
1
vote
2answers
29 views

Simple Random Walk on Integers

Question concerning a simple random walk on 1D. Why the probability of hitting $\pm 2^n$ before return to $0$ is $2^{-n}$? I have no idea how to start... Thank's!
0
votes
0answers
15 views

Expected Value of Continuous Random Walk

I'm currently attempting my MMath master project. However, i'm a little stuck on an expected value of the continuous distribution. Its where i wish to change my random walk from a continuous walk to ...
-1
votes
0answers
22 views

Random walk in Greenberg-Hastings model [on hold]

Consider the following cellular automaton known as the Greenberg-Hastings Model: The state space is $X=\left\{0,1,2\right\}^{\mathbb{Z}^d}$. Sites $x\in\mathbb{Z}^d$ represent cells which can be ...
1
vote
0answers
23 views

Random walk return for subgraph

Assume that $G$ is a finite graph and we have a simple random walk starting at some vertex $v$ of $G$. We fix $n$, and consider the probability that the random walk does not return to $v$ after $n$ ...
0
votes
0answers
6 views

Stochastic Process with mean reverting property

Here I am seeking for a definition of what kind of stochastic processes are called mean reverting stochastic process. That is, what are the properties that a stochastic process should obey in order to ...
0
votes
0answers
20 views

Calculate 1D random walk with alternating step size expected iterations to return to origin

I'm trying to solve a problem as outlined below; I'm a bit new, however, and I'm not sure how I could solve this problem. Assume someone has lost their keys, and uses an inefficient random walk to ...
0
votes
0answers
31 views

Random Walk, Markov Process

I'm stuck on a homework question and am wondering if anyone can offer some hints. Suppose we have some straight line graph G over the set $ V = \{1, 2, 3, ... , n\} $ of vertices, with an edge between ...
1
vote
0answers
26 views

Random walk on non-negative integers

Consider the Random walk on the non-negative integers with transition probabilities $$ p_{0,1}=1,~~~p_{i,i+1}=1-r,~~~p_{i,i-1}=r,~~~i\geq 1. $$ Determine $p_{00}^{(n)}$ As far as ...
0
votes
0answers
50 views

Recurrence of a trapped random walk

i am wondering how behaves a symmetric random walk on $\mathbb Z$ except in $\pm 1$ where it goes towards 0 with probability $p$ and towards $\pm 2$ with probability $ q < p \ (p+q=1)$ ? on which ...
2
votes
2answers
43 views

Expected time to get x units away when only able to move 1 unit either way

I know this is a common problem, but this problem has been bugging me after someone asked me it, and I can't find the answer anywhere on the Internet. Say we have a number line, and we start at the ...
0
votes
0answers
67 views

Random walk on infinite binary tree (recurrence, transience)

Consider a random walk on the infinite binary tree with root $x$ which has the following transition probabilities. $$ p_{x,0}=p_{x,1}=\frac{1}{2},~~~p_{y,y0}=p,~~~p_{y,y1}=q,~~\text{and ...
1
vote
0answers
24 views

Prove that $\text{Var} \tau = \frac{1 − (p − q)^2}{(p-q)^3} $ where $\tau$-stopping time

Let $S_n = \xi_1 + \dots + \xi_n$ be asimetric random walk such that $P(\xi_i = 1) = p > \frac{1}{2}$ and $P(\xi_i = -1) = q $. Let $\sigma^2 =1-(p-q)^2$ and let $X_n=(S_n-n-(p-q)n)^2 - \sigma^2n $ ...
2
votes
0answers
30 views

Sum of $\{X_n\}$ iid random variables contained in a compact interval implies each $X_i=0$ a.s.?

I am working through an exercise that starts with a sequence i.i.d. random variables where for $a\leq b$, $$\Pr\left(\lim\sup_n \sum_{i=1}^{n} X_i \in [a,b] \right) \neq 0.$$ Does this require $X_i ...
0
votes
0answers
24 views

Theorem and proof about random walks

$\tau_{+d}=inf \{n: S_n =0, S_{n+1}>0, ... ,S_{n+d}>0 \}$ $\tau_{-d}=inf \{n: S_n =0, S_{n+1}<0, ... ,S_{n+d}<0 \}$ $q_n=P\{S_1>0,...,S_n>0\}=P\{S_1<0,...,S_n<0\}, n\in N$ I ...
3
votes
3answers
58 views

Guarantee to lose in +EV gamble?

I've checked it in numerical experiments but found it counter intuitive. A player start with $a_0>0$ dollars, let's denote the amount of money after $n$ rounds $a_n$ dollars. In each round, the ...
0
votes
0answers
27 views

Stochastic processes

Update I am a bit confused whether $y_t$ is independent over time under the following assumptions: Consider, first a RV $A$, that follows this process: $A_t = \rho A_{t-1} + e_t$, where $e_t$ is ...
1
vote
0answers
22 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
26 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
13 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
39 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
25 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
23 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
44 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
21 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
37 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
21 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
22 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
53 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
11 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
41 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
34 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
44 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
49 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
34 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
176 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 ...
4
votes
1answer
102 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
18 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
56 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
107 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
36 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
30 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
147 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
19 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
33 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
41 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 ...