Your History

Menu

Stochastic Discrete-Time System with Input

Prerequisites

Stochastic Discrete-Time Update Operator | \(p\left( \mathbf{X}_{n+1} = \mathbf{x}_{j} \,\vert\, \mathbf{X}_{n} = \mathbf{x}_{i} \right) = T(i, j)\)
Markov Transition Matrix Entries | \(\left[ T \right]_{i,j} = p\left( \mathbf{X}_{n+1} = \mathbf{x}_{j} \,\vert\, \mathbf{X}_{n} = \mathbf{x}_{i} \right)\)

Description

Another case for a stochastic discrete-time dynamical system is given by extending the Markov chain with inputs. These systems, also named "controlled Markov chains", have several update operators - one \( \htmlClass{sdt-0000000027}{T}_a \) for each input \( a \).

Conditioning the regular stochastic update operator on a single input yields an expression for determining transition probabilities for that input.

\[p\left( \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}+1} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000011}{j}} \,\vert\, \mathbf{randomVar}_{\htmlClass{sdt-0000000117}{n}} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000018}{i}}, \mathbf{U}_{\htmlClass{sdt-0000000117}{n}} = a \right) = \htmlClass{sdt-0000000027}{T}_a(\htmlClass{sdt-0000000018}{i}, \htmlClass{sdt-0000000011}{j})\]

Symbols Used:

This symbol represents a random variable. It is a measurable function that maps a sample space of possible outcomes to a a measurable space.
\( j \)

This is a secondary symbol for an iterator, a variable that changes value to refer to a series of elements
\( i \)

This is the symbol for an iterator, a variable that changes value to refer to a sequence of elements.

\( T \)

This is the symbol for a dynamical system's update operator.
\( \mathbf{x} \)

This symbol represents a state of the dynamical system at some time point.
\( n \)

This symbol represents any given whole number, \( n \in \htmlClass{sdt-0000000014}{\mathbb{W}}\).

Derivation

  1. Consider the update operator for a finite-state and discrete Markov system with no input:
    \[p\left( \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}+1} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000011}{j}} \,\vert\, \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000018}{i}} \right) = \htmlClass{sdt-0000000027}{T}(\htmlClass{sdt-0000000018}{i}, \htmlClass{sdt-0000000011}{j})\]
  2. The update is described by a single Markov transition matrix \( \htmlClass{sdt-0000000087}{T} \) with entries:
    \[\left[ \htmlClass{sdt-0000000087}{T} \right]_{\htmlClass{sdt-0000000018}{i},\htmlClass{sdt-0000000011}{j}} = p\left( \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}+1} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000011}{j}} \,\vert\, \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000018}{i}} \right)\]
  3. A set of inputs \( \htmlClass{sdt-0000000078}{\mathbf{u}}_1, \htmlClass{sdt-0000000078}{\mathbf{u}}_2, ..., \htmlClass{sdt-0000000078}{\mathbf{u}}_L \) is added to the Markov system results in state updates that depend on the input (a controlled Markov Chain)
  4. Each input has a corresponding Markov matrix \( \htmlClass{sdt-0000000087}{T}_{\htmlClass{sdt-0000000078}{\mathbf{u}}_1}, \htmlClass{sdt-0000000087}{T}_{\htmlClass{sdt-0000000078}{\mathbf{u}}_2}, ..., \htmlClass{sdt-0000000087}{T}_{\htmlClass{sdt-0000000078}{\mathbf{u}}_L} \) that controls the update: if the system is given \( \htmlClass{sdt-0000000078}{\mathbf{u}}_k \), the update operator will be given by the matrix \( \htmlClass{sdt-0000000087}{T}_{\htmlClass{sdt-0000000078}{\mathbf{u}}_k} \).
  5. Conditioning the relation at (1) on the input as a random variable \( \mathbf{U}_{\htmlClass{sdt-0000000117}{n}}\) at time \( \htmlClass{sdt-0000000117}{n} \) with the realization \( \mathbf{U}_{\htmlClass{sdt-0000000117}{n}} = a \) results in the input-adjusted equation:
    \[ p\left( \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}+1} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000011}{j}} \,\vert\, \mathbf{\htmlClass{sdt-0000000005}{X}}_{\htmlClass{sdt-0000000117}{n}} = \htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000018}{i}}, \mathbf{U}_{\htmlClass{sdt-0000000117}{n}} = a \right) = \htmlClass{sdt-0000000027}{T}_a(\htmlClass{sdt-0000000018}{i}, \htmlClass{sdt-0000000011}{j}) \]
    as required.

References

  1. Jaeger, H. (n.d.). Neural Networks (AI) (WBAI028-05) Lecture Notes BSc program in Artificial Intelligence. Retrieved May 17, 2024, from https://www.ai.rug.nl/minds/uploads/LN_NN_RUG.pdf