I have asked this question on [stats.se.com](https://stats.stackexchange.com/questions/325194/reinforcement-learning-definition-construction-of-state-and-action-random-var) 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?**



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


