31:T9a5,# Conditions Then, under what conditions is the stationary distribution unique, if it even exists? A *sufficient* condition is **irreducibility** and **positive recurrence**, although the former implies the latter if the state space is finite. In that case, all we need is irreducibility. Here's a *necessary and sufficient* condition: the stationary distribution exists and is unique if and only if the Markov chain has exactly one positive recurrent class. Note that this allows the chain to be reducible if all the other classes are transient.

*what about Markov chains where the necessary and sufficient condition isn't satisfied?*

If a Markov chain has *multiple* positive recurrent classes, then there are *multiple* stationary distributions. The interpretation here is that the long-run proportions will depend on the initial state, and are therefore non-identifiable.

If a Markov chain has *no* positive recurrent classes, then there exists *no* stationary distribution. This can only happen when the state space is infinite. Here, the chain doesn't spend an appreciable amount of time in any state, and the long-run proportions will be identically zero. Another instance of infinity breaking things!

^{We can break down this case even further. An (irreducible) infinite Markov chain can be *positive recurrent*, ***null recurrent***, or ***transient***. If the chain is transient, then we will only visit each state a finite number of times. If the chain is null recurrent, then we will visit each state infinitely often, but it will also take infinitely long to return! In both cases, the long-run proportions will tend to 0.}

# Simulation Let's visualize this with a simple, two-state example. We can analytically compute the stationary distribution by solving the global balance equations, and then compare it to the empirical long-run distribution computed from a sample path. Under our conditions, it turns out that the latter will converge to the former almost surely! The rate of convergence is known as the **mixing time** of the Markov chain.32:T1a37,markov = { // DIAGRAM PARAMETERS const prob_12 = `${p_12}`; const prob_21 = `${p_21}`; const speed = `${spd}`; // BOX CONSTANTS const width = 900; const height = 400; // ARROWHEAD CONSTANTS const markerBoxWidth = 20; const markerBoxHeight = 20; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; const markerWidth = markerBoxWidth / 2; const markerHeight = markerBoxHeight / 2; const arrowPoints = [[0, 0], [0, 20], [20, 10]]; //////////////////////////////////////////// STATE DIAGRAM SKELETON /////////////////////////////////////////////////// const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]); // STATES let states = [ { x: width / 3, y: 0.375 * height, r: 50, text: '1', fill: "blue", count: 0}, { x: 2 * width / 3, y: 0.375 * height, r: 50, text: '2', fill: "red", count: 0}, ]; // Add hidden states + text to the svg element let groups = svg .selectAll('g') .data(states) .join('g') .attr('transform', (d, i) => {return `translate(${d.x}, ${d.y})`;}) groups .selectAll('circle') .data(d => [d]) .join('circle') .attr('cx', 0) .attr('cy', 0) .attr('r', d => d.r) .style('fill', d => d.fill) .style('opacity', 0.3); groups .selectAll('text') .data(d => [d]) .join('text') .attr('x', 0) .attr('y', 0) .attr('font-size', 30) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'white') .text(d => d.text); // LINKS (curvy) const points = [[[300, 100], [280, 60], [230, 50], [190, 80], [190, 130], [210, 150], [240, 150]], // 0 -> 0 [[345, 130], [400, 115], [450, 110], [500, 115], [545, 130]], // 0 -> 1 [[600, 100], [620, 60], [670, 50], [710, 80], [710, 130], [690, 150], [660, 150]], // 1 -> 1 [[555, 170], [500, 185], [450, 190], [400, 185], [355, 170]] // 1 -> 0 ]; const curve = d3.line().curve(d3.curveNatural); for (let i = 0; i < points.length; i++) { svg .append('path') .classed('curve', true) .attr('d', curve(points[i])) .attr('stroke', 'gray') .attr('fill', 'none') .attr('marker-end', 'url(#arrow)'); } // Add arrowheads to the svg element -- GRAY svg .append('defs') .append('marker') .attr('id', 'arrow') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerBoxWidth) .attr('markerHeight', markerBoxHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'gray') .style("fill", 'gray'); // Add arrowheads to the svg element -- BLACK svg .append('defs') .append('marker') .attr('id', 'arrow2') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerBoxWidth) .attr('markerHeight', markerBoxHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'black') .style("fill", 'black'); ///////////////////////////////////////////// BAR CHART SKELETON /////////////////////////////////////////////////// // X-axis let x = d3.scaleLinear() .domain([0, 1]) .range([ 0, width / 2 ]); svg.append("g") .attr("transform", "translate(225," + 0.9 * height + ")") .call(d3.axisBottom(x).ticks(21)) .selectAll("text") .attr("transform", "translate(0,0)rotate(-45)") .style("text-anchor", "end"); svg.selectAll("myRect") .data(states) .enter() .append("rect") .classed('bars', true) .attr("x", width / 4) .attr("y", (d, i) => 0.62 * height + 55 * i) .attr("width", d => x(d.count / d3.sum(states, d => d.count))) .attr("height", 50) .attr("fill", d => d.fill) .attr("opacity", 0.8) ///////////////////////////////////////////////// INTERACTIVITY ////////////////////////////////////////////////////// // if num < transition_prob, we TRANSITION (=== switch the value of prev) // prev = 0: state 1, prev = 1: state 2 set(viewof n, 1); set(viewof n_1, 0); let prev = Math.random() > 0.5 ? 0 : 1; if (prev === 0) { states[0].count += 1; set(viewof n_1, 1); } else { states[1].count += 1; } function blink() { let num = Math.random() if (prev === 0) { var next = svg.selectAll('circle').filter((d, i) => num < prob_12 ? i === 1 : i === 0); } else { var next = svg.selectAll('circle').filter((d, i) => num < prob_21 ? i === 0 : i === 1); } let path_select = svg.selectAll('path.curve') .filter((d, i) => { if (points[i][0][0] === 300 && prev === 0 && num > prob_12) { return true; } else if (points[i][0][0] === 345 && prev === 0 && num < prob_12) { return true; } else if (points[i][0][0] === 600 && prev === 1 && num > prob_21) { return true; } else if (points[i][0][0] === 555 && prev === 1 && num < prob_21) { return true; } else return false; }); if (prev === 0) { if (num < prob_12) { prev = 1; states[1].count += 1; } else { states[0].count += 1; } } else // if (prev === 1) { if (num < prob_21) { prev = 0; states[0].count += 1; } else { states[1].count += 1; } } set(viewof n, d3.sum(states, d => d.count)); set(viewof n_1, states[0].count); let bars = svg.selectAll('rect.bars'); bars.transition() .delay(speed) .transition() .attr("width", d => x(d.count / d3.sum(states, d => d.count))); path_select.transition() .duration(speed / 2) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow2)') .transition() .duration(speed / 2) .attr('stroke-width', 1) .style('stroke', 'gray') .transition() .duration(300) .attr('marker-end', 'url(#arrow)'); next.transition() .duration(speed) .transition() .duration(speed) .style("opacity", 1) .transition() .duration(speed / 2) .style("opacity", 0.3) .on("end", blink); return svg.node(); } return blink(); }33:T5ed,

