Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

0
votes
0answers
11 views

mean and covariance of a random process

I'm looking at an example from a book I'm reading, How does it formulate the mean? I am thinking $$E[X[n]] = \sum\limits^\infty_{-\infty} X[n]P[X[n]] =\\ \sum\limits^\infty_{n=-\infty} X[n = even] \...
0
votes
0answers
14 views

The probability of a random walker hitting a barrier for the first time

I am grabbling with the following problem and the final condition gets me. To me it seems that I must do an awful lot of accounting to keep track of instances where the random variable has already ...
0
votes
0answers
31 views

Help on Martingales (Random Walk): $\mathbb{P} (Z_1=-1) = \mathbb{P} (Z_1=1) = \frac{1}{2}.$ [on hold]

I cannot figure out how to solve this exercise. Any explanation and/or tip about this would be appreciated. $\\$ Let $(Z_n)$ be a sequence of i.i.d. random variables with: $$\mathbb{P} (Z_1=-1) = \...
1
vote
0answers
14 views

Random walk with incommensurate steps

Anyone seen any research on random walks with steps +q/-1, where q is irrational? I am interested in probability of staying positive for n steps. Alternative formulation would be steps of size 1 ...
0
votes
2answers
16 views

Stretching the Brownian Motion in [0,1] to get another Brownian Motion in [0,t]

I'm running a simulation of a Standard Brownian Motion by limit of a Symmetric Standard Random Walk $\{S_n ,n\geq 1\}$ and $S_n=\sum_{k=1}^n X_k$, where $P(X_k =-1)=P(X_k =1)=\frac{1}{2}$. And ...
1
vote
1answer
27 views

Show that a random walk on a finite grid graph is recurrent

I want to show that a random walk on a graph is recurrent. The graph is a network of nodes which connect together to make a $N \times M$ rectangular grid, such as this, my first thought was to ...
0
votes
0answers
31 views

Setting up a predator-prey model with diffusion

I'm trying to set up a predator-prey model, where the predator affects the distribution of the prey. Effectively, over time the prey has moved from areas of high concentration of the predator to areas ...
2
votes
0answers
28 views

moments of absorption time of simple random walk with 1 barrier.

let $S$ be a simple random walk starting at 0 with probability $p$ of going to the right, and $q$ of going to the left and with drift to the right $p>q$. Define $T=\inf \{n>0: S_n = 1\}.$ The ...
0
votes
0answers
37 views

What does it mean for a random walk to be recurrent? [closed]

I have a random walk on a graph, and I've been asked to show that it is recurrent, and am just trying to pin down the exact meaning of this. Thanks.
0
votes
1answer
32 views

Understand the probability formula of a random walk

I have the following problem: Let's assume $G$ is a graph with vertices in red or blue colour. There is no limitation on how we connect the vertices, i.e., a red vertex can be connected with either ...
0
votes
0answers
21 views

Number of random walks starting from $0$

Find a number of paths in random walk from $S_0=0$ to $S_{8n}=0$ satisfying the following terms: (a) $S_k \le -2$ for $2 \le k \le 4n-2$ (b) $S_k > 0$ for $4n \le k \le 8n$ Theorem: Let $S_0=a$ ...
0
votes
0answers
22 views

Finding and solving a recurrence relation for a random walk between triangle vertices.

In order to find a first order recurrence relation, I partitioned on the position of the bug after the $(n-1)^{th}$ jump. Let $A_n$ be the event that the bugs lands on vertex 1 after the $n^{th}$ ...
3
votes
2answers
100 views

Why this random walk can't go on forever?

$A$ starts with $i$ coins, $B$ with $N-i$. At each trial, $A$ gives one coin to $B$ with probability $p$ or $B$ gives one coin to $A$ with probability $q$ where $p+q=1$. This can be modeled as a 2D ...
0
votes
0answers
8 views

Random walk on sparse graphs

In one of the papers I am reading I saw an information that "short (O(log n)) random walk will not cover to a stationary distribution since walks will tend to remain within regions which ...
1
vote
1answer
43 views

random walk, how many steps does it take to visit all the states?

For example, random walk in a 2-D integer space, range of x: [-5, 5], range of y: [-8, 8] starting at (0,0), equal probability to go left/right/up/down, step size 1. How many steps it is going ...
1
vote
1answer
43 views

random walk with finite range

Let $X=(X_n)_{n \in \mathbb{N}}$ be a sequence of i.i.d. $\mathbb{Z}$-valued random variables satisfying the following conditions: a) For all $n \in \mathbb{N}$ and $k \in \mathbb{Z}$, we have $\...
0
votes
1answer
46 views

On simple random walk with $\mathbb{P}\left(X=+1\right)=p>\frac{1}{2}$

