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?**