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
106 views

Flipping an unfair coin

An coin has probability $p<0.5$ of landing heads up. We flip it infinitely many times, after $n$ tosses, let $S_n$ be the number of heads minus the number of tails. What is the expected value of ...
4
votes
0answers
146 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
2
votes
0answers
62 views

Dimension free Concentration bounds for Martingales

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
2
votes
1answer
110 views

An application of Donsker's theorem.

Let ${X_i}$ be iid with $E[X]=0$ and $Var(X)=\sigma^2$ Let $S_0=0$ and $S_n=X_1+...+X_n$ for all $n \ge 1$. Show that $\lim_{n\rightarrow \infty}P(S_k>0 \space for \space k=n,n+1,\dots,2n)=1/4 $. ...
1
vote
1answer
342 views

Random walk serial correlation

Given a model $$Y_t =b_0 + b_1 \cdot X_t + b_2 \cdot Z_t + e_t,$$ where the error term $e_t$ follows a random walk form of serial correlation $e_t = e_{t-1} + u_t$. Further assume $u_t$ has zero mean ...
2
votes
1answer
366 views

Proof: Mean and Variance of the squared distance of a random walk in n-dimensional space

consider a $x$ step random walk starting from origin in $n$-dimensional space where each step is taken into a random direction and has a distance of 1, i.e., each step is a vector on the ...
1
vote
1answer
275 views

A Boundary crossing result for discrete brownian bridge

Let $S_n$ be a random walk with gaussian increments with $S_0=0$, i.e. $S_n-S_{n-1}\sim N(0,1), n\geq 1$. Fix $a>0,b\in \mathbb{R}$ and $c<a+bn$. Define the new process $$ ...
1
vote
1answer
99 views

Help calculating variance of a random variable

This is related to this question Average end point of 1-dimensional random walk? Given several discrete random variables such that $p(Z_i=1-2k)=p$, where $k$ is a small real number, and ...
2
votes
1answer
376 views

Mean displacement for a random walk on a $d$-dimensional lattice

How does the mean displacement of a random walk on a $d$-dimensional integer lattice (or $d$-dimensional hexagonal lattice) scale with the number of steps $N$ in the walk? Is the displacement always ...
0
votes
1answer
112 views

Average end point of 1-dimensional random walk?

Is it possible to estimate the average end point of a 1-dimensional random walk of n steps where the probability of going "left" is p and going "right" is 1-p? Thanks.
0
votes
2answers
912 views

Random walk with absorbing barriers

Consider a random walk with absorbing barriers at $0$ and $3$. $\mathbb P(S_{n+1}-S_n=1)=0.6$ and $\mathbb P(S_{n+1}-S_n=-1)=0.4$. What is the probability of eventual absorption at $0$, given that the ...
4
votes
2answers
143 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
1
vote
1answer
253 views

Cover Time for Random Walk on a cycle

I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ ...
1
vote
0answers
65 views

planar walks and catalan numbers

prove that following numbers are equal: (unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (0,1) or (1,0), ending at the same point and only intersecting at the ...
4
votes
1answer
331 views

Random Walk on Z

Let $S_n$ be the symmetric random walk on $\mathbb{Z}$. How do i calculate $P(\limsup_{n\rightarrow\infty} S_n=\infty)$? I already know that the probability is 1 but I don't really know how to start? ...
0
votes
1answer
347 views

Simple Probability Matrix

Consider a simple model that predicts whether you pass you next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will pass your ...
2
votes
0answers
300 views

Teleporting random walk

Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper) I used a one ...
0
votes
3answers
930 views

The variance of a simple random walk/process

I've been trying to wrap my head around this for the past day. Please help! Let $\epsilon_i = \pm 1$ with equal probabilities independently for $i=1,...,N$. Then $Z_i = \epsilon_1 + ... + \epsilon_i$ ...
0
votes
1answer
118 views

The random walk $S_n=a+\sum_{i=1}^nX_i$

