2d:null 2e:["$","title",null,{"children":"stdlib: Simulating Noisy Time Series Using Discrete-time Markov Chains | Athan | Observable"}] 33:[] 31:{"id":"1099e62f77fdfe1a","slug":"stdlib-simulating-noisy-time-series-using-discrete-time-ma","title":"stdlib: Simulating Noisy Time Series Using Discrete-time Markov Chains","thumbnail":"c5772988d730d5361624e4ceb2abff03888d35d7a8480221a1f514a73b3d2357","access_level":"public","create_time":"$D2018-02-06T23:06:14.869Z","update_time":"$D2018-12-04T15:38:48.044Z","view_time":null,"first_public_time":"$D2018-02-07T04:49:37.820Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"305fcf2f11e07649","login":"kgryte","name":"Athan","avatar_url":"https://avatars-next.observableusercontent.com/62abcb0f1a226f03a1138db7fec8a58afd71e37ca89254954af372e75fb90a73","tier":"starter_2024","bio":"Node.js and JavaScript. Currently working on a JavaScript standard library for numerical and scientific computing.\r\n\r\nhttps://www.patreon.com/athan"},"version":507,"publish_version":507,"role":null,"authored":false,"authors":[{"type":"individual","id":"7b908ca3d7dc4524","login":"kgryte","name":"Athan","avatar_url":"https://avatars-next.observableusercontent.com/62abcb0f1a226f03a1138db7fec8a58afd71e37ca89254954af372e75fb90a73","tier":null,"bio":"Node.js and JavaScript. Currently working on a JavaScript standard library for numerical and scientific computing.\r\n\r\nhttps://www.patreon.com/athan"}],"members":[{"type":"individual","id":"7b908ca3d7dc4524","login":"kgryte","name":"Athan","avatar_url":"https://avatars-next.observableusercontent.com/62abcb0f1a226f03a1138db7fec8a58afd71e37ca89254954af372e75fb90a73","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"16cb696d0295f5bd","slug":"stdlib","title":"stdlib","owner":{"id":"305fcf2f11e07649","login":"kgryte","name":"Athan"}},"type":"notebook","body":{"titling":"auto","title":"stdlib: Simulating Noisy Time Series Using Discrete-time Markov Chains","cells":[{"id":0,"value":"md`# stdlib: Simulating Noisy Time Series Using Discrete-time Markov Chains`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"md`A markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends **only** on the previous event. In other words, we can predict a future event based solely on the sequence's current state and without regard for the sequence's prior states.\n\nMarkov chains are commonly used to model a broad range of real-world phenomena, such as biological reactions, speech, financial time series, and user behavior.\n\nIn this notebook, we'll discuss discrete-time Markov chains and how we can use them to simulate noisy time series.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`* * *\n\n## Getting Started`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`Throughout the notebook, we'll be using [stdlib](https://github.com/stdlib-js/stdlib), a standard library for JavaScript and Node.js with an emphasis on numerical and scientific computing applications. The library provides a collection of robust, high performance libraries for mathematics, statistics, streams, utilities, and more. For source code, see the GitHub [repository](https://github.com/stdlib-js/stdlib).\n\nTo use [stdlib](https://github.com/stdlib-js/stdlib) in Observable, we can load one of the distributable [files](https://github.com/stdlib-js/stdlib/tree/develop/dist) intended for use in browser environments.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"stdlib = require( \"https://unpkg.com/@stdlib/stdlib@0.0.32/dist/stdlib-flat.min.js\" )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md`The returned \\`object\\` contains over 1000 functions and methods. To see available functionality, click through the returned \\`object\\` above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"md`To reduce function name noise, we'll alias some of the [stdlib](https://github.com/stdlib-js/stdlib) functions we'll be using in this notebook.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"md`Function for generating [uniformly distributed pseudorandom numbers](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/random/base/randu):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"randu = stdlib.base.random.randu","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"md`Function for generating [normally distributed pseudorandom numbers](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/random/base/normal):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":358,"value":"randn = stdlib.base.random.normal","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"md`Function for generating [plots](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"plot = stdlib.plot","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"md`Function for generating a [uniformly spaced numeric array](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/math/utils/linspace):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"linspace = stdlib.linspace","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":170,"value":"md`To convert [virtual DOM](https://github.com/Matt-Esch/virtual-dom) to HTML, we can use the [\\`vdom-to-html\\`](https://github.com/builtcrew/vdom-to-html) package available on \\`npm\\`. To load the package, we use [\\`wzrd.in\\`](https://wzrd.in/), which [browserifies](https://github.com/browserify/browserify) (i.e., bundles) an \\`npm\\` package for use in browser environments.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":172,"value":"vdom2html = require( \"https://wzrd.in/standalone/vdom-to-html@2.1\" )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md`* * *\n\n## Two-state Markov Chains`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"md`The anatomy of a discrete-time Markov Chain is straightforward, being comprised of two elements: a set of initial probabilities, \\`I\\`, describing the probability that a process begins in any particular state and a matrix of transition probabilities, \\`A\\`, describing the probability that a process transitions from state \\`s_i\\` to state \\`s_j\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"tex`I = \\begin{bmatrix}\ns_0 \\\\\ns_1 \\\\\ns_2 \\\\\n\\vdots \\\\\ns_{n}\n\\end{bmatrix}, \\ \\ A = \\begin{bmatrix}\na_{00} && a_{01} && \\ldots && a_{0n} \\\\\na_{10} && a_{11} && \\ldots && a_{1n} \\\\\n\\vdots && \\vdots && \\ddots && \\vdots \\\\\na_{n0} && a_{n1} && \\ldots && a_{nn}\n\\end{bmatrix}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"md`As an example, let's assume a two-state Markov chain with initial probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"initial = [ 0.3, 0.7 ] // should sum to 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"md`and transition probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"transition = [[ 0.2, 0.8 ], [ 0.4, 0.6 ]] // each row should sum to 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"md`In this example, we are saying that \n\n- the Markov chain has a ${initial[0]*100}% probability of starting in state \\`s_0\\` and a ${initial[1]*100}% probability of starting in state \\`s_1\\`.\n- when in state \\`s_0\\`, the Markov chain has a ${transition[0][0]*100}% probability of transitioning to state \\`s_0\\` (i.e., staying in the same state) and a ${transition[0][1]*100}% probability of transitioning to state \\`s_1\\`.\n- when in state \\`s_1\\`, the Markov chain has a ${transition[1][0]*100}% probability of transitioning to state \\`s_0\\` and a ${transition[1][1]*100}% probability of transitioning to state \\`s_1\\` (i.e., staying in the same state).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"md`Using the set of initial probabilities and the matrix of transition probabilities, we can simulate a state sequence as follows. First, we randomly choose an initial state by drawing a uniformly distributed random number on the interval [0,1]. If the number is less than or equal to ${initial[0]}, we start in state \\`s_0\\`; otherwise, we start in state \\`s_1\\`.\n\n> **Aside**: this does **not** generalize to more than 2 states. We'll describe a more general approach to simulate a Markov chain later in this notebook.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"initial_state = ( randu() <= initial[0] ) ? 0 : 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"md`In a similar fashion, we can choose the next state by drawing a uniformly distributed random number on the interval [0,1]. If the number is less than or equal to the first transition probability ${transition[initial_state][0]}, we transition to state \\`s_0\\`; otherwise, we transition to state \\`s_1\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"second_state = ( randu() <= transition[initial_state][0] ) ? 0 : 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"md`To simulate the next state, we repeat the previous command, but this time using \\`second_state\\` rather than \\`initial_state\\` to ensure that we use the relevant set of transition probabilities.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"third_state = ( randu() <= transition[second_state][0] ) ? 0 : 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"md`To simulate \\`n\\` steps of a Markov chain, we can generalize the above approach as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"state_sequence = {\n var nsteps = 100;\n var states;\n var curr;\n var i;\n\n states = new Array( nsteps );\n states[ 0 ] = initial_state;\n curr = initial_state;\n for ( i = 1; i < nsteps; i++ ) {\n curr = ( randu() <= transition[curr][0] ) ? 0 : 1;\n states[ i ] = curr;\n }\n return states;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"md`To visualize the simulated state sequence, we can create a plot using the [\\`plot()\\`](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor) API available in [stdlib](https://github.com/stdlib-js/stdlib) . We'll first create a [\\`plot\\`](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor) instance.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"plt = plot()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"md`We can configure the [\\`plot\\`](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor) instance by setting various properties.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"function configurePlot( plt, y, numStates ) {\n // Disable auto-rendering, deferring, instead, to Observable:\n plt.autoRender = false;\n \n // Plot meta data:\n plt.description = 'Markov chain simulated state sequence.';\n plt.title = 'Simulated Markov Chain';\n \n // Plot dimensions:\n plt.width = 800; // pixels\n \n // x-axis configuration:\n plt.xLabel = 'Step';\n plt.xMin = -1;\n plt.xMax = y.length;\n \n // y-axis configuration:\n plt.yLabel = 'State';\n plt.yMin = -0.1;\n plt.yMax = (numStates-1) + 0.1;\n plt.yNumTicks = numStates;\n \n // Data point encoding:\n plt.symbols = [ 'open-circle' ];\n \n // Values along the abscissa (x-values) will simply be a linearly spaced array representing the step number:\n plt.x = [ linspace(0, y.length-1, y.length) ];\n \n // State sequence:\n plt.y = [ y ];\n \n return plt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":190,"value":"configurePlot( plt, state_sequence, 2 )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"md`We can then render the plot by first wrapping method invocation in a function to ensure reactivity in Observable`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":193,"value":"function renderPlot( plt, y, numStates ) {\n configurePlot( plt, y, numStates );\n return vdom2html( plt.render() );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"md`and then linking function output to a cell containing rendered HTML`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"html`${renderPlot(plt, state_sequence, 2)}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"md`**Note**: If you re-run any of the cells above which are involved in simulation, you should see the [plot](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor) update.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"md`* * *\n\n## Discrete-time Markov Chains`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"md`We can generalize the approach used for simulating two-state Markov chains to N-state Markov chains as follows. In general, for \\`N\\` states each having probability \\`p_i\\` and satisfying`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"value":"tex`\n\\sum_{i = 0}^{N - 1} p_i = 1\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":258,"value":"md`we can randomly pick a state by drawing a uniformly distributed random number on the interval [0,1] and partitioning the cumultative probability into unique \"bins\", where each bin belongs to a particular state \\`i\\`. If the random number falls in bin \\`i\\`, the simulated state is \\`s_i\\`.\n\nFor example, let's assume we have the set of initial probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"tex`I = \\begin{bmatrix} 0.1 \\\\ 0.3 \\\\ 0.2 \\\\ 0.1 \\\\ 0.3 \\end{bmatrix}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"md`If we convert the set of initial probabilities to a set of cumulative probabilities, we have`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":269,"value":"tex`\\textrm{csum} = \\begin{bmatrix} 0.1 \\\\ 0.4 \\\\ 0.6 \\\\ 0.7 \\\\ 1.0 \\end{bmatrix}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":273,"value":"md`If we draw a uniformly distributed random number \\`r\\` and \\`r\\` is less than 0.6, but greater than 0.4, the corresponding state is \\`s_2\\`.\n\n> **Aside**: You may want to take a moment to convince yourself that the probability that we select state \\`s_i\\` using this method is, in fact, \\`p_i\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":279,"value":"md`Accordingly, let us define a function to compute the cumulative sum.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"function csum( arr ) {\n var out;\n var i;\n \n out = [];\n out.push( arr[ 0 ] );\n for ( i = 1; i < arr.length; i++ ) {\n out.push( out[ i-1 ] + arr[ i ] );\n }\n return out;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":284,"value":"md`Let's confirm that this function works as intended (subject to floating-point rounding error).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"csum( [ 0.1, 0.3, 0.2, 0.1, 0.3 ] )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"md`> **Aside**: notice that the computed values are **not** exact due to floating-point rounding error. Depending on the application, one may want to use robust arithmetic or, at minimum, a summation algorithm which minimizes accumulated error. For the purposes of this notebook where absolute precision is not required, the outlined implementation suffices.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":296,"value":"md`Let us once again define a set of initial probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":298,"value":"I = [ 0.1, 0.3, 0.2, 0.1, 0.3 ] // should sum to 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":301,"value":"md`and a matrix of transition probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"A = {\n var transition = new Array( 5 );\n \n // Transition probabilities when in state s_0:\n transition[ 0 ] = [ 0.2, 0.7, 0.1, 0.0, 0.0 ]; // should sum to 1\n \n // Transition probabilities when in state s_1:\n transition[ 1 ] = [ 0.4, 0.3, 0.25, 0.05, 0.0 ]; // should sum to 1\n \n // Transition probabilities when in state s_2:\n transition[ 2 ] = [ 0.05, 0.2, 0.4, 0.3, 0.05 ]; // should sum to 1\n \n // Transition probabilities when in state s_3:\n transition[ 3 ] = [ 0.02, 0.18, 0.2, 0.2, 0.4 ]; // should sum to 1\n \n // Transition probabilities when in state s_4:\n transition[ 4 ] = [ 0.3, 0.0, 0.0, 0.2, 0.5 ]; // should sum to 1\n \n return transition;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"md`To simulate a Markov chain of length \\`n\\`, we can generalize the approach we used previously when simulating a two-state Markov chain.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"function simulate( initial, transition, n ) {\n var nStates;\n var states;\n var probs;\n var r;\n var i;\n var j;\n \n nStates = initial.length;\n \n // Convert the initial probabilities to cumulative probabilities:\n initial = csum( initial );\n \n // Convert each set of transition probabilities to cumulative probabilities:\n transition = transition.slice(); // avoid mutation\n for ( i = 0; i < nStates; i++ ) {\n transition[ i ] = csum( transition[ i ] );\n }\n \n // Define the output state array:\n states = new Array( n );\n \n // Determine the initial state:\n r = randu();\n for ( i = 0; i < nStates; i++ ) {\n if ( r < initial[ i ] ) {\n states[ 0 ] = i;\n break; \n }\n }\n // Simulate the next `n-1` steps:\n for ( i = 0; i < n-1; i++ ) {\n probs = transition[ states[i] ];\n r = randu();\n for ( j = 0; j < nStates; j++ ) {\n if ( r < probs[ j ] ) {\n states[ i+1 ] = j;\n break;\n }\n }\n }\n return states;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"md`Let's try simulating a Markov chain of length ${n}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"viewof n = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":316,"value":"seq = simulate( I, A, n )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":324,"value":"md`To visualize the simulated state sequence, we'll create another [plot](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":326,"value":"plt2 = plot()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"md`which we can render in a manner similar to before`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"html`${renderPlot( plt2, seq, 5 ) }`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"md`**Exercise**: try adjusting the slider above to simulate Markov chains of different lengths.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":341,"value":"md`**Exercise**: try adjusting the probabilities in the transition probability matrix to explore how the transition probabilities affect Markov chain behavior.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"md`* * *\n\n## Adding Noise`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"md`More often than not, experimental data is not as pristine as the simulated state sequence above. Instead, due to a variety of factors, data is corrupted by noise, where noise is defined as the unwanted (and, in general, unknown) modification of a signal during capture, storage, transmission, processing, and/or conversion.\n\nWhile noise may be of many different forms, for the purposes of this notebook, we will only consider [Gaussian white noise](https://en.wikipedia.org/wiki/White_noise).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":361,"value":"md`To generate a noisy state sequence, let's once again define a set of initial probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"I_corrupted = [ 0.1, 0.3, 0.2, 0.1, 0.3 ] // should sum to 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"md`and a matrix of transition probabilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":371,"value":"A_corrupted = {\n var transition = new Array( 5 );\n \n // Transition probabilities when in state s_0:\n transition[ 0 ] = [ 0.2, 0.7, 0.1, 0.0, 0.0 ]; // should sum to 1\n \n // Transition probabilities when in state s_1:\n transition[ 1 ] = [ 0.4, 0.3, 0.25, 0.05, 0.0 ]; // should sum to 1\n \n // Transition probabilities when in state s_2:\n transition[ 2 ] = [ 0.05, 0.2, 0.4, 0.3, 0.05 ]; // should sum to 1\n \n // Transition probabilities when in state s_3:\n transition[ 3 ] = [ 0.02, 0.18, 0.2, 0.2, 0.4 ]; // should sum to 1\n \n // Transition probabilities when in state s_4:\n transition[ 4 ] = [ 0.3, 0.0, 0.0, 0.2, 0.5 ]; // should sum to 1\n \n return transition;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"md`In additon to \\`I\\` and \\`A\\`, let's also assign each state an observation value (i.e., in the absense of noise, what is the value you would observe, which, assuming Gaussian noise, is equivalent to the mean observed value when a simulated process is in state \\`s_i\\`)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"means = [ 0.2, 0.35, 0.5, 0.6, 0.8 ]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"md`and an expected standard deviation (i.e., how much do we expect each observed value to vary from the true state value)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"sigmas = [ 0.1, 0.1, 0.1, 0.1, 0.1 ]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"md`To help us know what the observed value would be in the absence of noise, we can define a function which returns the \"true\" underlying state sequence`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":461,"value":"function stateSequence( seq, means ) {\n var states;\n var i;\n \n states = new Array( seq.length );\n for ( i = 0; i < seq.length; i++ ) {\n states[ i ] = means[ seq[i] ];\n }\n return states;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":386,"value":"md`To corrupt a simulated state sequence, we simply iterate over the sequence and generate a pseudorandom number drawn from a normal distribution having mean μ and standard deviation σ.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"function corrupt( states, means, sigmas ) {\n var state;\n var out;\n var i;\n \n // Initialize an output array:\n out = new Array( states.length );\n \n // For each state, simulate a corrupted observation:\n for ( i = 0; i < states.length; i++ ) {\n state = states[ i ];\n out[ i ] = randn( means[ state ], sigmas[ state ] );\n }\n return out;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"md`Now, we are ready to simulate! Let's try simulating a Markov chain of length ${n_corrupted}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":393,"value":"viewof n_corrupted = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"seq_corrupted = simulate( I_corrupted, A_corrupted, n_corrupted )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":409,"value":"md`Using our function for corrupting a state sequence, we can transform the state sequence into a sequence of corrupted observations`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":411,"value":"obs = corrupt( seq_corrupted, means, sigmas )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":398,"value":"md`To visualize the simulated observations along with the true underlying state sequence, we'll create another [plot](https://github.com/stdlib-js/stdlib/tree/2589885865dd621cdc0d5b1118b9c6e0b8c45a1d/lib/node_modules/%40stdlib/plot/ctor)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"plt3 = plot()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":416,"value":"md`but this time, in order to better accommodate the plotted data, we'll want to configure the plot differently`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":419,"value":"function configurePlotCorrupted( plt, corrupted, underlying ) {\n var n;\n var x;\n \n n = corrupted.length;\n \n // Disable auto-rendering, deferring, instead, to Observable:\n plt.autoRender = false;\n \n // Plot meta data:\n plt.description = 'Simulated noisy time series.';\n plt.title = 'Simulated Time Series';\n plt.labels = [\n \t'noisy',\n 'true'\n ];\n \n // Plot dimensions:\n plt.width = 800; // pixels\n \n // x-axis configuration:\n plt.xLabel = 'Step';\n plt.xMin = -1;\n plt.xMax = n;\n \n // y-axis configuration:\n plt.yLabel = 'Observation';\n plt.yMin = 0.0;\n plt.yMax = 1.0;\n \n // Data point encoding:\n plt.colors = [\n '#1f77b4', // blue\n '#d62728' // red\n ];\n plt.symbols = 'none';\n plt.lineOpacity = [ 1.0, 0.3 ];\n \n // Values along the abscissa (x-values) will simply be a linearly spaced array representing the step number:\n x = linspace(0, n-1, n);\n plt.x = [ x, x ];\n \n // Observations:\n plt.y = [ corrupted, underlying ];\n \n return plt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"md`As we have created a new function for configuring the plot, we need to create a new wrapper function for plot rendering`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"function renderPlotCorrupted( plt, corrupted, underlying ) {\n configurePlotCorrupted( plt, corrupted, underlying );\n return vdom2html( plt.render() );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"md`We can now render the plot in a manner similar to before`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"html`${renderPlotCorrupted( plt3, obs, stateSequence( seq_corrupted, means ) ) }`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":472,"value":"md`And that's it! We have now used Markov chains to simulate noisy time series.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":474,"value":"md`**Exercise**: try adjusting the slider above to simulate Markov chains of different lengths.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":476,"value":"md`**Exercise**: try adjusting the probabilities in the transition probability matrix to explore how the transition probabilities affect Markov chain behavior.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"md`**Exercise**: try adjusting state standard deviations to explore how noise affects observations.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":480,"value":"md`* * *\n\n## Conclusion`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":482,"value":"md`In this notebook, we discussed Markov Chains at a high level, explored how to simulate a discrete-time Markov process, and saw how we could generate realistic noisy time series. In a future notebook, we'll cover continuous-time Markov chains and how we can follow a similar approach to model continuous processes exhibiting Markov behavior.\n\nIf you are interested in learning more about [stdlib](https://github.com/stdlib-js/stdlib), be sure to check out the GitHub [repository](https://github.com/stdlib-js/stdlib) and to follow updates on [Twitter](https://twitter.com/stdlibjs). :)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"md`* * *\n\n## License`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"md`\nCopyright (c) 2018 Athan Reines.\n\nLicensed under the Apache License, Version 2.0 (the \"License\");\nyou may not use this file except in compliance with the License.\nYou may obtain a copy of the License at\n\n http://www.apache.org/licenses/LICENSE-2.0\n\nUnless required by applicable law or agreed to in writing, software\ndistributed under the License is distributed on an \"AS IS\" BASIS,\nWITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\nSee the License for the specific language governing permissions and\nlimitations under the License.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 32:"$31:body"