I'm reading Ross' "Stochastic Processes" book, in the part of random walks, and I have troubles to understand an argument. Consider $\{S_n\}_{n\ge 0}$ the simple random walk, with $\mathbb{P}\left(X=...
1
vote
0answers
14 views

Biased random walk conditioned to reach 0 reverses the bias

Let $S_n$ be a biased random walk with $P(S_{n+1} = S_n +1) = p >1/2$ and $P(S_{n+1} = S_n -1) = 1-p$. Suppose $S_0 = 1$ and let $\eta= \inf \{ n \colon S_n = 0\}$. Possibly $\eta = \infty$, so ...
2
votes
1answer
33 views

Probability of sumprocess

Consider $(X_n)_{n\ge 1}$ iid with $P(X_1=1)=P(X_1=-1)=\frac{1}{2}$. Then there is the sumprocess $S_n:=\sum_{i=1}^n X_i$ and the stopping times $$T_{a,b}:=\min\{n\ge 1:S_n\in\{a,b\}\},$$ $$T_{a}:=\...
1
vote
1answer
91 views

A certain fact about conditional expectation concerning the one sided shift associated to the random walk on a graph.

$\newcommand{\mc}{\mathcal}$ $\newcommand{\E}{\mathbf E}$ $\newcommand{\R}{\mathbf R}$ $\newcommand{\P}{\mathbb P}$ $\newcommand{\wh}{\widehat}$ Definitions Let $G$ be a connected graph on a finite ...
0
votes
1answer
14 views

Random walk's stopped process

If $S_n$ is a simple random walk in $\mathbb{Z}$ starting in $x \in \{1,...,N-1\}$. It is true that $P\{S_{n \wedge T}=y\}=0,$ when $y \in \{0,N\}$? Where $T = \inf\{n: S_n \in \{0,N\}\}$. I can't ...
1
vote
1answer
22 views

When is an i.i.d Bernoulli Process indepent increment?

I was reading anarticle that i.i.d bernoulli process are markov and independent increment process are markov too. So, I was wondering if an i.i.d. bernoulli process can be independent increment.
0
votes
0answers
6 views

Applications of high mean escape time subgraphs

I am learning about algorithms for finding subgraphs with high mean escape time, and I am wondering if someone could enlighten me on what applications there are for such a task. Applications to either ...
0
votes
2answers
75 views

Velocity from Probabilities in a Random Walk with One Step Memory

We consider a discrete space, continuous time random walk on the integer line where the walker hops from a lattice site to a nearest neighbor site. Suppose the walker has one step memory and it ...
0
votes
1answer
59 views

Random Walk with Stirling's Theorem

In a colloquium I saw the following result: In simple and symmetrical random walk $S_n$ d-dimensional starting in $0$ you have: $P(S_{2n}=0) \sim \frac{1}{n^{d/2}}$ In which book can I see your ...
0
votes
0answers
17 views

Dampening Random Walk

Say we have some vairble $x_{0} = 0$ and at each time step $Pr[x_{t+1} = x_{t}+r_{t}] = Pr[x_{t+1} = x_{t}-r_{t}] =0$. We know if $r$ is constant over time then there is always a finite amount of ...
0
votes
0answers
12 views

Reference Request for Random Walks

This is kind of a vague question, but I will try to make it as precise as possible. So I have been studying random walks and their properties, in particular, I am interested in conditions that imply ...
1
vote
2answers
15 views

What does the arrows mean? (notation for markov chain topic)

I found this arrow notation while reading about markov chain and random walks and dont understand this notation. I can't find the answer anywhere. Help? {T0 < Tc} (slanted arrow up, from left ...
1
vote
1answer
37 views

The infinite random walk: two approaches leads to two different solutions. How to solve?

The "random walk" process is well known for mathematicians, see for instance https://en.wikipedia.org/wiki/Random_walk . It is also known as "the drunk walk". It is demonstrated that if you have a n ...
1
vote
1answer
50 views

Gamblers ruin and the mean time calculating

There's a gambler with initial money $k=100\$$. He plays till bankruptcy or till having $N=500\$$. In every game he wins $100\$$ with probability $p=\frac{1}{2}$, loses $100\$$ with probability $q=\...
0
votes
1answer
16 views

Derivation of $\mathbb{E}\left [ S_{n}^2 \right ]$ in a simple random walk

Consider a simple random walk on the number line $\mathbb{Z}.$ At each unit, the walker moves left or right with probability $\frac{1}{2}.$ Assuming the walker starts at point $x$, we can define $$...
1
vote
1answer
50 views

Find the number of paths in random walk

Find the number of paths in random walk from $S_0$ to $S_{4n}$ satisfying all of the following terms: a)$S_0 = S_{2n}=0$, b)$S_k \ge 1 \; for \;1 \le k \le 2n-1$, c)$S_{4n}=2$. I need help with ...
1
vote
0answers
169 views

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 ...
1
vote
1answer
173 views

(Random Walk) Compute average ratio for the number of right cookies to total cookies eaten in a single cycle

