Markov Chains versus Iterated Function Systems

An iterated function system on a space \(S\) is a collection \(F\) of \(K\) endofunctions \(f_k\colon S \to S\) with index \(k \in [K]\). Given a starting point \(s_0 \subseteq S\), we consider sequences \(s_{n+1} = f_{k_n}(s_n)\) where another sequence \(k_n \in [N]\) selects the applied function at each step. Note that the starting point and selection rule should also be considered part of the data that make up an iterated function system. Typically, these systems are associated with fractal geometry. A natural question is, whether and what this sequence converges towards. An answer is available, if all the functions are assumed strictly contractive. The simplest case is just rotating through \(f_1, \ldots, f_K\) in a cycle, that is, \(k_n \equiv n \mod K\) for all \(n \in \mathbb{N}\). Note that this reduces to repeatedly applying the endofunction \(f = f_K \circ \cdots \circ f_1\) and thus directly falls under the realm of standard fixed-point iteration theorems. Wether the fixed point of \(f\) also is one for each \(f_k\) is a reasonable question. A more interesting setting is to randomly choose \(k_n\) iid for each \(n \in \mathbb{N}\). Indeed, this defines a discrete time Markov chain over the state space \(S\). In light of this, one may wonder what is the stationary distribution of this chain. A converse statement also holds: any discrete time Markov chain over a discrete state space \(S\) with rational transition probabilities can be represented as an iterated function system on \(S\) with iid selection via a distribution. To this end, let \(M\) be the least common multiple of denominators in normalized fractional representations (that is, numerator and denominator are coprime) of each transition probability. We define the collection \(F\) to consist of \(M\) functions, defined as follows. Note that we can define the functions at each state \(s \in S\) independently; the system is far from unique. For each state \(s\) we simply let \(m\) of them map \(s\) to \(s'\) where the corresponding transition probability in the chain would be \(m/M\). Since all the fractions must add to \(1\), this defines exactly \(M\) functions in total. Now the function is simply chosen uniformly at each step.

As an example, we convert the Markov chain