Consider a variant of random walk defined as $$S_n=a+\sum_{i=1}^nX_i,$$ where $X_i$ takes either value $2$ with prob= $p$ or value $-1$ with prob =$1-p$. What is $P(S_n=b)$?
2
votes
1answer
442 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
1
vote
1answer
60 views

Inequality between two Random Walks

Let's consider two Random Walks, $$x^{(1)}_t = x_0 + \sum_{i=1}^{t}\xi^{(1)}_i,$$ $$x^{(2)}_t = x_0 + \sum_{i=1}^{t}\xi^{(2)}_i.$$ The random variables $\xi^{(1)}_i$ are i. i. d. They take values on ...
3
votes
1answer
152 views

A Coupled Random Walk on the xy-Plane

Consider a point on the $xy$-plane whose position is updated in iterations. In each iteration, the point undergoes, with equal probability, either an $A$- or a $B$-update, defined as follows: ...
3
votes
1answer
154 views

successive doubling the stake until head appears

I consider the following gaming system: Start with 1 dollar and always bet on head (coin tossing). You always double your stake until the first head appears. Maximum rounds: $n$ I formulated it as a ...
1
vote
1answer
359 views

Asymmetric random walk with unequal step size other than 1.

Say, an asymmetric random walk, at each step it goes left by 1 step with chance $p$, and goes right by $a$ steps with chance $1-p$. (where $a$ is positive constant). The chain stops whenever it ...
0
votes
1answer
681 views

Expected hitting time of one of two barriers

In the webpage "hitting time of one of two barriers", the probability that a non symmetric random walk hits one of two barriers is computed. The walker starts from $x=0$ and the barriers are located ...
1
vote
2answers
609 views

Probability related to random walks in two dimensions

I'm trying to show that two random walks will eventually meet in a two dimensional setting but I can't figure out where to start. Can someone lead me towards the right direction?
4
votes
2answers
561 views

Random walk on lollipop graph

Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
1
vote
1answer
142 views

How to solve recurrence in two variables

How can you solve this simple looking recurrence relation in two variables? $f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x}$ The function $f$ is defined for non-negative integer values $a$ and ...
0
votes
2answers
265 views

hitting time of one of two barriers

Let's consider a one-dimensional Random Walk. At each time the walker moves of one step to the right with probability $p$ and to the left with probability $q$, with $p+q=1$. The walk is not symmetric, ...
1
vote
1answer
201 views

Random Walk probability game

I try to solve some exercises from olympiads and I have difficulties with this one: Consider a round table with 20 people. One of these players receive a book and chooses one of his neighbors and ...
4
votes
0answers
131 views

probability of this event happening

