Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

learn more… | top users | synonyms

0
votes
1answer
62 views

Application of CLT to random walks

Let $X_1,X_2,\ldots$ be an iid sequence such that $P\{X_1 = 1\} = p$, $P\{X_1 = -1\} =p$ and $P\{X_1 = 0\} = 1-2p$. We have that $E[X_1] = 0$ and $E[X_1^2] = 2p$. Define $S_n = \sum_{i=1}^nX_i$ and $...
0
votes
0answers
35 views

Finiteness of the hitting time of random walk

Let $X_1,X_2,\ldots$ be an iid sequence such that $P\{X_1 = 1\} = u$, $P\{X_1 = -1\} = d$ and $P\{X_1 = 0\} = 1-(u+d)$. We have that $E[X_1] \neq 0$. Define $S_n = \sum_{i=1}^nX_i$ and $S_0 = 0$ and ...
0
votes
0answers
52 views

Ergodic Theorem for Markov Chain with one closed communicating class and several transient states

It is known, that if a markov chain with a finite state space has only one closed aperiodic communicating class and several transient states, then there is a unique stationary distribution for this MC....
2
votes
2answers
94 views

Convergence of mean of an irreducible Markov chain / ergodic theorem

Let $\{X_n\}$ be an irreducible Markov chain on a discrete state space $\mathbb{N}$, that has a stationary distribution $\pi$. Prove or disprove : with probability $1$: $$\lim_{n\rightarrow +\...
1
vote
1answer
55 views

Markov Chain Questions

I've been stuck on these problems for a while. I keep banging my head against the wall, but my calculations are incorrect each time. I sum the probabilities together for each possibility (it's a ...
1
vote
0answers
30 views

Transform Markov chain that doesn't have stationary transition probabilities to one that does?

This question concerns Exercise 7.3 in Walsh's Knowing the Odds. A Markov chain is defined as having stationary transition probabilities if for all $i, j, n$ we have $P(X_{n+1} = j \mid X_n=i) = P(...
0
votes
1answer
34 views

Number of $1's$ in a string in terms of successive pairs

Problem. Let $X_n=0$ or $1$ and set $Y_n=(X_n,X_{n+1})$. Set also $\displaystyle \sum_{k=1}^{n}\mathbb{I}_{\{X_k=1\}}$ be the number of times $X_k's$ become $1$, from $X_1$ till $X_n$ ($\mathbb{I}_{A}$...
1
vote
2answers
65 views

Non-symmetric random walk on $\mathbb{Z}^2$

a random walker, walks on a lattice with non-negative coordinates. In each step, if he is in a positive coordinate, say $(a,b)$ where $a,b>0$ he will go to $(a-1,b)$ or $(a,b-1)$ with same ...
0
votes
1answer
34 views

What does it mean $f \mu$, when f is a function and $\mu$ a measure?

Let $f$ be a function and $\mu$ a measure. I saw in Revuz's $\textit{Markov Chains}$ the following notation: $$f \mu$$ What does it mean? Thank you!
0
votes
1answer
43 views

calculating limit of a markov chain

I want to calculate the following limit $lim_{n \to \infty}\ A={\begin{bmatrix}1 & 0 &0 & 0&0\\1-p & 0 & p & 0&0\\0 & 1-p & 0 & p&0\\0&0&1-...
1
vote
1answer
53 views

A fair die is thrown repeatedly until we obtain the same number twice in a row.

A fair die is thrown repeatedly until we obtain the same number twice in a row. Compute the expected number of throws. For this, I found $6$ finding the transition matrix and using first step ...
0
votes
0answers
24 views

Markov Chain, probabilities of future generations

Suppose the number of daughters of a woman is 0, 1, 2, or 3 with respective probabilities 0.3, 0.4, 0.2, 0.1. Suppose further that the number of daughters of each of her descendants has the same ...
5
votes
1answer
55 views

Branching Process: generation survival or extinction?

Let $p\in [0,1]$, and consider a branching process where the number of offspring of an individual is zero with probability $p$, and is two with probability $1-p$. Initially there is one ...
0
votes
0answers
41 views

Time to absorption for infinite state Markov chain

I have a Markov chain with a single absorbing state $s_{-1}$. The transient states have absorption probabilities $p_{i,-1} = 1-f_i$ and transition probabilities to the next state $p_{i,i+1} = f_i$. We ...
0
votes
1answer
36 views

Relating the stationary distribution of an ergodic Markov chain to its mean return time

Let $X_t$, $t=0,1,2...$ be an ergodic Markov chain on $S=\{1,...,n\}$ with transition matrix $P=\left(P_{ij}\right)_{i,j\in S}$. Let $T^i=\inf\{t\geq1:X_t=i\}$ and $h_j^i=\mathbb{E}\left(T^i\right\...
0
votes
0answers
92 views

Expected infimum of a 1d random walk

Consider a simple symmetric random walk on $\mathbb{Z}$ starting from $0$, $S_n$. Let $I_n := \inf\{S_0, S_1, S_2, \ldots S_n\}$. Is an explicit formula for $E[I_n]$ known?
2
votes
0answers
53 views

Limiting products of realizations of an integer-valued Markov chain

Let $(X_m)$ be a finite space discrete time irreducible and aperiodic Markov chain with stationary distribution $\pi$. The state space is a finite set of positive integers $\{x_1, x_2, \dots, x_l\}$. ...
1
vote
1answer
30 views

Irreducible and recurrent Markov chain - theorem notation question

In [J. R. Norris] Markov Chains (Cambridge Series in Statistical and Probabilistic Mathematics) (2009), page 35, Theorem 1.7.5 says: In (ii), does it mean $\gamma^k$ is notation for $\gamma^k_i$ ...
1
vote
1answer
148 views

Stochastic Markov Chain Application: Rat in the maze problem, a modification

I am really new to Stochastic processes, and this is one of the supplementary practice questions that I stumbled across whilst studying: Modify the situation as described in http://www.ucl.ac.uk/...
0
votes
0answers
11 views

Alternated Ehrenfest Chain (Welfare Distribution)

Consider a simple wealth distribution model with two trading agents. Let N denote their total wealth (represented by balls of two colors, black and white). At each time the agents may trade, i.e. we ...
1
vote
0answers
20 views

Two Markov chains $X_t$, $Y_t$ have the same transition matrix $P$, show $\Bbb P(\tau_c\le t_0) = \Bbb P(\tau_c\le 2t_0|\tau_c> t_0)$

Given two Markov chains $X_t$, $Y_t$ characterized by the same transition matrix $P$, let $\tau_c$ be the first time the two chains have the same state, i.e. $\tau_c = \min\{t:X_t=Y_t\}$. The ...
0
votes
1answer
28 views

Symmetric Simple Random Walk - Definition Clarification

I'm finding conflicting answers everywhere, including in my own notes. In the phrase "symmetric simple random walk", which part, "symmetric" or "simple" refers to having a probability of $0.5$ to go ...
1
vote
1answer
37 views

regular Discrete Time Markov Chains

I have a transition matrix $P$. I know that $P$ is regular if all $p^{(n)}_{ij}>0$ for some $n \geq 1$. Is there an algorithm that can help me to verify whether $P$ is regular without calculating $...
1
vote
0answers
19 views

Is this the same thing as some simple discrete probability distribution?

I want to count the number of trials until one success in a sequence where the success probability is increased with each failure. For each trial, the success probability is $1-\binom{k+1+i}{k-1}^{-1}$...
2
votes
1answer
55 views

Given two biased coins, the probability of obtaining heads on the $i^\text{{th}}$ toss using the following strategy?

We are given two coins: A and B with probability of obtaining heads being: $\alpha$ and $\beta$ respectively. The following sampling rule is used for i=1,2,...: If the $i^{\text{th}}$ toss results in ...
1
vote
1answer
21 views

Why does this MCMC algorithm to estimate parameters of a linear equation not converge to the posterior distribution?

As a kind of proof of principle I'm trying to estimate the parameters of a linear equation (before moving on to ODEs) using Markov Chain Monte Carlo sampling. The post that I am following can be found ...
2
votes
1answer
93 views

Showing a queueing system is a Markov Chain

I generally understand how to do this but I'm having trouble with a formal proof. "Consider an $M/M/1/m+1$ queue with exponential arrivals rate $\lambda$, exponential service rate $\mu$, and finite ...
0
votes
1answer
119 views

Markov chain: molecules in urns

I am struggling to get started on this question. I think I am confused at what the transition matrix is suppose to represent. So I know the matrix is going to have this form: $$ \begin{vmatrix} P_{...
0
votes
1answer
103 views

Markov Chain Snakes and Ladders

I am really stuck on the following question: So first I need to work out the transition matrix. But I am not sure how? Lets say I am at square 0 and I want to square 1, is the probability of moving ...
0
votes
1answer
35 views

If $X$ to $Y$ to $Z$ is a Markov chain, prove or disprove $H(Y\mid X)\le H(Z\mid X)$

If $X \to Y \to Z$ is a Markov chain, prove or disprove $H(Y\mid X)\le H(Z\mid X)$. I said the statement was true, and from $I(X;Y)\ge I(X;Z)$ by definition, thus $H(X) - H(X\mid Y) \ge H(X)-H(X\mid ...
0
votes
0answers
45 views

Normalisation of an invariant measure

Is there an example of a Markov chain with invariant measure $\pi$ and $\sum_{i \in I}\pi(i) = \infty$ that can be normalised so that we can consider an invariant distribution instead? This is a ...
0
votes
0answers
25 views

Most visited vertex in a random walk with a place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
1
vote
1answer
307 views

Gambler's Ruin and Markov Chains

Suppose that on each play of a certain game, a person will either win one dollar with the probability of $\frac{2}{3}$ or lose one dollar with probability $\frac{1}{3}$. Suppose also that the person's ...
1
vote
1answer
60 views

Markov DTMC and CTMC: How to build a $Q$ generating matrix using given $2$ state $q$ probabilities? Find Steady State Probabilities

I know that $$q_{(i,j)(i+1,j)}=\lambda_1$$ $$q_{(i,j)(i-1,j+1)}=\lambda_2$$ $$q_{(i,j)(i+1,j-1)}=0.5\lambda_3$$ $$q_{(i,j)(i,j-1)}=0.5\lambda_3$$ where $\lambda_1 , \lambda_2 , \lambda_3 $ are rates ...
4
votes
1answer
36 views

Getting all positive integer solution (All possible states of a chemical system) to undertermined linear system (Conservation law from stoichiometry)

Let a chemical system be defined as $${A<=>B<=>C}$$ Then the stoichiometry is given as $$S=\begin{bmatrix} -1& 1& 0& 0\\ 1& -1& -1 & 1\\ 0 & 0 & 1 &-...
0
votes
1answer
49 views

How many stationary distributions does a time homogeneous Markov chain have?

I've been given the following definition: For a THMC with one step transition matrix $\mathbf{P}$, the row vector $\mathbf{\pi}$ with elements $(\pi_{i})_{i \in S}$ (where $S$ is the state space) ...
0
votes
1answer
28 views

Distribution of Markov Chain with transition matrix

An optional challenge assignment: Given a stationary Markov chain $\mathbf X=(X_k)^\infty_{k=1}$ where $X_k$ takes values in {0,1,2}. Let it have a probability transition matrix $P=[P_{ij}]=Pr(X_{k+1}=...
1
vote
0answers
30 views

Probability that sample path ends at a high.

I am trying to get the probability that a sample path ends at a high. To formulate the problem, let sequence $\{S_n\}$ be a random walk, with $S_0 = 0$, defined by $$ S_n = \sum_{k=1}^n X_k$$ Where $...
1
vote
1answer
35 views

Invariant measure nomenclature

I'm looking through my notes and I've come across the following line: If $\sum_{i \in I}\pi(i) = \infty$ then we (usually) say that the Markov chain doesn't have an invariant distribution. My ...
0
votes
0answers
18 views

DTMC and CMTC , First Passage Probabilities and Expectation.

Let the sample space $S=(0,1,2)$. Let $Q=\begin{pmatrix} -4 & 2 & 2 \\ 3 & -5 & 2 \\ 0 & 3 & -3 \\ \end{pmatrix}$ be the generator of our CTMC. ...
0
votes
0answers
45 views

Markov chain matrix multiplication - Finding all path probability in a graph

I realize there are many Markov Chain questions on this site. I have reviewed all relevant questions, the closest to my question are: Finding the probability from a markov chain with transition matrix ...
0
votes
1answer
43 views

Markov Chains: Finding the Embedded DTMC $P(t)$ from generator matrix $Q$

Markov Chains: Finding the Embedded DTMC (transition probability matrix) $P(t)$ from generator matrix $Q$ where the sample space $S=(0,1,2)$ $Q=\begin{pmatrix} -4 & 2 & 2 \\ ...
0
votes
1answer
17 views

How many stationary measures does a random walk with absorbing barriers have?

Suppose I have a markov chain with finite state space $0,\ldots, N$. At each state $1, \ldots, N-1$, we have that the probability of going up and down one state is of probability $\frac{1}{2}$. Now, ...
1
vote
1answer
22 views

What is an example of a Markov Chain with two stationary measures?

I am trying to come up with a transition matrix for a Markov Chain with two stationary measures, but am not able to construct it. Would anyone have an example? Thanks.
0
votes
1answer
21 views

Stochastic Kernel almost surely determined by semidirect product?

Given a measurable space $(\Omega, \mathcal{F})$ with two probability measures $\mathbb{P}_1$, $\mathbb{P}_2$ and a second measurable space $(X,\mathcal{A})$ with two stochastic kernels $\mu_1, \mu_2$ ...
1
vote
0answers
18 views

marginalised markov chain

If there is a Markov chain for the joint variable $z=(x,y)$, the marginal process $x$ is not, in general, Markovian itself. However, if we consider the probability of a two time step process $$p(z_0,...
1
vote
0answers
42 views

What is the invariance principle of Random Walks?

Several papers I have read allude to the fact that a random walk is invariant; however, I have been unable to find any reference to support this fact. Could anyone explain why random walks are ...
1
vote
0answers
52 views

Finite irreducible Markov chain

The question I have is stated as follows: Show that for any finite-state irreducible Markov chain $$\max_{i,j}\mathbb E_iT_j\le C$$where the constant $C$ only depends on the number of states and $\...
0
votes
1answer
34 views

Create a transition table

I am trying to create a transition table for a markov chain but I have difficulties. Consider a game, where each player (of two, lets call them A and B) has a fixed given probability of scoring 3 ...
0
votes
1answer
56 views

Sampling uniform equilibrium distribution with Markov Chain Monte Carlo

I'm wanting to sample the discrete uniform distribution over $n = 10$ integers using MCMC. My question concerns the transition probability matrix, $P$. As I understand it, any symmetric, irreducible ...