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
1answer
39 views

Brownian motion is almost surely continuous

Why is Brownian motion required to be almost surely continuous instead of merely continuous? For example, this is stated as condition 2 in this article in section 1, Characterizations of the Wiener ...
1
vote
0answers
14 views

What are the assumptions for applying Wald's equation with a stopping time

I am trying to understand the assumptions under which I am allowed to apply Wald's equation for a sum of a random number $N$ of random variables $X_n$, $1\leq n\leq N$. There seem to be several ...
1
vote
1answer
24 views

Expectation of constraint random walk

Problem description I am currently dealing with a practical problem that can be simplified to something like this: I start by setting a value to 0 Every minute, I try to increase or decrease 1 or ...
3
votes
0answers
29 views

Random walks and their uses

Can anyone provide some motivation behind the use of random walks? I know they're used a lot in computer science, in things like page walk (I think that's what it was called- something like pagerank), ...
0
votes
3answers
71 views

Random walk on the real line

A particle stands on the origin of real line. In every second it jumps one unit to the left or right by the probability $\frac{1}{2}$. what is a probability that it reach to point $+1$?
9
votes
1answer
57 views

random walk on finite cyclic group

Suppose that I have a random walk on the finite cyclic group of order $d > 2$, where the initial probability distribution $Q$ assigns the values $p, q, r$ to $-1, 0, 1$, respectively, where $p + q ...
0
votes
1answer
29 views

Simple Random Walk and $n$th zero hitting time

I am reading an example in Durrett's book regarding the $n$th time the random walk hits 0. Consider a simple random walk, $X_i=1$ or $X_i = -1$ with equal probability. Let $S_n = X_1 + \dots + X_n$. ...
0
votes
0answers
6 views

Power law in power spectrum and memory.

If we generate white noise and do the FFT of it, we get the same amplitude for each of the frequencies. Therefore, the output of the FFT of the noise follows approximately the power law ...
1
vote
1answer
35 views

Random Walk on Clock Hands

We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps. If you start at 1 what is the expected number ...
2
votes
1answer
65 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
33 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
35 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
16 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
vote
0answers
25 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
40 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
34 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
77 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
27 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
59 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
1answer
46 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
27 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
46 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
27 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
47 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
38 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
23 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
13 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
46 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
35 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
54 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
35 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
207 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
57 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 ...