Play $(n+1)t$ rounds of the same coin-tossing game and the coin is fair ($n$ is a fixed natural number). Please help me find the following probability: $P$(the number of rounds of tossing that ...
2
votes
1answer
90 views

is the possibility of this event happening positive?

Play 2*t rounds of the same coin-tossing game, please express P(t rounds show head and the other t rounds show tail, and at any time point between 0 and 2t, the number of coin landing head is no less ...
1
vote
0answers
339 views

Extinction probability of a simple birth death process

X is a simple birth death process with birth rate $\lambda n$ and death rate $\mu n$ Embedded within a simple birth death process is a simple random walk. Let $Y_n $ be the value of X at the time of ...
4
votes
1answer
141 views

Chance of being able to quit while ahead in a betting game (Markov chain with gambler's ruin)

Suppose a player starts with $N$ chips, and is playing a game with odds $O$, betting 1 chip in each iteration. When the player reaches 0 chips the betting must end. What is the probability that at ...
1
vote
1answer
190 views

Simple random walk hitting time asymptotic behavior

Let $p(n,t)$ be the probability that a simple random walk starting at state $n$ hits $0$ within $t$ steps. How big can $p(n,t(n))$ get for large $n$ when $t(n) = o(n^2)$? It seems like maybe it could ...
-1
votes
1answer
146 views

Stationary distribution for different types of graph

This is a follow-up questions to posts: Stationary distribution for directed graph Stationary distribution for different types of graph The definition of stationary distribution in ...
0
votes
1answer
858 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
0
votes
2answers
184 views

Random Walk Proof Problem

I have to do the following problem: Let $(s_n)_{n\geq 0 }$ be a 1-dimensional, unbiased random walk. For $a,b\in\mathbb Z$, let $T_a=\inf\{n>0:s_n=a\}$ and $T_{a,b}=\inf\{n>0:s_n=a\hspace{3mm} ...
2
votes
1answer
121 views

Existence of a stationary distribution for a random walk

Consider a random walk on a infinitely countable connected graph. We assume that each vertex has finitely many neighbors and that we have a uniform bound of the number of neighbors at each vertex. The ...
4
votes
1answer
223 views

Two gamblers' ruin

I'm trying to work out the solution to a variant of the gambler's ruin. Here's my version: There are two very unlucky but friendly gamblers A and B who decide to pool their money together to form a ...
0
votes
1answer
185 views

transience and recurrence of a random walk

I have a random walk $\{X_n\}$ where each transition causes moving one step to the right (with probability $p$) and one step to the left (with probability $1-p$). Now $X_n \to \infty$ as $n\to\infty$ ...
2
votes
1answer
1k views

Expected number of steps till a random walk hits a or -b.

On wikipedia I read that the expected number of steps till a 1D simple random walk hits either $a$ or $-b$ is equal to $ab$. (I have seen this result also on other websites.) However, no proof or ...
1
vote
2answers
1k views

Stopping Time, Random Walk

I'm trying to solve this problem and don't know where to start. If someone could prove it or tell me how or point me to any relevant information I'd very much appreciate it. Let $(s_n)_{n\geq0}$ be a ...
0
votes
0answers
249 views

Expected number of steps for reaching $K$ in a random walk

Assuming steps are $+1/-1$ with a $50/50$ probability. What is the expected step count for reaching $10, 100$ or $K$?
3
votes
2answers
163 views

A problem on left skip free random walk with downward drift

Let $X_i$, $i \geq 1$ be i.i.d random variables. Let $P_j=P(X_i = j)$ and suppose that $$\sum_{j=-1}^{\infty} P_j=1$$. That is the possible values of the $X_i$ are $-1,0,1,\dots$. If we take $$S_0=0, ...
0
votes
0answers
35 views

Optimal way to move in a grid to find a random walker

Consider an $n$ times $n$ grid. Assume there are two agents $A$ and $B$. At time $t_0$, agent $A$ is at square $(n,n)$ and $B$ is at random square. At time $t+1$, agent $B$ has moved one square ...
3
votes
1answer
67 views

Random mixing of the space of triangulations of a surface

Summary: How quickly does the edge-flip random walk in the space of triangulations of a closed, connected, orientable surface converge to the uniform distribution over all triangulations? Let $M$ be ...
1
vote
1answer
120 views

Finding the exact solution of a difference equation

We know a particle moves two units to the right with probability $p$, or $1$ unit to the left with probability $q$, hence $(p+q=1)$. $$q_k=P\left(S_n=0\mid S_0=k\right)$$ We are asked to find the ...
2
votes
1answer
119 views

Uniform upper bound related to unidimensional symmetric random walk

Consider the following basic random walk : $S_n=\sum_{k=1}^n X_k$ where the $(X_k)$ are i.i.d. with $P(X_k=(-1))=P(X_k=1)=\frac{1}{2}$. Let $M_n=\max(0,S_1,S_2, \ldots ,S_n)$ and $\mu(n,t)=P(M_n \leq ...
1
vote
1answer
137 views

Show that $Z_t = Z_0 \exp\left( \mu t + X_t \right)$ is well defined where $X_t$ is a Jump process (Lévy process)

Consider $X= \left( X_t \right)_{t\geq 0}$ is a Lévy process whose characteristic triplet is $\left( \gamma, \sigma ^2, \nu \right)$ and where its Lévy measure is $$ \nu \left( dx\right) = A ...