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

1
vote
1answer
60 views

State space reduction of a CTMC

I have a CTMC with six states $\{0,1,\ldots,5\}$. It turns out that states 3 and 4 are equivalent and so are states 1, 2 and 5. I would love to clump equivalent states into one. $$Q_1=\matrix {& ...
0
votes
1answer
20 views

What is the difference between a communicating class and a closed communicating class?

I checked the definition on Wikipedia http://en.wikipedia.org/wiki/Markov_chain#Properties I couldn't see any difference.
1
vote
1answer
44 views

Finding the general pattern form

Suppose a Markov chain given as follows. $p_{ii}=1-3a$ And $p_{ij}=a\ \forall i\ne j$ where $P=(p_{ij}), 1\le i,j\le 4$. Find $P_{1,1}^n$. Attempts: I have tried to compute for the case $n=1, 2, 3$. ...
0
votes
2answers
264 views

Exercise 1.3.2 of Norris, “Markov Chains” [closed]

I'm working my way through Norris's classic textbook, but I'm having problems with this hitting probability question: "A gambler has £2 and needs to increase it to £10 in a hurry. He can play a game ...
1
vote
1answer
62 views

Markov Chain: starting at $i$ reaching $N$ before $0$

Starting at some state $i$, we have probability of going $P_{i,i+1} = p$ and probability $P_{i,i-1} = 1-p$ what is the probability I reach N before I reach zero? Can I convert this to a gambler's ...
1
vote
1answer
78 views

Markov chains: simple random walk $S_n$

In the case of a simple random walk $\{S_n, n \ge 0\}$ what is $S_n$. I see this for $P\{S_n=i |\ |S_n|=i_{n-1},...,|S_1|=i_1 \} = \frac{p^i}{p^i+q^i}$ What does this mean? is it: the probability ...
1
vote
1answer
100 views

Markov Chain Solution Eigenvalue

I am having trouble understanding how to solve for the state vector at time $t$ for a markov chain using matrix algebra. I have the following Markov Transition Intensity Matrix, for the states A, N, ...
1
vote
0answers
80 views

Rate of convergence of $n$-fold convolution over $\mathbb{Z}_p$.

Suppose that $\mu$ is a probabilist measure on $\mathbb{Z}_p$ such that $d_{TV}(\mu,\mu_U)\leqslant \delta < 1$. What are the best upper bound on $$ d_{TV}(\underbrace{\mu*\mu*\ldots*\mu}_{n ...
3
votes
1answer
177 views

Markov Chain Initial Distribution

Suppose $\{X_0,X_1,X_2,\dots\}$ is a discrete-time Markov chain taking values in a finite set $\{1,\dots,N\}$ with initial distribution $p_i(0) = P(X_0 = i)$ for $i\in\{1,\dots,N\}$ and transition ...
1
vote
1answer
85 views

Transition Matrix $P$ of a Linear Birth-Death process

I am working on a problem where I have to prove that $P_{20}(t)=P_{10}^2(t)$, given that I have a linear Birth and death process: i.e. $\lambda_n=n.\lambda$ and $\mu_n=n.\mu$. I think the solution ...
1
vote
1answer
84 views

Hitting Time Markov Chain

Let$\left\{{X_{n}: n\in \mathbf{N}}\right\}$ be a Markov Chain in discrete time, with the hitting time being defined as $\displaystyle H^A=\inf\left\{{n\geq 0 : X_{n}\in A}\right\}$. Assuming $i\not ...
3
votes
1answer
117 views

Dice probability of a winning more than $X\%$ of the time over $Y$ Throws

I have a die with three possible outcomes. The three outcomes are win (+1), draw (0) and lose (-1). $P(w) + P(d) + P(l) = 1$. (1) If I throw the die Y times, what is the probability I will win $X$ ...
1
vote
1answer
80 views

Conditioning a CTMC on the future on a Yule pure birth process

I need to solve a problem where I am asked to calculate $M=P(X(0)=2|X(1)=3,X(2)=4,X(3)=5)$ in a Yule pure birth process where $\lambda=1$, so $\lambda_n=\lambda.n=n$ and $\mu_i=0$ (the death rate is ...
1
vote
0answers
102 views

First and second moments of recurrence time in a finite two-dimensional Markov chain

I have a two dimensional finite Markov chain with $(m+1)^2$ states, and with transition rates: $q_x((x,y)\to (x+1,y))=(m-x)\lambda,\quad 0\leq x< m, 0\leq y \leq m$, $q_x((x,y)\to ...
1
vote
0answers
46 views

Finding Steady state using markov chains. Am I right?

Suppose that there are two doctors in a country town, Dr Black and Dr White. Each year, 13% of patients move from Dr Black to Dr White, while 19% of patients move from Dr White to Dr Black. Suppose ...
1
vote
2answers
281 views

What is the difference between the forward and backward equations in a CTMC?

Given that the Forward equation in a CTMC (Continuous Time Markov Chain) is: $P'(t)=P_t G$, and the Backward equation is: $P'(t)=G P_t$, which equations should I use of the two depending on the case I ...
0
votes
1answer
116 views

Transition probability in Continuous Time Markov Chain (CTMC)

I know that for a CTMC, the transition matrix $P(t)=e^{tQ}$, where $Q$ is the infinitesimal generator matrix of the irriducible CTMC. My question is how do I deal with situations or problems that ask ...
2
votes
1answer
96 views

Markov chain and hitting times

I have a Problem about hitting times. That's the following: Let $A\subset E$ and the first passage time $T_A$ and the hitting time $H_A$. Define: $T_A =\inf\{n\geq 0;X_n \in A\}$ and $H_A ...
0
votes
1answer
48 views

Coupon collector's problem as Random Walk

I see in a book the following as coupon collector's problem. We have $N$ coupons labelled $1,2,\dots,N$ from which we pick with replacement. I could not understand what is the random walk here.
1
vote
1answer
195 views

Markov Chain, closed, recurrent states

There are two urns, with the first one containing three white balls and the second one containing three black balls. At each step, we draw a ball from each urn, and then put the ball drawn from the ...
2
votes
1answer
61 views

A doubt on $d$-dimensional random walk

Consider a $d$-dimensional random walk with equal probabilities in each of the $d$-directions (so, $p(v_i,v_j)=\frac{1}{d(v_i)}=\frac{1}{2d}$ here. Now, suppose the walker takes $2n$ steps. Now I have ...
1
vote
0answers
80 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 ...
0
votes
1answer
69 views

Irreducible Markov chain

Consider an irreducible Markov chain with an invariant distribution $\pi$. Then show that if $\pi(x)>0$ for some $x \in S$, where $S$ is the state space, then $x$ is recurrent. Here's what I was ...
1
vote
1answer
70 views

Calculating cumulative Markov Chain outcomes

I have a Markov process, with 2 possible states (1 or 0) and a transition matrix P. State at time t=n is determined by x0*Pn. As n goes to infinity, xn goes to the steady state vector, q = [q1 q2]. ...
2
votes
2answers
94 views

Expected value of a series of random variables in a markov chain

I have a Markov Chain such that $X_n = \max(X_{n-1}+\xi _n,0)$ where the $\xi_n$ series is independent and identically distributed. I want to show that if $\mathbb E(\xi_n) > 0$ (where $\mathbb ...
1
vote
1answer
83 views

Intuition behind Gambler's Ruin Problem Solution

In case of gambler's ruin (fair) the probability that a process starting at state $j$ eventually will reach state $N$ before state 0 is $\frac{j}{N}$. I understand that it should be proportional to ...
1
vote
1answer
54 views

A basic doubt on Markov Chain / Conditioning

Suppose we want to calculate $n$-step transition probability of a Markov chain conditioned on the fact that it does not pass through some particular state. Can I do this by removing that state from ...
0
votes
1answer
36 views

A basic doubt on some submatrix consisting of transient states of a stochastic matrix

Consider a submatrix of a stochastic matrix where all the states are transient. So, $ Q^n\to 0$ which is clear to me. But why this implies that all of the eigen values of $Q$ have absolute values ...
0
votes
1answer
37 views

Does a Markov Blanket allow connections between Parents of a Node?

In a Markov Blanket, we can connect the childredn of a node between them, as a child can be parent (or spouse) of another child. Does this rule apply as well for Parents of a node? In advance, Thank ...
0
votes
2answers
499 views

Markov chain: closed, finite classes are recurrent?

In Norris: Markov Chains the closed class C is defined as one for which $i\in C$ and $P_i(X_n=j \text{ for some }n\ge0)>0$ implies that $j\in C$. Here's theorem 1.5.6 from the book with proof ...
1
vote
1answer
581 views

What is the transition matrix and stationary distribution of ${T}$

Let $T = (X_n:n \in \mathbb{N})$ denote a homogeneous Markov chain with state space $E=\lbrace 1, 2, 3\rbrace$ and $$\mathbb{P}(X_1=2\vert X_0=1) = \mathbb{P}(X_1=3\vert X_0=1)=\frac{1}{3}$$ as well ...
3
votes
1answer
251 views

A basic question on irreducible periodic markov chain

For an irreducible periodic (period $2$) Markov Chain I know that both of the following two quantities are same and equal to $\pi(i)$: $$ \lim_{n\to \infty} \frac{1}{2}(p_n(j,i) + p_{n+1}(j,i))$$ $$ ...
1
vote
1answer
88 views

Are there open questions in Markov chains?

I would be curious to know if there's still open question about discrete markovian chains
0
votes
1answer
80 views

Eigen value of TPM for an irreducible markov chain with period $d > 1$

For an irreducible periodic Markov Chain with period $d >1$, the transition probability matrix will have $d$ eigenvalues with absolute value 1. Why ?
0
votes
1answer
70 views

Generating Markov Chains recursively

$X_0:\Omega\rightarrow I$ is a random variable where $I$ is countable. Also $Y_1,Y_2,\dots$ are i.i.d. $Unif[0,1]$ random variables. Define a sequence $(X_n)$ inductively as $X_{n+1}=G(X_n,Y_{n+1})$, ...
2
votes
1answer
118 views

What is the difference between positive presistent and null persistent state in a Markov Chain?

I'm not looking for the difference in the mathematical definition, but rather for an intuitive explanation of their differences and possible examples, so that I can have them in my head when ...
0
votes
1answer
173 views

Most likely path through a continuous time Markov chain

If I have a discrete Markov chain, it's easy to find the most likely path through it: just look at the probabilities of following each possible path independently, and take the largest one. In a ...
0
votes
1answer
83 views

Decision theory question about selling a house

I have a real world problem and I was wondering if you guys have any nice insight on the best way to solve it mathematically. I'm not sure there is a decisive solution, but it would be nice to have a ...
0
votes
1answer
111 views

Need help in understanding state transition diagram of a convolutional coder. How are the output bits calculated?

Have a look at the above figure. I am confused in how the output bits are calculated. e.g. according to my understanding a state transition from 00 to 10 (with input bit 1) should produce output 10 ...
0
votes
0answers
115 views

Markov chains, limiting distribution and periodicity

My textbook on Markov chains has theorems on when a chain has a unique limiting distribution, but not the other way around, i.e. when a chain does not have a limiting distribution. My question is the ...
0
votes
1answer
60 views

Stochastic matrix with structure

Let $P \in [0,1]^{(n \times n)}$ be a stochastic matrix i.e $P_{ij} > 0 ~ \forall i,j$ and $\sum_{j}P_{ij} = 1~ \forall i$. Now let us impose additional structure on $P$ by saying that $P_{ij} + ...
0
votes
0answers
88 views

Markov Chains Proof using Statistics

Source: This came from "Introduction to probability" by Charles Miller Grinstead, and James Aurie Snell. It was located on page 407 and is Theorem 11.1 in the section 11.1 Introduction. Theorem: The ...
2
votes
0answers
73 views

simple proof of the $L^2$ weak law for discrete-time ergodic Markov processes

Let $\{X_t\}_{t\in\mathbb{Z}}$ be a stationary and ergodic stochastic process with finite second moment. Von Neuman's ergodic theorem implies that the time average $(1/N)\sum_{j=0}^{N-1} X_j$ ...
0
votes
2answers
87 views

Discrete Markov Transition Matrix

Well, I've been reading over the internet but I've been unable to find a straight answer. I've got a transition matrix for a Markov Discrete Chain. I've made the graph and according to my knowledge, ...
2
votes
2answers
75 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 ...
1
vote
1answer
96 views

Why Gibbs sampling needn't “remixing”

I am generating $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \dots, \mathbf{x}^{(n)}$ using Gibbs sampling methods. So I want $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \dots, \mathbf{x}^{(n)} \sim$ some ...
2
votes
1answer
56 views

Elementary probability question (Random walks)

Given a random walk $X_{t \ge 0}$ on $\mathbb{Z}$ starting at $0$ with probabilities $P(n, n + 1) = p$ and $P(n, n - 1) = 1 - p$, let $Y = \min\{X_0, X_1 \dots \}$. What is the probability that $Y = ...
0
votes
1answer
221 views

What values of $p$ make this a transient chain?

Suppose we have a Markov chain with state space $S = \{0, 1, 2, \dots \}$ and probabilities $p(x, x + 2) = p$, $p(x, x - 1) = 1-p$ for $x > 0$ and $p(0, 2) = p$ and $p(0, 0) = 1 - p$ I would ...
1
vote
1answer
197 views

How to show that this process is a Markov chain?

This question is from DEGROOT's "Probability and Statistics". Question: Suppose that a coin is tossed repeatedly in such a way that heads and tails are equally likely to appear on any given ...
1
vote
1answer
49 views

makov chains and property

let $X_t$ for $t \in \{1,2,...,10\}$ be a sequence of independent tosses of a fair coin. We denote heads with 1 and tails with 0. Define the random variable $S_n=\sum_{t=1}^n X_t$ for $n \in ...