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

Selecting a Stationary distribution of a Markov chain

Suppose that a finite-state Markov chain with transition matrix $M$ has multiple stationary distributions (or invariant measures). Let $\Pi$ denote the set of the stationary distributions. Fix any $\pi \in \Pi$. Does there exist a Markov chain with…
Pierre
  • 103
0
votes
1 answer

Modifying the transition matrix in an irreducible Markov chain

Suppose I have an irreducible and recurrent Markov chain in a state space with at least 2 states, given by a transition matrix $ (P)_{ij} $. I would like to show that the derived transition matrix $$ \hat{P_{ij}} = \begin{cases} 0 & i = j \\ (1…
0
votes
1 answer

how to be sure that from one state to another state

http://robotics.eecs.berkeley.edu/~wlr/126/w12.htm when you draw this graph how can you sure that state go from 1 to 2 is 100%? look at first example, there is a p and q is it probability from 1 to 2 that is drawn only when P(from 1 to 2) > 0.5,…
Scott
  • 65
  • 6
0
votes
1 answer

What is number coming from in $\gcd$ of Markov chain topic?

For example for [6], $d(1) = \gcd\{3, 5, 6,\, ...\} = 1$. What do $3,5,6$ calculated from?
Scott
  • 65
  • 6
0
votes
0 answers

Hitting Probability for Markov Chain

I have a discrete Markov Chain on the integers. From state $i$ I have a probability $\mu$ to go to $i-1$ and probability $\lambda$ to go to $i+1$, where $\mu+ \lambda=1$. I am asked to calculate the probability that starting from $0$ we ever hit $i…
Patrick
  • 419
0
votes
1 answer

How to define states in Markov Chains?

For words problems, I'm having trouble defining what state should be in a Markov chain, when the states aren't that obvious. Are there any general procedures that should be followed in order to identify what a state should be? An example I'm having…
0
votes
0 answers

Likelihood of histories given state space, initial distribution, transition matrix

I'm an economist looking at Markov Chains for the first time, and this is simple stuff and it is quite embarassing to post about this, because the answer is provided, but I do not understand the solution to the problem below. Can someone shed some…
Fede C
  • 21
0
votes
1 answer

Why is the markov chain that models the movement of a bishop aperodic?

I understand why a king's movement is aperiodic, because it can return to the start point in 2 or 3 movements. If the king starts at 2,2 the moves for the 2 movements scenario would be 2,2 -> 2,3 -> 2,2 and for the 3 movement scenario would be 2,2…
0
votes
1 answer

Why is $\alpha(x) = P^{\alpha}(X_0 = x)$?

Assume that $(X_n)$ is a sequence of random variables that are stationary with respect to $P^{\alpha}$, with $\alpha > 0$ being a stationary distribution. Then, why are we allowed to write $\alpha(x) = P^{\alpha}(X_0 = x)$?
Julian
  • 1,401
0
votes
1 answer

Is this sufficient for the transience of a Markov Chain?

Let $(X_n)$ be an irreducible Markov chain on a countable state space $S$. Suppose there's an non-empty set $A\subseteq S$ such that for some $x\notin A$ $$ P_x(\tau_A<\infty)<1$$ Where $\tau_A :=\inf\{n\geqslant 1: X_n\in A\}$ is the hitting time…
Max
  • 484
  • 2
  • 14
0
votes
1 answer

Triangle Inequality for hitting time of Markov Chains

Given a finite, irreducible and aperiodic discrete time Markov chain on state space, $\{1, 2,\cdots, n\}$, define $h(i,j)$ to be the expected time for the first visit to $j$ from state $i$. Here we consider $h(i,i)$ to be the mean return time to…
Sudheer
  • 343
0
votes
2 answers

Can a markov chain have period of zero?

So i had an exam returned today, and im not convinced that my answer was wrong so it went like this. Markovian Chain Picture The question was if the the markov chain had a period (The correct answer is it has a period). And me looking at it, i was…
Wuh
  • 11
  • 1
0
votes
0 answers

How did the author get these transitional probabilities in this markov model?

I am referring to this: http://www.mdpi.com/1999-5903/9/3/37/htm In Chapter 3.1, the author assumes a scenario where in the first 50ms of an observation, pages 1 and 2 are dirty. In the next 50ms, pages 2, 3 and 4 are dirty. And in the last 50ms,…
0
votes
1 answer

Long term probability of arrangement of $n$ processors

I have been having struggling with this question for some time now and nothing comes to mind: A group of $n$ processors are arranged in an ordered list. At every step, a task comes into the first processor in the list, if it cannot solve the task,…
GuPe
  • 7,318
0
votes
1 answer

Show that a homogeneous markov-chain is still a markov-chain after replacing the index with a monotonic increasing sequence.

Let $X = (X_n)_{n \in \mathbb{N}_0}$ be a homogeneous Markov-chain and $(n_r)_{r \in \mathbb{N}_0}$ a monotonic increasing sequence in $\mathbb{N}_0$. How can I show that $$Y = (Y_r)_{r \in \mathbb{N}_0} = (X_{n_r})_{r \in \mathbb{N}_0}$$ is as well…
Hekri
  • 53