the transition matrix: ${tex`~~\,P = \begin{bmatrix}~~\,1-\textcolor{red}{p_{12}} & ~~\textcolor{red}{p_{12}}~~\\ ~~\,\textcolor{blue}{p_{21}} & ~~1 -\textcolor{blue}{p_{21}} ~~\,\end{bmatrix} \,= \begin{bmatrix}${(1-p_12).toPrecision(1)} & ${p_12}\\ ${p_21} & ${(1-p_21).toPrecision(1)} \end{bmatrix}`}

${p_21 == p_12 & p_21 == 0 ? md`the *analytical* solution: ${tex`~`}there are 2 recurrent classes, so there's no unique solution.` : md`the *analytical* solution: ${tex`\,\,\pi = \begin{bmatrix}\,~~~\frac{\textcolor{blue}{p_{21}}}{\textcolor{red}{p_{12}}\, +\, \textcolor{blue}{p_{21}}} & ~~~\frac{\textcolor{red}{p_{12}}}{\textcolor{red}{p_{12}}\, +\, \textcolor{blue}{p_{21}}} ~~\,\end{bmatrix} \,\approx \begin{bmatrix} \textcolor{blue}{${Number((p_21 / (p_12+p_21)).toPrecision(3))}} & \,\textcolor{red}{${Number((p_12 / (p_12+p_21)).toPrecision(3))}} \end{bmatrix}`}`} ${p_21 == p_12 & p_21 == 0 ? md`the *empirical* solution: ${tex`~~`}the empirical distribution will depend on the initial state.` : md`the *empirical* solution: ${tex`~~\hat \pi = \begin{bmatrix} \frac{\sum\limits_{i=1}^{${n}}\textbf{1}\{X_i \,=\, \textcolor{blue}{1}\}}{${n}} &\!\!\! \frac{\sum\limits_{i=1}^{${n}}\textbf{1}\{X_i \,=\, \textcolor{red}{2}\}}{${n}}\end{bmatrix}\approx \begin{bmatrix} \textcolor{blue}{${Number(n_1 / n).toPrecision(3)}} & \,\textcolor{red}{${Number(1 - (n_1 / n)).toPrecision(3)}} \end{bmatrix}`}`}34:T6bc,

