Markov processes: Construction of the state variables 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?
 A: 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$. 
