# Random iteration of a set of monotone maps until fixed point

Let $P$ be a poset with a least element $\bot$ ($\forall x \in P.\ \bot \le x$). Let $M$ be a set of monotone maps $P \to P$. Call $x \in P$ reachable if $x = f_1(f_2(...f_n(\bot)...))$ for some sequence $f_i \in M$. Call $x$ fixed if $x = f(x)$ for all $f \in M$.

If $x$ reachable, $y$ fixed, then $x \le y$. For then $x = F(\bot)$ for $F$ some composition of functions in $M$. Since $F$ is monotone and $\bot \le y$, we have $x = F(\bot) \le F(y) = y$. Thus there is at most one reachable fixed point.

Question #1: If there is a reachable fixed point $x$, will applying functions in $M$ uniformly at random (starting from $\bot$) eventually find $x$ with probability 1?

This requires a uniform probability distribution over $M$, so is ill-defined if $M$ is infinite. So:

Question #2: If there is a reachable fixed point $x$, will any schedule which eventually includes every sequence of $M$s infinitely often eventually find $x$ (starting from $\bot$)?

For our purposes, $M$ is at most countable. I'd even be interested in a solution to the case where $M$ is finite.

Suppose $x$ is reachable and fixed. Pick $F$ with $x = F(\bot)$ to witness $x$'s reachability. Let $s$ be an arbitrary reachable element, with $F' \in M^*$ witnessing its reachability, i.e. $F'(\bot) = s$.
Observe that $F(s)$ is reachable, since $F(s) = F(F'(\bot))$. So $F(s) \le x$ because $x$ is fixed, by your own reasoning above. But $\bot \le s$ so $x = F(\bot) \le F(s)$ by monotonicity. Hence $x = F(s)$.
That is, if we start from $\bot$ and hit it with some functions $F'$ from $M$, $x$ will always remain reachable, even from that point $F'(\bot)$, by exactly the sequence of functions $F$.