Mathematics Stack Exchange
Mathematics Stack Exchange

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
1
vote
2 answers

Is it meaningful to talk about margins-of-error in a Markov Chain?

We're creating a Markov Chain based on an analysis of user's history. We add up and normalise users behaviour, and then normalise to create a two dimensional map of probabilities, but some of these probabilities are very low and I was wondering if…
Ricardo Gladwell
  • 113
1
vote
1 answer

Finding $P_{11}(n)$ in Markov Chains

Calculate: $P_{11}(n)=P(X_n=1|X_0=1)$ where the transition matrix is of the form: $$\left[\begin{matrix}0 & 1 &0 \\ 0 & \dfrac{1}{2} & \dfrac{1}{2} \\ \dfrac{1}{2} & 0 & \dfrac{1}{2}\end{matrix}\right]$$ okay so I worked out my eigenvalues of the…
sarahusher
  • 834
1
vote
2 answers

Proof of Markov Property

I'm trying to understand a simple proof for the markov property which states that: "$A_1$, $A_3$ are conditionally independent given $A_2$ iff $P(A_3 | A_1 \cap A_2)=P(A_3|A_2)$" The Proof begins as follows: "only if" $$P(A_3 | A_1 \cap A_2) =…
sarahusher
  • 834
1
vote
1 answer

Markov Chains as Autoregressive Processes

Is there a simple way to approximate a Markov Chain as an Autoregressive Process, for instance, an AR(1) process? I am aware that it is easy to approximate an AR(1) process with a Markov Chain, but I am not sure about the converse. Thanks.
hulp10
  • 292
1
vote
3 answers

Recurrence of infinite markov chain

I have a Markov chain with state space $S=\{0,1,2...\}$ and a sequence of positive numbers $p_1,p_2,...$ where $\sum p_i=1$. The transition probabilities are based on these where $p(x,x-1)=1, x>0$ $p(0,x)=p_x, x>0$ Is this chain recurrent? What…
rakoonise
  • 111
1
vote
0 answers

condition for recurrence of the chain

Let $\{X_n\}$ be an irreducible Markov chain with transition probability $P=(p_{ij})$ on a countable state space $S=\{0,1,2,\dots\}$.Suppose $s\in S$.Show that $s$ is a recurrent state if the there is a solution of the following…
Ribhu
  • 742
1
vote
3 answers

Markov chain, successive running average

Here's my question: Take three numbers $x_1$, $x_2$, and $x_3$, and form the successive running averages $$x_n = \frac{x_{n-3} + x_{n-2} + x_{n-1}}{3}$$ starting with $x_4$. Prove that $$\lim_{n \to \infty} x_n = \frac{x_1 + 2x_2 + 3x_3}{6}$$ So I…
EpicMochi
  • 1,018
1
vote
2 answers

Markov chains question?

A country is divided into three geographic regions. It is found that each year 5% of the residents move from region I to region II and 5% move from region I to region III. In region II, 15% move to region I, and 10% move to region III. In region…
cbass0
  • 195
  • 2
  • 2
  • 14
1
vote
1 answer

Given an invariant distribution is the (finite state) Markov transition matrix unique?

Doeblin's theorem states that for a given transition probability matrix there exists a unique invariant distribution for that chain. Is the converse true as well? Can two (finite state, discrete) Markov Chains have the same invariant distribution,…
Tom Kealy
  • 282
1
vote
1 answer

What is the corresponding transition matrix for this DTMC?

there I am a bit confused about forming the transition matrix for this inventory problem. Suppose that $X(n)$ is amount of the item in the inventory at the end of the each period (day). One thing that is quite straightforward is to consider…
Majid Biazaran
  • 85
1
vote
2 answers

Exercise 1.3.2 of Norris, "Markov Chains"

I'm working my way through Norris's classic textbook, but I'm having problems with this hitting probability question: "A gambler has £2 and needs to increase it to £10 in a hurry. He can play a game with the following rules: a fair coin is tossed:…
Ubt388
  • 37
  • 1
  • 3
1
vote
1 answer

Markov Chain: starting at $i$ reaching $N$ before $0$

Starting at some state $i$, we have probability of going $P_{i,i+1} = p$ and probability $P_{i,i-1} = 1-p$ what is the probability I reach N before I reach zero? Can I convert this to a gambler's ruin problem where I start with i in bank and reach N…
knk
  • 359
  • 4
  • 16
1
vote
1 answer

Hitting Time Markov Chain

Let$\left\{{X_{n}: n\in \mathbf{N}}\right\}$ be a Markov Chain in discrete time, with the hitting time being defined as $\displaystyle H^A=\inf\left\{{n\geq 0 : X_{n}\in A}\right\}$. Assuming $i\not \in A$, how do I prove…
An old man in the sea.
  • 5,241
1
vote
1 answer

Irreducible Markov chain

Consider an irreducible Markov chain with an invariant distribution $\pi$. Then show that if $\pi(x)>0$ for some $x \in S$, where $S$ is the state space, then $x$ is recurrent. Here's what I was trying: so we know that $P_x(T_y<\infty)>0$ for any…
adamG
  • 665
  • 1
  • 10
  • 23
1
vote
1 answer

Finding stationary distribution on markov chain

We have the state space {0,1,2,3,4,5,...,} we got the following transition probabilities $p_{00}=q+r$ $p_{01}=p$ $p_{i,i-1}=q$ $p_{i,i}=r$ $p_{i,i+1}=p$ for $i>=1$ where we have $p+q+r=1$ FInd the stationary distribuion where $p=.2,q=.4,r=.4$ Is the…
Fernando Martinez
  • 6,698
  • 19
  • 74
  • 108
1 2 3
…
30 31