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
175 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
80 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
177 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
68 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
529 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
113 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
0answers
97 views

Extracting hitting times from the pseudoinverse of a Laplacian matrix for an undirected graph

Provided a pseudoinverted Laplacian matrix for an undirected graph $G$, how can I extract first passage and commute times between vertex pairs in $G$?
1
vote
1answer
159 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
49 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
163 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
187 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
148 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
2answers
251 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
116 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)$?
1
vote
0answers
236 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. ...
2
votes
0answers
146 views

Random walks in $1$, $2$ and $3$ dimensions [closed]

I know that this may seem easy but I have no clue where to start (if possible could you answer this in the simplest way possible)? Consider a person who is at the position $x=0$ on the $x$-axis at ...
1
vote
1answer
56 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
140 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
116 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
170 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
329 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
332 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
361 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
136 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
185 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
134 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
125 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
87 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
188 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
120 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
167 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
129 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
439 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
141 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
107 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 ...
3
votes
0answers
142 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
115 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$ ...
1
vote
1answer
456 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
518 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
175 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
110 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
28 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
49 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
118 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
82 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
124 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 ...
0
votes
1answer
207 views

Symmetric random walk with bounds

can anyone help me with this: We are considering a symmetric random walk that ends if level 3 is reached or level -1 is reached. Start=0 What is the expected number of walks? So I am looking for: ...
3
votes
2answers
925 views

Null-recurrence of a random walk

In a random walk on $\mathbb{Z}$ starting at $0$, with probability 1/3 we go +2, with probability 2/3 we go -1. Please prove that all states in this Markov Chain are null-recurrent. Thoughts: it is ...
0
votes
1answer
126 views

Random walk with zero drift

Let $X_{k+1} = X_k+\xi_k$ be a random walk on $\Bbb R$ starting from $0$ and such that $\mathsf E\xi_0 = 0$, $\mathsf{Var}[\xi_0]>0$. Is that true that $$ -\infty = ...
9
votes
3answers
336 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...