Markov processes: Construction of the state variables

Question

I have asked this question on stats.se.com but I did not receive an answer. Given is the description of a probabilistic finite state machine and I want to 'translate this' into a Markov process 'on it'. The input is (in the most simple case)

• A finite set of states $S = \{s^{(1)}, ..., s^{(N)}\}$
• A function $\Delta^d : S \times S \to [0,1]$ such that for every $s$, $\sum_{t \in S} \Delta^d(s,t) = 1$ (indicates the probability of moving from $s$ to $t$).
• An initial distribution $I^d : S \to [0,1]$ such that $\sum_{t \in S} I^d(t) = 1$ (indicating the probability for the initial state).

We imagine this input as a probabilistic finite state machine that offers 'different runs through it'. A single concrete (infinitely long) run is a sequence $s = (s_n)_{n \in \mathbb{N}}$ where $s_n \in S$ for every $n$. In order to understand this process better we attempt to model these runs by outcomes of random variables $S = (S_n)_{n \in \mathbb{N}}$. The question is simple:

Can we construct $S_n$ concretely and if so, how?

My attempt:

Of course we could simply assume that there are infinitely many RV $S_n$ and then state assumptions like the markovian property $$p(s_n|s_1,...,s_{n-1}) = p(s_n|s_{n-1})$$ and the coupling between the $S_n$ and the input (for example, $p(s_1) = I^d(s_1)$ and if $s_m = s_n$ and $s_{m-1} = s_{n-1}$ then $p(s_n|s_{n-1}) = p(s_m|s_{m-1}) = \Delta^d(s_{n-1},s_n)$). However, we could also 'construct' these random variables (except for the first one) in a natural way: We simply follow the rules given by the input:

What the input actually wants to state is that $\Delta^d$ gives rise to a single random variable $\Delta : S \times \Omega \to S$ such that for every $s,t \in S$, $$P[\Delta(s,\cdot) = t] = \Delta^d(s, t)$$ i.e. $\Delta$ selects (in a random fashion) the next state given that the current state is $s$. This should philosophically be in line with the assumptions above because in some sense, $$''S_n|S_{n-1} = S_m|S_{m-1} = \Delta''$$ for all $m,n$.

We have a first random variable $S_1 : \Omega \to S$ and for this one we assume that $P(S_1=s_1) = I^d(s_1)$. Now for $S_2$ we construct it as $$S_2(\omega) = \Delta(S_1(\omega), \omega)$$ i.e. see what the first sampled state was and then follow the 'way of $\Delta$'.

Of course I want to see that these constructions are in line now. Hence I want to have $$p(s_2|s_1) = \Delta^d(s_1, s_2)$$ but all I get is $$p(s_2|s_1) = P[S_2=s_2|S_1=s_1] = \frac{P(\omega | \Delta(S_1(\omega), \omega) = s_2 ~\text{and}~ S_1(\omega)=s_1)}{I^d(s_1)}$$ and this is equal to the desired outcome $\Delta^d(s_1, s_2)$ iff. $$P[\Delta(s_1, \cdot) = s_2 ~\text{and}~ S_1=s_1] = \Delta^d(s_1, s_2) \cdot I^d(s_1) = P[\Delta(s_1, \cdot) = s_2] \cdot P[S_1=s_1]$$ but assuming that the random variables $\Delta(s_1, \cdot)$ ('close' to $S_2$) and $S_1$ are independent is somewhat like assuming that $S_2$ and $S_1$ are independent (which should not be true!).

Am I modelling it in a wrong way?

Answer 1

The Markov chain construction you want you should able to find in any text on Markov chains/processes or even in texts on probability/stochastic processes in general. Yet, it is simpler to give the construction than to look for it in the literature.

Indeed, let $p_0:=I^d$ and $p:=\Delta^p$, the "initial distribution" and the transition matrix, respectively. Let $S_0$ be any random variable (r.v.) such that $P(S_0=s)=p_0(s)$ for all $s\in S$. For each natural $n$ and each $s\in S$, let $X_{n,s}$ be a r.v. such that $S_0,(X_{1,s})_{s\in S},(X_{2,s})_{s\in S},\dots$ are independent and $P(X_{n,s}=t)=p(s,t)$ for all natural $n$ and all $s$ and $t$ in $S$. Finally, with $S_0$ already defined, define the r.v. $S_n$ for all natural $n$ recursively by the condition that $S_n=X_{n,s}$ on the event $\{S_{n-1}=s\}$, for each $s\in S$.

Then for any natural $n$ and any $s_0,\dots,s_n$ in $S$, \begin{multline*} P(S_n=s_n|S_0=s_0,\dots,S_{n-1}=s_{n-1}) =\frac{P(S_0=s_0,\dots,S_{n-1}=s_{n-1},S_n=s_n)}{P(S_0=s_0,\dots,S_{n-1}=s_{n-1})} \\ =\frac{P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1},X_{n,s_{n-1}}=s_n)} {P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} =P(X_{n,s_{n-1}}=s_n) \end{multline*} and, similarly, \begin{multline*} P(S_n=s_n|S_{n-1}=s_{n-1}) =\frac{P(S_{n-1}=s_{n-1},S_n=s_n)}{P(S_{n-1}=s_{n-1})} \\ =\frac {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1},X_{n,s_{n-1}}=s_n)} {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} \\ =\frac {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})\,P(X_{n,s_{n-1}}=s_n)} {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} \\ =P(X_{n,s_{n-1}}=s_n). \end{multline*} So, \begin{equation} P(S_n=s_n|S_0=s_0,\dots,S_{n-1}=s_{n-1})=P(S_n=s_n|S_{n-1}=s_{n-1})=P(X_{n,s_{n-1}}=s_n) =p(s_{n-1},s_n), \end{equation} so that $S_0,S_1,\dots$ is indeed a Markov chain with "initial distribution" $p_0$ and transition matrix $p$.