Questions tagged [markov-chains]

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.

A Markov chain is a stochastic process on a discrete (finite or countably infinite) space in which the distribution of the next state depends only on the current state. These objects show up in probability and computer science both in discrete-time and continuous-time models. For Markov processes on continuous spaces please use .

A discrete-time Markov chain is a sequence of random variables $\{X_n\}_{n\geq1}$ with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states, i.e. $$\mathbb P(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\mathbb P(X_{n+1}=x\mid X_{n}=x_{n}),$$ if both conditional probabilities are well defined, i.e. if $\mathbb P(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

5938 questions
0
votes
2 answers

Understanding the meaning of transition rates in a CTMC

I am reading the queueing theory volume 1 by Kleinrock. In the chapter on Continuous Time Markov Chain(CTMC), the author defines the infinitesimal generator, $Q(t)$ as having the following elements: \begin{align} q_{ii}(t) &= \lim_{\Delta t \to 0 }…
gaganso
  • 217
0
votes
1 answer

Irreducible aperiodic Markov chain $P$ with invariant distribution implies $p_{ij}^{(n)} \rightarrow \pi_j$

I am reading Norris' book on Markov chains, and there is a theorem that sais : Let $P$ be irreducible and aperiodic, and suppose that $P$ has an invariant distribution $\pi$. Let $\lambda$ be any distribution. Suppose that $(X_n)_{n\ge 0}$ is…
roi_saumon
  • 4,196
0
votes
1 answer

Markov chain: infinite number of stationary distributions

Is it possible to construct a Markov chain having an infinite number of stationary distributions $\pi_i$? Maybe also with a finite set of states $S$? Maybe someone can explain why the following Markov chain has an infinite number of stationary…
0
votes
0 answers

$(Z_n)_{n\ge0}:=(X_{2n+1})_{n\ge0}$ Markov chain given $(X_n)_{n\ge0}$ is a Markov chain?

Given a markov chain $(X_n)_{n\ge0}$ with transition matrix $P$ I just proved that $(Z_n)_{n\ge0}:=(X_{kn})_{n\ge0}$ is a Markov chain with transition matrix $P^k$, $k\ge1$. Does this also work for $(Z_n)_{n\ge0}:=(X_{2n+1})_{n\ge0}$? In case…
0
votes
1 answer

Why is this model not a Markov chain?

I'm new to probability models. Taken from Ross' Introduction to Probability Models 11th ed: "Example 4.4 (Transforming a Process into a Markov Chain) Suppose that whether or not it rains today depends on previous weather conditions through the last…
goblinb
  • 591
  • 2
  • 11
0
votes
1 answer

Depict the Markov chain that models this process. Specify the matrix of transition probabilities. Then solve the problem.

P=\begin{pmatrix} 0.25 & 0.25 & 0.50 \\ 0.10 & 0.30 & 0.60\\ 0.05 & 0.15 & 0.80\\ \end{pmatrix} I know that $\vec{u}= P\vec{u}$ and we are trying to get: $(I-P)\vec{u}=\vec{0}$ I know that $(I-P)$= \begin{pmatrix} 0.75 & -0.25 &- 0.50 \\ -0.10 &…
Killercamin
  • 801
  • 4
  • 17
  • 39
0
votes
0 answers

Summation of transition probability of Markov chain

From Ross Ch. 4 Ex. 45 (c): Consider an irreducible finite Markov chain with states $0,1,\dots,N$. Let $x_i=P\{$visit state $N$ before state $0$ | start in $i\}$. Then $$x_i=\sum_{j=0}^{N}P_{ij}x_j,\qquad x_0=0,\qquad x_N=1$$ If $\sum_jjP_{ij}=i$…
hokoxixe
  • 11
  • 2
0
votes
1 answer

10 People and 2 Rooms - Probability Puzzle

Ten people are attending a party in a two-room apartment and, initially, it is equally likely that all ten are in room A or that nine are in room A and one in room B. This is no ordinary party: every minute, one person is chosen uniformly at random…
0
votes
0 answers

Prove this process is Markov chain

Let $X_n$ be largest number of first n throws of a fair six-sided die, show that $X = \{X_n: n\ge 1\}$ is homogeneous Markov chain My try: Let $Y_i$ denote the number of $i$th throw, then $X_n = \max\{Y_1,Y_2,...,Y_n\}$, $$P(X_{n+1} = j | X_n =…
0
votes
2 answers

Discrete-time Markov Chain; $n$-step transitions

Let $\{X_{n}\}_{n\geq0}$ be a discrete-time Markow chain on the state space $S=\{1,2,3\}$ with transition matrix \begin{pmatrix} 1/3 & 1/3 & 1/3 \\ 0 & 2/3 & 1/3 \\ 2/3 & 1/3 & 0 \end{pmatrix} The initial distribution is…
0
votes
2 answers

Determine stationary distribution of Markov Chain

I am struggling with finding the stationary distribution(s) for a discrete Markov chain with the following transition probability matrix \begin{bmatrix}1/3&2/3&0&0&0\\ 1/2&1/2&0&0&0\\ 0&1/2&0&1/2&0\\ 0&0&0&1/4&3/4\\ 0&0&0&1/3&2/3\end{bmatrix} Since…
0
votes
0 answers

Random walk on non-negative integers - Transcience Recurrence etc

Good evening. I have a problem concerning the random walk on non-negative integers. Suppose that $ p_{0,1}=1 , p_{i,i+1}=1-p , p_{i,i-1}=p $ . I would like to know for which value of $ p $ this random walk is transient/recurrent. I tried to apply…
0
votes
1 answer

Show that $P=pQ+(1-p)A$ is the transition matrix for an ergodic Markov chain.

Let $Q$ be a $k\times k$ stochastic matrix. Let $A$ be a $k\times k$ matrix each of whose entries is $1/k$. For $0
Parseval
  • 6,413
0
votes
1 answer

Show that $\mathbb{P}(T>n)=p(1-q)^{n-2},$ for $n\geq 2.$

Given the state space $S=\{1,2\}$ and the transition matrix for the two-state chain is given by $$\mathbf{P}=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix},$$ where $p$ and $q$ are not both $0$. Let $T$ be the first return time to state $1$,…
Parseval
  • 6,413
0
votes
0 answers

Does the definition of positive or null recurrence require aperiodicity?

Do the notions of null or positive recurrence have to be defined with respect to irreducible, aperiodic chains or does irreducibility suffice?
p-value
  • 474