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

3
votes
1answer
109 views

What does a customer see when it begins to be served in $M/M/1$ queue?

In queueing theory, the PASTA (Poisson Arrivals See Time Averages) principle [wiki] justifies $a_n = P_n$ where $$a_n = \text{proportion of customers that find } n \text{ customers in the system when ...
3
votes
1answer
127 views

Proving that Markov Chain Monte Carlo converges

I am trying to understand how the very basic Markov Chain Monte Carlo approach works: We try to approximately calculate the expected value $E_{\pi(x)}[X]$ by drawing sequential samples from a Markov ...
3
votes
1answer
593 views

Sum of two Markov processes another Markov process?

Let $dX_{t} = m_1(l_1-X_{t})dt+\sigma_1 dW_{t}$ and $dY_{t} = m_2(l_2-Y_{t})dt+\sigma_2(\rho dW_{t}+\sqrt{1-\rho^2}dW_{t}^{1})$ where the $m_i$'s, $l_i$'s and $\sigma_i$'s are constants, $\rho \in ...
3
votes
1answer
26 views

The expectation of total number of different states in N time points

[Conditions] (1) An object has K possible states. (2) This object can have only one state at a single time point. (3) The probability of each state at any single time point is 1/K, and each time ...
3
votes
1answer
294 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))$$ $$ ...
3
votes
1answer
662 views

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that ...
3
votes
1answer
1k views

Acceptance probability of Metropolis-Hastings

I am an IT guy writing my masters thesis on MCMC methods for use in predicting the outcome of football(soccer) matches. Right now I am trying to wrap my head around MCMC and Metropolis-Hastings in ...
3
votes
1answer
158 views

what's the generalized approach to this infinite state markov chain problem

