In what follows, we consider the Boolean algebra on the set 
$\Bool=\{0,1\}$ with the classical operators of conjunction '.', 
of disjunction '+', of negation '$\overline{~}$', and of 
disjunctive union $\oplus$. 

Let $n$ be a positive integer. A  {\emph{Boolean map} $f$ is 
a function from $\Bool^n$  
to itself 
such that 
$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
Functions are iterated as follows. 
At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. 
Formally,
let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
\[
F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
\]
Then, let $x^0\in\Bool^n$ be an initial configuration
and $s\in
\llbracket1;n\rrbracket^\Nats$ be a strategy, 
the dynamics are described by the recurrence
\begin{equation}\label{eq:asyn}
x^{t+1}=F_f(s_t,x^t).
\end{equation}


Let be given a Boolean map $f$. Its associated   
{\emph{iteration graph}}  $\Gamma(f)$ is the
directed graph such that  the set of vertices is
$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. 

\begin{xpl}
Let us consider for instance $n=3$.
Let 
$f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
$f^*(x_1,x_2,x_3) = 
(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
\overline{x_1}\overline{x_3} + x_1x_2)$.
The iteration graph $\Gamma(f^*)$ of this function is given in 
Figure~\ref{fig:iteration:f*}.

\vspace{-1em}
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.5]{images/iter_f0c}
\end{center}
\vspace{-0.5em}
\caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
\end{figure}
\end{xpl}


Let thus be given such kind of map.
This article focuses on studying its iterations according to
the equation~(\ref{eq:asyn}) with a given strategy.
First of all, this can be interpreted as walking into its iteration graph 
where the choice of the edge to follow is decided by the strategy.
Notice that the iteration graph is always a subgraph of 
$n$-cube augmented with all the self-loop, \textit{i.e.}, all the 
edges $(v,v)$ for any $v \in \Bool^n$. 
Next, if we add probabilities on the transition graph, iterations can be 
interpreted as Markov chains.

\begin{xpl}
Let us consider for instance  
the graph $\Gamma(f)$ defined 
in \textsc{Figure~\ref{fig:iteration:f*}.} and 
the probability function $p$ defined on the set of edges as follows:
$$
p(e) \left\{
\begin{array}{ll}
= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
= \frac{1}{6} \textrm{ otherwise.}
\end{array}
\right.  
$$
The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
\[
P=\dfrac{1}{6} \left(
\begin{array}{llllllll}
4&1&1&0&0&0&0&0 \\
1&4&0&0&0&1&0&0 \\
0&0&4&1&0&0&1&0 \\
0&1&1&4&0&0&0&0 \\
1&0&0&0&4&0&1&0 \\
0&0&0&0&1&4&0&1 \\
0&0&0&0&1&0&4&1 \\
0&0&0&1&0&1&0&4 
\end{array}
\right)
\]
\end{xpl}


% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
% % $\Bool^n$  by:
% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
% % It is known that
% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$

% % Let then $M(x,\cdot)$ be the
% % distribution induced by the $x$-th row of $M$. If the Markov chain
% % induced by
% % $M$ has a stationary distribution $\pi$, then we define
% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
% Intuitively $d(t)$ is the largest deviation between
% the distribution $\pi$ and $M^t(x,\cdot)$, which 
% is the result of iterating $t$ times the function.
% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
% with respect to $\varepsilon$ is given by
% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
% It defines the smallest iteration number 
% that is sufficient to obtain a deviation lesser than $\varepsilon$.
% Notice that the upper and lower bounds of mixing times cannot    
% directly be computed with eigenvalues formulae as expressed 
% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
% only consider reversible Markov matrices whereas we do no restrict our 
% matrices to such a form.




