1
vote
1answer
20 views

rate of convergence of absorbing markov chain

Let $G$ be a biconnected and non-bipartite graph. I can simulate a random walk on this graph with a markov chain. The stochastic matrix is $M = AD^{-1}$, where $A$ is the adjacency matrix of $G$ and ...
3
votes
0answers
31 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
0
votes
0answers
16 views

Random Walk Prediction on a grid using markov chain

We have a m*n Grid and n no of robots in that grid which would perform a random walk simultaneously.Each robot can move in 4 direction specifically Up, Left, Down, Right. After x steps the random ...
0
votes
0answers
62 views

proving null recurrence of random walk (Markov chain)

How would I prove that the zero state of a random walk with a positive probability of staying in the same state is null recurrent. (sorry if this isn't a random walk and just a Markov chain.) eg. ...
2
votes
2answers
40 views

Generate random sample with three-state Markov chain

I have a Markov chain with the transition matrix $$\pmatrix{0 & 0.7 & 0.3 \\ 0.8 & 0 & 0.2 \\ 0.6 & 0.4 & 0}$$ and I would like to generate a random sequence between the three ...
3
votes
1answer
59 views

Random walk where increment depend on current position

Consider the following stochastic process, $$b(i+1) = b(i) + \xi_i (b_i),$$ where $\xi_i(b_i) \in \{-1, k \}$ are the independent increments having the following distribution: $$\begin{align} P (\xi ...
1
vote
1answer
78 views

First step analysis on random walk

Let us consider random walk on integers {0,1,...,N} where $P(N,N)=1$,$P(0,1)=1$, $P(N,N-1)=0$ and all other connections have probability $\frac{1}{2}$. Using first step analysis, compute $p_{00}$ for ...
4
votes
1answer
76 views

random walk in a certain environment

Consider the following random walk in one dimension, starting from $r(0)=0$. $$ r(i+1) = r(i) + \xi, $$ where $\xi(i, r(i))$ is an increment with distribution $P(\xi=1) = \frac{c^{r(i)}}{i-r(i)+1}$ ...
1
vote
0answers
22 views

Prove equilibrium theorem without irreducibility and aperiodicity

I have to solve the following question: Consider a random walk Markov chain on $S = \{1, 2, \ldots, 100\}$. If the chain is between 2 and 99, it selects one of the adjacent states with equal ...
0
votes
1answer
52 views

Random walk with weighted probabilities

Taking a walk on $\mathbb{N}$, starting at 1, I need to find out how many steps I expect to take before returning to the origin, as a fraction. For each step, I either walk forward, backward, or stay ...
0
votes
2answers
56 views

How Do You Calculate Probabilities of Random Events Occuring in Sequence?

So I have a series: $f(x_{n+1})=x_n \pm t$ and $f(x_0)=W$ What I'd like to calculate is the probability in terms of $t$ and $W$ (assuming they're any constant $W>t$) that any $f(x_q)=0$ for all ...
4
votes
2answers
109 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
0
votes
0answers
13 views

why $d$-dimensional symmetric random walk is not recurrent for $d \geq 3$

I want to understand why $d$-dimensional symmetric random walk is not recurrent for $d \geq 3$. I am not finding any good resource for this. Can someone help here ?
1
vote
0answers
52 views

A matrix-multiplication random walk

Let $x \in \mathbb{R}^n$. Consider an $n\times n$ matrix $A$. Suppose we're interested in how $||A^nx||$ grows with $n$, the answer (excluding pathological cases) is that it scales exponentially with ...
2
votes
2answers
67 views

Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice. If we consider a particle starting ...
0
votes
0answers
30 views

How to perform a stochastic search of the locality of a node in a network?

In a graph that may be a random graph (ER graph), scale free network, etc. I would like to obtain a distribution of the locality of the nodes surrounding a ...
2
votes
1answer
253 views

Expected time for winning in biased Gambler's Ruin

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,n\}$ with absorbing states $A=\{0,n\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where ...
1
vote
1answer
171 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
1
vote
1answer
61 views

Absorbing state for a collection of random walks

Further to this question; having learned some stuff since I posed it. Consider a collection of random walks $X_i$ which take finite integer values. These evolve as time-inhomogeneous Markov Chains. ...
0
votes
1answer
211 views

Coin toss probability calculation

A gambler bets on coin flips. With each flip, he wins $1$ dollar with probability $p$, and loses $1$ dollar with probability $1-p$. He starts with $2$ dollar and stops when he reaches either $0$ or ...
1
vote
1answer
119 views

Random walk probability non-symmetric steps

I currently have a probability class tutorial question that I have no idea where to begin. At first instinct, I thought it may have been a CTMC question or branching question, but now I have no idea, ...
4
votes
0answers
122 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 ...
0
votes
2answers
532 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
114 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
237 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
171 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 ...
4
votes
2answers
364 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, ...
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
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
440 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 ...
3
votes
2answers
930 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 ...
1
vote
2answers
123 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 ...
0
votes
0answers
72 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
265 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 ...
5
votes
1answer
329 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
151 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 ...
1
vote
1answer
59 views

Absorbing time in $0$ of a simple left-drifted Markov chain on non-negative integers

Let $M$ denote the Markov chain on states $\{0, 1, 2, ...\}$ with absorbing state $0$. For $i \geq 1$, let the transition probabilities be $p$ for $(i, i-1)$ and $1-p$ for $(i, i+1)$. Further, assume ...
0
votes
0answers
73 views

Martingale with reflecting barrier

I am not very familiar with the theory of martingales or random walks, perhaps someone could point me in the right direction or give me some help with the following problem. Consider a random ...
0
votes
1answer
289 views

Why is a random walk a time-homogeneous Markov process?

Why is a random walk on $\mathbb{R}^d$ (see below) a time-homogeneous Markov process? Specifically, why does it satisfy requirement #2 of definition 17.3 that the map ...
2
votes
1answer
183 views

Random walk on finite graph

I know that the stationary distribution of a random walk on the graph is given by, (degree of the node)/($2\times$ total number of links in graph). My question is, how do we get this solution?
2
votes
1answer
303 views

Non-symmetric simple random walk stopping time

Say there is a random walk $\{S_n\}$ with $S_0=0$ and $0<p=P(S_1=1)<\frac{1}{2}$. We know such a random walk would go to $-\infty$ eventually. Define the stopping time $T=\inf\{n: S_n=-\infty\}$, ...
2
votes
2answers
238 views

What does it mean for MCMC to converge?

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will ...