Say, a bag has 10 balls, in which 9 are red, 1 is black. Each red ball is worth 1 point, each black is worth 4 points. I have 8 picks from the bag to start with (the bag refills itself after each ...
3
votes
1answer
609 views

Countable state Markov chain: detailed balance consequences

Let $S$ be a countable set and $\pi$ a probability distribution on $S$. A discrete-time Markov chain $(X_n)$ with state space $S$ is said to be in detailed balance with respect to $\pi$ (or simply in ...
3
votes
1answer
1k views

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 ...
3
votes
1answer
96 views

What happens to a regular Markov matrix that has more than one steady state/stationary distribution?

It is known that for a regular Markov matrix $M,$ $M^{n}$ has the steady-state vector as all of its columns as $n \to \infty.$ I learned this in class, but what if there is more than one steady-state ...
3
votes
1answer
298 views

Identifying states in Markov chains

I just started learning about Markov processes and got the following homework question. Classify all the states as recurrent or transient for the Markov chain below $$\begin{matrix} ...
3
votes
1answer
109 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...
3
votes
2answers
58 views

Markov chains diagram - what are the numbers above arrows?

Most if not all articles describe the numbers above arrows as probabilities of a transition in that direction, such as this one, or this one. But here, for example, something really weird is ...
3
votes
1answer
22 views

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it ...
3
votes
0answers
28 views

$ X_n = 2 Y_n + Y_{n+1} $ (non)Markov Chain

Let $Y_1,Y_2,\dots$ be iid random variables with $P(Y_n=0)=1-p,\; P(Y_n=1)=p$ where $p\in(0,1)$. Define $$ X_n = 2 Y_n + Y_{n+1} $$ The question is, whether $\{X_n\}$ is a Markov chain or not. ...
3
votes
1answer
75 views

Markov Property Confusion

I feel like I'm being very dense/employing some sort of circular reasoning, but I'm having trouble understanding the Markov Property. According to Durrett (ISBN-10:1461436141), $X_n$ is a Markov chain ...
3
votes
0answers
39 views

Periodicity of Markov chains under cartesian product

Suppose that you have a finite state Markov chain, with $n$ states and characterized by $p_{i,j}$ the probability of reaching state $j$ from state $i$. Consider the new Markov chain with $n^2$ states ...
3
votes
0answers
114 views

Prove or disprove: If $h$ is harmonic on $E$, then $h$ is constant on each $C_i$

For a general finite Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E$ and transition matrix $P=(p_{x,y})_{x,y\in E}$, not necessarily irreducible, we define the linear space of ...
3
votes
0answers
56 views

Why a positive recurrent Markov chain implies positive limiting probability?

Let $X=\{X_0,X_1,\ldots\}$ be an irreducible, positive recurrent, and aperiodic Markov chain with the state space $S=\{0,1,2,\ldots\}$ then how do we show that the probability $$ ...
3
votes
0answers
40 views

A basic doubt on Markov chain/ergodicity

Consider a finite state (no. of state $N$) Markov chain $\{X_n\}$ (all the random variables are bounded) such that there is a state $i*$ such that $$ \sum_{i=1}^{N}p_{ii*}^{(n)} > 0$$ for all ...
3
votes
1answer
169 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
3
votes
0answers
80 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
3
votes
0answers
164 views

Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition ...
3
votes
1answer
125 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$ ...
3
votes
3answers
449 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 ...
3
votes
0answers
111 views

SLLN of Markov chains .

Let $X_1$, $X_2$,... be a finite state, irreducible and aperiodic Markov chain with initial state $X_0=i$. It is known that \begin{equation} \mathrm{P}\Big\{\lim_{n\rightarrow\infty} ...
3
votes
1answer
309 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 ...
3
votes
1answer
93 views

expected hitting time with two absorbing states

Consider a Markov chain in a finite space and with two absorbing states, each of which is accessible from the other, transient states. Is the expected number of transitions to reach any single ...
3
votes
0answers
130 views

Prove the 2 definitions of the periodicity of Markov Chain are equivalent.

In many textbooks, there are basically 2 ways of defining the periodicity of Markov Chain. One is by partitioning the graph in to subgraph such that transition in one group of state leads to the other ...
3
votes
1answer
203 views

Monotonic convergence of powers of a stochastic matrix

Let $P$ be a stochastic matrix (nonnegative and each row summing to 1). Assuming that $P^n$ converges to $\textbf{1}\pi$ as $n \rightarrow \infty$, where $\pi$ is a row vector (stationary distribution ...
3
votes
0answers
106 views

maximum renewal rate of a Markov chain

Consider a Markov chain $(X_t)$ on a state-space with a countably generated $\sigma$-algebra and assume this Markov chain allows for small sets of order one. This means there exist sets $\mathfrak{S}$ ...
3
votes
0answers
146 views

Generalization of Dobrushin's Ergodic Decomposition for continuous Markov Chains

Let $T$ be the shift transformation. Let $P$ be invariant for $T$ and also define a discrete state space Markov Chain. Let $C_{1},\ldots,C_{n}$ be the connected components of the Markov Chain. It ...
3
votes
0answers
33 views

Name for maximum transition probability

Let $p(x,y)$ denote the transition probability of a markov chain. Similarly, let $p^n(x,y)$ be the n-step transition probability. My question is, is there a formal name for $S(x,y):=\sup_n p^n(x,y)$. ...
3
votes
0answers
66 views

When is this reversible diffusion on the integer lattice non-exploding?

Let $U\in C^{\infty}(\mathbb R^n;\mathbb R)$ and consider a continuos time Markov chain on the scaled integer lattice $\delta\mathbb Z^n$ with jump rates given by $r_{\delta}(x,y) := \begin{cases} ...
3
votes
0answers
264 views

Probability question about change in vending machines; maybe markov chain?

Suppose there are vending machine that sells its goods for $3$. It's known that a third of the buyers use three coins of $1$, a third of the buyers use $2$ and $1$, and the last third use $5$. The ...
2
votes
2answers
70 views

Under what conditions does $(I-N)^{-1}$ exist?

Given an nxn matrix N and $I=I_n$, under what conditions does $(I-N)^{-1}$ exist? On one hand $(I-N)(I + N + N^2 + ...) = (I + N + N^2 + ...) - (N + N^2 + ...) = I?$ On the other hand, $(I-N)(I + N ...
2
votes
1answer
473 views

If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element

A transition probability matrix $P\in M_{n\times n}$ is regular if for some $k$ the matrix $P^k$ has all of its elements strictly positive. I read that this can be tested by using the following ...
2
votes
3answers
480 views

The second largest eigenvalue for Perron-Frobenius matrix

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix. My question: Is there any estimation of the difference between the first and ...
2
votes
2answers
2k views

What values makes this Markov chain aperiodic?

Let the following transition matrix represent a $4$ state Markov chain $$\begin{pmatrix} 0 & a & 0 & b \\ \frac{1}{2} & 0 & \frac{1}{3}+c & d \\ 0 & a & 0 & ...
2
votes
1answer
6k views

Expected number of steps/probability in a Markov Chain?

Can anyone give an example of a Markov Chain and how to calculate the expected number of steps to reach a particular state? Or the probability of reaching a particular state after T transitions? I ...
2
votes
1answer
65 views

Is every PMF on the set of non-negative integers the stationary distribution of some birth-death process?

Let $f(.)$ be a probability mass function on the non-negative integers such that $0<f(n)<1$ and $f(0)+f(1)+...=1$. Then does there exist an irreducible birth-death process with stationary ...
2
votes
2answers
156 views

Using Markov - Chain to find average and probability

Suppose a computer generate a random vector of n positions where each position appears on of the numbers from 1 to n. The generation is performed uniformly on the $n!$ possibilities. In the problem we ...
2
votes
2answers
347 views

Professor has 4 umbrellas, Markov chain and Probability

OK this problem is making me tear my hair out. I need someone to walk me through this in baby-steps method like 1 + 1 = 2. I am trying to figure out what I don't understand. I know this is going to be ...
2
votes
2answers
134 views

Independence of the first passage time of a Markov chain being less than or equal to $n$ and $X_n$

I am reading my lecture notes on Markov chains, and in the proof of one proposition the following statement is made: "For $n = 1,2, \dots$ the event $\{n \leq T_k\}$ depends only on $X_0, \dots, ...
2
votes
2answers
55 views

Is there a proof that the observations of a hidden Markov chain is not itself a Markov chain?

Suppose $\{X_n\}$ is the hidden Markov chain, and $\{Y_n\}$ is the series of observations, where $\mathbb{P}\{Y_n = j| X_n = i\}$ is the same for all $n$ (please correct me if I have not stated the ...
2
votes
1answer
606 views

example of irreductible transient markov chain

Can anyone give me a simple example of an irreductible (all elements communicate) and transient markov chain? I can't think of any such chain, yet it exists (but has to have an infinite number of ...
2
votes
2answers
2k views

Markov chain with infinitely many states

I understand that a Markov chain involves a system which can be in one of a finite number of discrete states, with a probability of going from each state to another, and for emitting a signal. ...
2
votes
2answers
2k views

Can Markov Chain state space be continuous?

I looked for a formal definition of Markov chain and was confused that all definitions I found restrict chain's state space to be countable. I don't understand purpose of such a restriction and I have ...
2
votes
1answer
458 views

Markov Process: Have you seen this notation and do you know what it means?

Ok, I've already posted this a minute ago, but my text deleted itself while I was editing it :-( So next try: Can you help me to understand the notation my professor uses to describe Markov ...