# Extensions

**Limiting Distribution**

The **limiting distribution** of a Markov chain is a probability vector ${tex`\pi`} such that ${tex`\lim\limits_{n\to\infty} P^{(n)}_{ij} = \pi_j`} for all ${tex`j \in \mathcal{S}`}. This exists and is equal to the *unique* stationary distribution when the Markov chain is also **aperiodic**, in addition to the above.

A Markov chain satisfying all three conditions — irreducibility, aperiodicity, and positive recurrence — is called **ergodic**. In a finite Markov chain, irreducibility implies positive recurrence, so positive recurrence is not strictly necessary then.

**Time-Reversibility**

A Markov chain is **time-reversible** if there exists a probability vector ${tex`\pi`} such that ${tex`\pi_j P_{ji} = \pi_i P_{ij}`} for all ${tex`i,j \in \mathcal{S}`}. These are known as the **detailed balance equations**.

Note that the detailed balance equations imply the global balance equations! Then, any probability vector ${tex`\pi`} that satisfies the detailed balance equations *is* the unique stationary distribution. In other words, reversibility is a *stronger* condition than being irreducible and positive recurrent; as such, it is also a *sufficient* condition.

35:[] 2f:{"title":"The π’s The Limit","cells":[{"id":0,"value":"# The π’s The Limit\n## Stationary Distributions in Discrete-Time Markov Chains\n\n*Eric Chen*\n\nThe goal of this notebook is to visualize the concept of *stationary distributions*, or invariant distributions, in discrete-time Markov processes. It's assumed that the reader has a working knowledge of Markov chains. To be specific, we only focus on discrete-time, discrete-state, time-homogeneous, first-order Markov processes.\n

","pinned":false,"hidden":false,"mode":"md"},{"id":30,"value":"# Definition\n\nA **discrete-time Markov chain** ${tex`\\{X_n\\}`} on state space ${tex`\\mathcal{S}`} is characterized by an ${tex`S\\! \\times\\! S`} **transition matrix** ${tex`P`}, with entries defined as ${tex`P_{ij} = P(X_{n+1} = j \\,|\\, X_n = i) \\in [0, 1]`}. \n\nThen, a **stationary distribution** for ${tex `P`} is a probability distribution ${tex`\\pi`} over ${tex`\\mathcal{S}`} with:\n

\n${tex`\\pi P = \\pi`}\n

\n\nwhere ${tex`\\pi`} is a row vector. Since ${tex`\\pi`} is a probability distribution, we require ${tex`\\|\\pi\\|_1 = 1`}. These are called the **global balance equations** for a discrete-time Markov chain.\n\n

","pinned":false,"hidden":false,"mode":"md"},{"id":2177,"value":"# Intuition\n\nWhy is this important? The stationary distribution tells us a lot about the eventual *convergence* of the Markov chain. When the distribution is unique, it can be interpreted as the chain's \"long-run probabilities\" — it represents the proportion of time that the chain spends in each state if you were to run the process indefinitely.\n\n

^{Things can get weird when we consider *infinite* Markov chains, and the usual \"long-run probabilities\" interpretation breaks down for some pathological [counterexamples](https://math.stackexchange.com/questions/2816677/what-is-the-necessary-and-sufficient-condition-of-markov-chain-sample-average-co). We won't consider them here.}

\n\n

","pinned":false,"hidden":false,"mode":"md"},{"id":146,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":1468,"value":"

^{Refresh the page to display a different combination of transition probabilities; right now, there's a bug in the code that computes the empirical long-run probabilities. Help would be appreciated!}

","pinned":false,"hidden":false,"mode":"md"},{"id":245,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"viewof p_12 = slider({min:0, \n max:1, \n step:0.1,\n value: Math.random().toPrecision(1),\n description: md`transition probability, ${tex`p_{12}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":364,"value":"viewof p_21 = slider({min:0, \n max:1, \n step:0.1,\n value: Math.random().toPrecision(1),\n description: md`transition probability, ${tex`p_{21}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":257,"value":"viewof spd = slider({max:1050,\n min:150,\n step:50,\n value: 200,\n description: html`animation delay`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":289,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":1454,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":1694,"value":"md`\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"import {slider} from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1192,"value":"function set(input, value) {\n input.value = value;\n input.dispatchEvent(new Event(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1143,"value":"viewof n = Inputs.input(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1226,"value":"viewof n_1 = Inputs.input(0)","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}