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

2
votes
1answer
78 views

Probability problem with markov property

Problem: In a test paper, the questions are arranged so that 3/4's of the time a True is followed by a True and 2/3's of the time a False is followed by a False. You are confronted with a 100 ...
2
votes
1answer
119 views

Proof that Markov Chains converges to the stationary distribution

Let $P$ is a transition matrix of a Markov Chain, which is irreducible, aperiodic and lets assume $\pi$ is its stationary distribution: $\pi = \pi P$. Does anyone knows the proof for the following ...
2
votes
1answer
336 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 ...
2
votes
2answers
91 views

Continuous-time finite-state Markov chain as a subordinated Brownian motion

I think I read somewhere that every semimartingale is representable as a time changed Brownian motion (sorry, I don't have a reference). This suggests that in particular a continuous-time finite-state ...
2
votes
3answers
104 views

why is this Markov Chain aperiodic

I have this Matrix: $$P=\begin{pmatrix} 0 & 1 \\ 0.3 & 0.7 \end{pmatrix}$$ this markov chain is said to be aperiodic, I dont understand how it comes to it. Period $\delta$ is the gcd of ...
2
votes
1answer
147 views

Construction of positive recurrent Markov chain

Let $\{X_i\}_{i\geq 1}$ be i.i.d. with values in $\mathbb N_0$. Define a Markov chain via the following transition matrix: $$p(0,n) = \mathbb P(X_1 = n-1) \qquad p(m,n) = \mathbb P\left(\sum_{k=1}^m ...
2
votes
2answers
295 views

Finding the exact stationary distribution for a biased random walk on a bounded interval

Imagine we have a biased random walk on an interval $[0, L]$, where the probability of taking a $+1$ step is $p$ and the probability of taking a $-1$ step is $(1-p)$. At the reflecting boundary $0$, ...
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 ...
2
votes
1answer
126 views

Markov Property

this relates to an unanswered question I posted a few days ago: Let $\{ X_t : t = 1, 2, 3 \dots \}$ follow a 2-state Markov chain with transition matrix P. Does the Markov property mean I can break ...
2
votes
1answer
82 views

How does this Markov process involving balls and bins behave?

I have some set $S_1,\ldots,S_k$ ($k \geq 3$) of bins, each initially with $N_0(S_i)$ balls ($N_t(S_i)$ denotes the number of balls in $S_i$ at time $t$). A bin can contain a negative number of balls. ...
2
votes
1answer
102 views

Expected number of jumps in regular jump HMC

Consider a homogeneous Markov Chain $X$ on a countable state space, ie a jump process. It is said to be regular (does not explode) if there are only a finite number of jumps in every finite interval. ...
2
votes
1answer
448 views

Understanding a Markov Chain

I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results. The chain starts ...
2
votes
2answers
180 views

Markov chain basic positive recurrency question

If a discrete markov chain is stationary (as far as I know: doesn't modify itself with time), irreducible (doesn't have transient states) and aperiodic (no periodic states), is it positive recurrent? ...
2
votes
1answer
406 views

Expected time of mouse's survival (stochastic matrix)

In the following wikipedia page explaining stochastic matrices, there is an example with 5 boxes and a cat and a mouse where they jump to a left or right box at every turn and it explains how to ...
2
votes
2answers
591 views

Proof of Markov property for Ehrenfest urn

[the question got downvoted on MO with the recommendation to ask here] In many books Ehrenfest Urn is used as an example of a homogeneous Markov chain, where entries in transition probabilities ...
2
votes
2answers
382 views

Markov Chain: Pensioner Problem

A pensioner receives 2000 dollars at the beginning of each month. The amount of money he needs to spend during a month is independent of the amount he has and is equal to i (i.e. i thousand dollars) ...
2
votes
1answer
78 views

Invariance on the product space

Let us consider two spaces $\mathbb{X},\mathbb{Y}$. For simplicity we put $\mathbb{X} = \mathbb{Y} = \mathbb{R}$. On the product space $\mathbb{S} = \mathbb{X}\times \mathbb{Y}$ we consider a Markov ...
2
votes
1answer
57 views

For finite Markov Chain, time average distribution is always a stationary distribution?

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know ...
2
votes
1answer
35 views

Why left multiplication when it comes to Markov chains?

When working with Markov chains and transition matrices $P$ we multiply from the left, meaning that for example $\mu^{(n)} = \mu^{(0)}P^n$ or that the stationary distribution satisfies $\pi = \pi P$. ...
2
votes
1answer
42 views

probability that a game finishes at $n$th step

A coin is flipped sequentially. The game finishes when the sequence TTH is formed(player X wins) or the sequence HTT is formed(player Y wins). I can find the expected time until absorption by X or Y ...
2
votes
1answer
53 views

Safe small wins vs. risky large wins at roulette

Short statement of problem : Two players play roulette at a casino. They both start with the same initial amount. Each player always plays his favorite bet each time, and stops playing as soon as he ...
2
votes
1answer
27 views

How to get transition matrix of markov process?

I am monitoring a Markov process with ~21 states. I know all the states, initial state and what states transitions can/cannot be, so that zero elements of transition matrix are known. I know the ...
2
votes
1answer
63 views

continuous time Markov chain, something the book does not explain

I have a problem with something in my book, under the chapter of continuous time Markov chains. I will post a link to what the book does. They do something which they seem to take for granted, but I ...
2
votes
2answers
163 views

Mean recurrence time and stationary distribution of a Markov chain?

In a Markov chain is there a theorem relating the existence of the stationary distribution and the mean recurrence time? E.g. impossible for stationary distribution to exist therefore mean recurrence ...
2
votes
1answer
50 views

Coarser cyclic decomposition of Markov chain

For a irreducible Markov chain with period $d$ there is a standard construction which shows that the state space can be partitioned into $d$ sets $C_1, \ldots, C_d$ such that $P(x,y)>0$ only if $x ...
2
votes
1answer
61 views

Can I invert a single row of a very large sparse matrix?

Problem I research electron behavior in organic solar cells and have found a way to recast this problem in terms of a large (n=~60 million) Absorbing Markov Chain that I represent as a sparse matrix. ...
2
votes
2answers
74 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 ...
2
votes
1answer
88 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 ...
2
votes
1answer
54 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 = ...
2
votes
1answer
118 views

If $P$ is an invertible transition probability matrix, does $P^{-1}[i,j]$ have any interesting meaning?

Suppose we have a Markov chain transition probability matrix $P$ that is invertible, i.e., $P^{-1}$ exists. Question: Does there exist a meaningful interpretation of the $(i,j)$ entry in $P^{-1}$? ...
2
votes
1answer
159 views

Markov Chain Ergodic Theorem

Consider a discrete time Markov Chain on countable state space $X_{0},X_{1},\ldots$. Assume that the chain satisfies the Foster Lyapunov criteria, and since it is countable state space chain, we ...
2
votes
1answer
100 views

Confidence intervals on maximum likelihoods of observed data

I observed 400 episodes of nursing care in a hospital. I tracked the movement of the nurses between 5 rooms $A-E$. The maximum likelihood of them moving from room $i\rightarrow j$ is given by: ...
2
votes
1answer
220 views

Two different ways of constructing a continuous time Markov chain from discrete time one

Consider a homogeneous continuous time Markov chain (CTMC) with Markov transition function $p(t)$ and infintesimal generator $G$. Its embeded discrete time Markov chain (DTMC) has its transition ...
2
votes
2answers
184 views

$(X_n)$ an irreducible transient Markov chain. Is $f(x) = \mathbb{P}(X_n = x_0 \text{ for some } n > 0 | X_0=x)$ constant?

Let $(X_n)_{n=0}^{\infty}$ be an irreducible transient Markov chain with countably infinite state space $E$. Let $T_x = \inf\{n > 0 : X_n = x\}$. Let $\mathbb{P}_x$ be probability conditioned on ...
2
votes
3answers
397 views

DTMC : Example of Irreducible Aperiodic Null Recurrent Chain

Can someone give me an example of a Discrete Time Markov Chain (DTMC) which is Irreducible Aperiodic Null Recurrent I know that a Simple Symmetric Random Walk on Integers is Irreducible ...
2
votes
2answers
59 views

Convergence of an Ergodic process

I'm having trouble working through the math of the problem below. I believe the problem as described is an ergodic process. I've written a simple simulation of the problem, that converges to 66.6...6% ...
2
votes
1answer
249 views

Markov Chains - How to calculate prob. a state is visited at least N times? what about Expectation?

In Markov chains, if I was given a transition probability matrix with each of the probabilities specified, then how do I determine the following: 1- Probability that state y is visited at least n ...
2
votes
1answer
70 views

probability equation multiplication understanding

I want to understand this probability equation. I'll be grateful, if someone can help. $$P(\text{Birth})P(\text{Death}) + (1-P(\text{Birth}))(1-P(\text{Death}))$$ The above is the transition ...
2
votes
1answer
187 views

How to tackle markov chains with transition cost?

A simple example would be: I have 3 states, A,B,C The transition matrix for the chain is: ...
2
votes
1answer
194 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
330 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
3k views

Calculating conditional probability for 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 & 0 & 0 \\\ 0 & ...
2
votes
1answer
377 views

Eigenvalues of a infinitesimal generator matrix

Consider a Markov process on a finite state space $S$, whose dynamic is determined by a certain infinitesimal generator $Q$ (that is a matrix in this case) and an initial distribution $m$. 1) Is ...
2
votes
1answer
222 views

Markov Decision Process - Utility Function

Reward R(S) in a Markov Decision Process is a mapping from a State S -> Bounded number. I want to know how a Utility Function is defined for an MDP. I think it has to be a mapping from a sequence of ...
2
votes
1answer
225 views

Comparing two Markov chains

I am interested in the question of the positive recurrence of a Markov chain that (in some sense) converges to another Markov chain known to be positive recurrent. The following is a concrete example ...
2
votes
1answer
162 views

How does the backward/forward algorithm work if there is no end?

I'm using Jason Eisner's spreadsheet to understand HMM more better. There's a box at the top that have a transition matrix. I see the Cold day and Hot day options, but don't understand why there's a ...
2
votes
1answer
938 views

Computing the similarity between two matrices / Monte Carlo analysis

I am studying the article at the following link, http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf Which applies Monte Carlo analysis to a decryption problem. The math is admittedly over ...
2
votes
0answers
22 views

Green's function of a Markov Chain, and maybe of a Feller Process?

How are the Green's functions of a Markov chain related to the notion from PDE theory? For instance, if the Markov chain (i.e. discrete state space) is continuous time, then the Green's function I'm ...
2
votes
0answers
31 views

Geometric ergodicity and mixing - stationary case

I have this theorem: The Markov Chain {$X_n$} is stationary and geometrically ergodic if and only if {$X_n$} is stationary and absolutely regular with $\beta_n=O(\gamma^n)$ for some $\gamma\in ...
2
votes
1answer
62 views

Monotonicity and Convexity of Stochastic Matrices

The definition of stochastic monotonicity and convexity is given by "Stochastic Orders and Their Applications" by Moshe Shaked and George Shanthikumar (1994) as: Let $P = \{p_{i,j} \}$ be a ...