Hey! So there is this interesting problem that was an exercise in my Stochastic Processes course, and I thought it would be nice to share it here.

Consider a finite set \(S\) and finitely many functions \( \{ f_i : 1 \le i \le k \} \) from \(S\) to \(S\) and a probability vector \( (p_i : 1 \le i \le k) \). Here is a Markov Chain with state space \(S\). If you are at a \(s\), select one of the functions using the probability vector. New state is value of the selected function at \(s\). This is called Iterated Function System IFS for short. Show that we do indeed have a Markov chain. What is its transition Matrix?

Conversely, show that given any transition matrix \(P\) you can produce an IFS (i.e. finitely many functions) which give back your Markov chain with transition matrix \(P\).

The forward direction is fairly straightforward (heh), but how do you do the other direction? I’ll write up my solution here eventuallyI have since this post finished a degree and moved the entire site over to a new setup, so I take the "eventually" back., but you can find my approach here.