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
1 answer

Search for a non absorbing Markov chain

According to the usual definition: "A Markov chain is absorbing if it has at least one absorbing state, and if from every state it is possible to go to an absorbing state." (taken for example from Darmouth College - slide #3) Now I am looking for an…
Andrew
  • 483
0
votes
0 answers

Ehrenfest urn model - expected hitting time

Consider the Ehrenfest urn model with $N$ identical balls divided in two urns $A$ and $B$. At each step, pick a ball at random and switch its urn. I need to compute $E_{N-1}(\tau_N) $ which is the expected hitting time for the state in which all…
Tomer
  • 434
0
votes
0 answers

Is this a time-homogeneous Markov Chain?

Let $Z_0,Z_1,Z_2,...$ be i.i.d. random variables,taking values $+1$ and $-1$ each with probability $1/2$. Let $S_n=\sum_{i=0}^n Z_i$(where we take $S_0=0$).Let $X_n=\sum_{j=0}^n S_j$. say whether or not $X_n$ is a time-homogeneous Markov chain? If…
Aya
  • 1
0
votes
2 answers

Generalising $P^n$ for nth time-step of markov chain

We have the following state-space $S = \{0,1,2,3\} $ with transition matrix:$$ P = \begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2}&\frac{1}{2}&0&0 \\ 0 &0 &\frac{1}{3} & \frac{2}{3} \\ 0 &0&0&1 \end{pmatrix}$$ Deduce a general…
0
votes
0 answers

In a Markov chain is an absorbing state considered an irreducible set of one element?

A closed set $C$ is irreducible if $x$ leads to $y$ for all states $x$ and $y$ in $C$. Would you consider a set of a singular absorbing state irreducible. Note that this is mostly a question of terminology.
0
votes
1 answer

Computing Markov chain state on a 2x2 matrix

I have the following Markov matrix $A=\begin{bmatrix} 1-\beta & \beta \\ \alpha & 1-\alpha \\ \end{bmatrix} $ And initial row vector $X_0 = (0,1)$ I need to compute the state vector $X_3$ which means $X_0 A^3 $. I started doing it but got a very…
Tomer
  • 434
0
votes
1 answer

Is this Markov chain aperiodic?

I am wondering if $\pi=\begin{pmatrix} 1&0\\1&0\end{pmatrix}$ is an aperiodic Markov chain or not? This chain is clearly not irreducible, but there is also no period for the chain since if you start in state 2, you will never return to it. The…
mathim1881
  • 590
  • 2
  • 12
0
votes
0 answers

There are k players, with player i having value

This is question 3 of the Marcov chain chapter of Introduction to Probability models by Ross (12th edition). There are k players, with player i having value $v_i > 0, i=1,...,k$. In every period, two of the players play a game, while the other k−2…
Ram Zi
  • 67
0
votes
1 answer

Random walk, number of visits before returning

I think I managed to solve a; Write P as $$\begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4}\\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 &…
mrrobot
  • 41
0
votes
0 answers

Updating the parameters of the Viterbi Algorithmm

I am currently studying Viterbi Algorithm within the context of probability and sequence generation. My understanding of it so far, is that it helps us generate a sequence of events such that it is most likely to cause a specific sequence of…
0
votes
1 answer

stationary/limiting distribution of an irreducible aperiodic finite markov chain problem

I'm having a hard time trying to compute the limiting distribution of this problem Problem In a kindergarten, $n$ boys and $n$ girls are standing in a circle playing a game. The children are spaced evenly around the circle and alternate between boys…
0
votes
1 answer

Express the Markov property using the transition matrix

Let $\{X_t; t \in \mathbb{N}_0\}$ be a discrete Markov chain with finite state space $\Omega$ and transition matrix $P$. Let $\{\mathcal{F}_t; t \in \mathbb{N}_0\}$ be the corresponding filtration. I saw in a paper (but without justification) that…
Babado
  • 1,306
0
votes
1 answer

How would this Markov chain problem be solved?

I have the following problem: Bob is a salesman. Each week, Bob will either make no money, make a small amount of money, or make a large amount of money. And if Bob makes money, he will either make \$100 (small amount) or \$1000 (large amount). For…
The Pointer
  • 4,182
0
votes
0 answers

Crossing problem in absorbing Markov chain

Considering one finite state discrete Markov chain and there are multiple transient states and multiple absorbing states. If there is a set of transient states A and the specific state i belongs to set A. My questions are, is there any algorithm can…
0
votes
0 answers

Criterion: Finite Markov chain expected time to absorption upper bound

Assume that $X$ is a Markov chain on a finite state space $S$ with $A\subset S$ a set of absorbing states for $X$. Assume that for any state $x\in S$ the the transition probability for $X$ to go from $x$ to $A$ is bounded from below as $\inf_{x\in…
Jfischer
  • 1,239