This question is a continuation of this post. Currently I am reading the paper Excited Random Walk in One Dimension. At page $8$ right column, the authors obtain equation $(33)$. The joint ...
8
votes
1answer
83 views

Bounding survival probability of an asymmetric random walk by a symmetric one

Consider two random walks that start from point $x=0$ and time $t=0$ and move either to right $x+1$ or left $x-1$: 1) Walker 1's first move is with equal probability to the right/left. However, ...
0
votes
1answer
24 views

Does a random cross the “speed line” infinitely often almost surely?

Suppose $(x_t)_{t=0}^\infty$ is a random starting from $x_0=0$ with transition probability $P(x_{t+1}-x_t)=p\mathbf 1(x_{t+1}-x_t=1)+q\mathbf 1(x_{t+1}-x_t=-1)$ where $p\ge0,q\ge0,p+q=1$. Given $a>...
-1
votes
0answers
34 views

The crossing probability of a random walk over an oblique line and the Brownian motion as the limit of a random walk

Suppose $(x_t)_{t=0}^\infty$ is a random starting from $x_0=0$ with transition probability $P(x_{t+1}-x_t)=p\mathbf 1(x_{t+1}-x_t=1)+q\mathbf 1(x_{t+1}-x_t=-1)$ where $p\ge0,q\ge0,p+q=1$. We are given ...
0
votes
0answers
27 views

Random walks in different directions?

Assume a person random walker takes equal steps to the right or left with equal probability. Probability that taking n steps, the person walking will be displaced 1 standard deviation or greater in ...
1
vote
2answers
58 views

Probability that a random walk reaches an arbitrary value in a given number of steps

I have a simple random walk over $\mathbb{Z}$: $X_{i+1} = X_i - 1$ (probability $p$) or $X_i + 1$ (probability $1-p$) and $X_0=0$ I want to find the probability of reaching an arbitrary negative ...
4
votes
1answer
130 views

(Random Walk) Compute average relative number of consecutive cookies eaten from the right side of the gap

Currently I am reading the paper 'Excited Random Walk in One Dimension.' At page $8$ left column, the authors obtain the following: Probability that the walk eats precisely $r > 0$ consecutive ...
1
vote
1answer
21 views

Looking for examples for the notion of cocycles.

A set $G$ endowed with an associative binary operation is called a semigroup if it possesses an identity element. Thus a semigroup is short of a group in that it may not be closed under inverses. Let ...
0
votes
1answer
35 views

heat equation stability condition random walk

I consider the heat equation : $$\frac{\partial f}{\partial t}(t,x) = \frac{\partial^2f}{\partial x^2}(t,x)$$ on ${\Bbb R}_+^* \times [0,1]$. One can proove that the explicit Euler scheme is stable ...
1
vote
0answers
35 views

Maximum of a simple random walk

$M_n=\max\{S_k : k= 1,...n\}$ where $S_n$ is a simple random walk, $S_n = \sum_{i=0}^n X_i$ and $X_i$ is a Bernoulli random variable where $P(X = 1) = P(X = -1) = 0.5$ Prove that $P(M_n \geq r \...
0
votes
0answers
52 views

(2-D Random Walk) Probability of Returning to Origin

I know this is a long question, but please bear with it since it is just because I go into a lot of detail: A particle moves 1 step in the N, E, S, or W direction each with probability 1/4 every ...
2
votes
1answer
96 views

Stationary distribution and limiting distribution of a random walk

Consider the random walk on $S={0, . . . , N}$, defined as follows. We are given $p, q, r >0$ with$ p+q+r= 1$. The walk increases by 1 with probability $p$, decreases by 1 with ...
0
votes
0answers
17 views

Convergence of a stochastic sequence??

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...
0
votes
1answer
23 views

Intuition behind a simple random walk on integer lines

Consider a random walk on a line of integers. Suppose we start from the state $x$. Then, the probability of jumping from $x$ to $x+1$ is $p(x, x+1)=p$, and the probability of jumping from $x$ to $x-1$ ...
4
votes
0answers
60 views

A probability concerning the maximum and minimum of a simple random walk

Let $X_i$ be i.i.d. such that $\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$. Let $a\in \{1,2,....\}$, now define the random walk, $S_0=a$ and $$S_n = a+\sum_{i=1}^n X_i$$ Now define the maximum ...
0
votes
0answers
16 views

Obtaining generating function for recurrence “time”

I was working on some exercise questions in Chapter 2 of Karlin and Taylor's "A First Course in Stochastic Processes." I was stuck on question 2.12 to be specific. Regarding a 1-dimensional random ...
0
votes
0answers
11 views

variance of a complex, stationary, autoregressive process

Let $\{c_n\}$ be a complex stationary discrete-time random process such that: \begin{equation} c_n = \sum\nolimits_{k=1}^{p} \bar{\rho}_k c_{n-k} + w_n, \quad n \in (-\infty,\infty) \end{equation} ...