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
2answers
367 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
403 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
137 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
206 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
153 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
126 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
88 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
229 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
126 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
173 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
134 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
536 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
147 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
109 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
157 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
132 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
549 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
630 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
183 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
126 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
31 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
54 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
102 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
129 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
234 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
1k 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
153 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
349 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 ...
0
votes
1answer
131 views

geometric sum - weighted random walk

I am trying to model the following sum: $\sum_{i=0}^{n}{W_i \alpha^{i}}$ where $\alpha \in[0, 1) $ and $W_n$ takes values 0 or 1 and may be modeled as a markow chain or for simplicity as a binary ...
1
vote
1answer
99 views

Mean time until adsorption for a well-mixed bounded random walk that suddenly allows for adsorption

I have a random walk on some interval $[0, N]$ with probability $p$ of taking a $+1$ step, probability $(1-p)$ of taking a $-1$ step, and where we have that $p>(1-p)$. Initially the boundaries are ...
1
vote
1answer
56 views

What's the name of this phemonenon in random walks?

Given a random walker on the number line that starts at 0 that has a 50% chance of going 1 unit in either direction every step, the walker will tend to stay on one side of the line for a while before ...
1
vote
2answers
129 views

Using random walks to predict behavior rather than matrix decomposition

I want to create a model that tries to predict a user's behavior based on the random walks of similar users. The problem is similar to Netflix's recommendation challenge. One of the popular solutions ...
5
votes
1answer
248 views

Walks of Even Length on a Bipartite Graph

Given a random walk on a simple $d$-regular bipartite graph $G$. The adjacency matrix $A'$ of $G$ may be split into blocks $$ A'=\pmatrix{ 0 &A^T\\ A&0 }, $$ The propagation operator $M=A'/d$ ...
4
votes
1answer
348 views

Covariance of Brownian-motion-like processes

We know that $\operatorname{Cov}(B_s,B_t)=\min(s,t)$ if $B_t$ is Brownian motion. What is $\operatorname{Cov}(B_{f(s)},B_{f(t)})$ for some injective $f$? How can I write $B_{f(t)}$ in an Ito ...
0
votes
0answers
76 views

Expected time spent in $i$, assymetric random walk on $\mathbb{Z}$

This is exercise 1.7.4 in Norris' Markov Chains textbook. I'm having difficulty calculating a simple looking expectation. Let $(X_n)_{n\geq0}$ be a simple random walk on $\mathbb{Z}$ with transition ...
0
votes
1answer
306 views

Relationship between a stationary distribution for a random walk and the hitting time at some position

In a previous question of mine, I asked for the probability distribution of an agent taking a biased walk on the positive integers (with a reflecting boundary at the origin): Probability distribution ...
7
votes
6answers
316 views

simplify summation of factorial (random walk)

I suspect that the expression $$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$ simplifies to $$\frac{2^N}{(N-1)!}$$ But I cannot find the intermediate steps. Can someone give me a hint how I can deduce ...
3
votes
1answer
81 views

Proof of random work property given the absolute value of variables

This hints that $E(|S_n|)\,\!$, the expected translation distance after ''n'' steps, should be of the order of $\sqrt n$. In fact, $$\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac ...
3
votes
3answers
107 views

Introduction to Markov Random Fields

I'm looking for a gentle introduction to this topic. The material I've found so far is substantially related to physics, and requires some background in such field. Is there anything more general and ...
0
votes
1answer
157 views

mean reverting random walks

I need a set of stochastic processes $x_i(t)$ with the following characteristics: At each time $t$, the jump of each variable can be just $+s$ or $-s$; The processes have to be mean reverting, so ...
5
votes
1answer
398 views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
2
votes
1answer
172 views

Random walk with 3 possible steps

I have i.i.d. random variables with following distribution: $$ P(\xi_i =1) = p_1, \ P(\xi_i = 0) = p_0, \ P(\xi_i = -1) = p_{-1}; \quad S_n = \sum^n_{i=1}\xi_i.$$ I am interested in probability of ...
3
votes
1answer
30 views

Infinite number of 1D-random walkers

Place exactly one random walker at each integer in $\Bbb Z$ and define $Y_n$ as the number of these who are at the origin at time n. Show that $0<\displaystyle\lim_{n\to\infty}P\{Y_n=0\}<1$ and ...
2
votes
0answers
105 views

Spectrum of Transition Matrix for Random Walk

Consider the symmetric random walk on $\{0, 1, \dots, n\}$ with transition probabilities $P(j \to j \pm 1) = 1/2$ for $1 \le j \le n-1$ and $P(0 \to 0) = P(0 \to 1) = P(n \to n) = P(n \to n-1) = 1/2$. ...
1
vote
1answer
146 views

Increasing entropy of random walk in regular graph

Let $P$ be a transition matrix of a random walk in an undirected regular graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
0
votes
1answer
870 views

Probability distribution of a Hitting Time in simple random walk

In order to solve a puzzle in correspondence with a friend, I am using a simple random walk hitting time calculation based upon the reflection principle as it is expressed in this University of ...
1
vote
0answers
76 views

Equilibrium distributions for a finite urn scheme

Given an urn with $n$ (fixed) balls that can be red or black, and given two parameters $0 < p, \, q < 1$, keep doing the following: Flip a $p$-coin. If heads come up, remove a black ball or ...
1
vote
2answers
218 views

A question about random walk in 1 dimension

For a simple random walk problem in 1 D, the expected position of the particle in $n$ step is $E(X_n)=n(p-q)$ so the distance from origin should be $=E(X_n)$ but according to Mean distance from ...
0
votes
1answer
152 views

Recurrent, strongly aperiodic random walk

Assume $(X_n)_{n\geq1} \subseteq \mathbb {Z}$ and $(Y_n)_{n\geq 1} \subseteq \mathbb {Z}$ to be iid, $X_i \sim Y_i$ and such that $S_n=\sum_{i=1}^n(X_i-Y_i)$ is a strongly aperiodic, recurrent random ...