\documentclass{article}
%\usepackage{prentcsmacro}
%\sloppy

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc} 
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
\usepackage{subfigure,pstricks,pst-node,pst-coil}


\usepackage{url,tikz}
\usepackage{pgflibrarysnakes}

\usepackage{multicol}

\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\usetikzlibrary{snakes}
\usetikzlibrary{shapes}

%% \setlength{\oddsidemargin}{15mm}
%% \setlength{\evensidemargin}{15mm} \setlength{\textwidth}{140mm}
%% \setlength{\textheight}{219mm} \setlength{\topmargin}{5mm}
\newtheorem{theorem}{Theorem}
%\newtheorem{definition}[theorem]{Definition}
% %\newtheorem{defis}[thm]{D\'efinitions}
 \newtheorem{example}[theorem]{Example}
% %\newtheorem{Exes}[thm]{Exemples}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{algor}[thm]{Algorithm}
%\newtheorem{propdef}[thm]{Proposition-D\'efinition}
\newcommand{\mlabel}[1]{\label{#1}\marginpar{\fbox{#1}}}
\newcommand{\flsup}[1]{\stackrel{#1}{\longrightarrow}}

\newcommand{\stirlingtwo}[2]{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}
\newcommand{\stirlingone}[2]{\genfrac{\lbrack}{\rbrack}{0pt}{}{#1}{#2}}

\newenvironment{algo}
{ \vspace{1em}
\begin{algor}\mbox
\newline \vspace{-0.1em}
\begin{quote}\begin{rm}} 
{\end{rm}\end{quote}\end{algor}\vspace{-1.5em}\vspace{2em}}
%\null \hfill $\diamondsuit$ \par\medskip \vspace{1em}}

\newenvironment{exe}
{\begin{example}\rm } 
{\end{example}
%\vspace*{-1.5em}
%\null  \hfill $\triangledown$ \par\medskip}
%\null  \hfill $\triangledown$ \par\medskip \vspace{1em}}
}


\newenvironment{proof}
{ \noindent {\sc Proof.\/}  }
{\null  \hfill $\Box$ \par\medskip \vspace{1em}}


\newcommand {\pb}[3] {
\medskip
\noindent
\fbox{
\parbox[c]{11.5cm}{
{\bf #1}

\noindent
{\bf Input:} #2

\noindent
{\bf Output:} #3

\medskip
}
}

\medskip
}


\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
\def \top {1.8}
\def \topt {2.3}
\def \sp {\hspace*{0.8cm}}
\def \A {\mathcal{A}}
\def \P {\mathcal{P}}
\def \B {\mathcal{B}}
\def \C {\mathcal{C}}
\def \D {\mathcal{D}}
\def \R {\mathcal{R}}
\def \T {\mathfrak{T}}
\def \M {\mathcal{M}}
\def \ov {\overline}

\begin{document}
\label{firstpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mathematical Backgroung}

Let $G$ be a finite group. For any subset $S$ of $G$ we denote by 
$<S>$ the subgroup of $G$ generated by $S$. 
If $<S>=G$, $S$ is a generator of $G$.



Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total
variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
defined by
$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ It is known that
$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$ Moreover, if
$\nu$ is a distribution on $\Omega$, one has
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$

Let $P$ be the matrix of a markov chain on $\Omega$. $P(x,\cdot)$ is the
distribution induced by the $x$-th row of $P$. If the markov chain induced by
$P$ has a stationary distribution $\pi$, then we define
$$d(t)=\max_{x\in\Omega}\tv{P^t(x,\cdot)-\pi},$$
and

$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
One can prove that

$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$

It is known that $d(t+1)\leq d(t)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{PRNG and random walk on Cayley graphs}


Let $S$ be a generator of $\mathbb{B}^N$ such that if $s\in S$, then
$-s\in S$. Let $\nu$ be a distribution on $S$ such that
$\nu(s)=\nu(-s)$. The matrix $P^\nu$, or just $P^\nu$, or just $P$,
is the matrix defined by: $P^\nu(x,y)=\nu(y-x)$ if $x-y\in S$ and $0$
otherwise.  $P_S^\nu$ is the $\nu$-random walk on the $S$-Cayley graph
of $G$.

A general results on random walks claims that the uniform distribution
is stationnary for $P$. Moreover, if $\nu(s)>0$ for each $s$, then
this is the limit distribution.

Let $\mathcal{P}$ be finite subset of $\mathbb{N}$ and $\mu$ a distribution
on  $\mathcal{P}$. Set
$$ P_{\mathcal{P},\mu}=\sum_{k\in\mathcal{P}}\mu(k)P^k.$$


With the above notation, $P_{\mathcal{P},\mu}$ is the matrix of the markov
chain corresponding to the PRNG defined by Christophe, where $S$ corresponds
to the boolean functions and $\mu$ si the probability of choosing elements
of $\mathcal{P}$. 


\begin{exe}
For instance let $e_i$ be the vector of $\mathbb{B}^N$ whose $i$-th
componenent is $1$ and all other compoennts are null. Let $e_0=0$ and
$S=\{e_i\mid 0\leq i\leq N\}$.  Choosing $\nu(e_i)=\dfrac{1}{N+1}$, we
obtain the random walk defined by the {\em bit negation} of the paper
by Christophe and JEF.
The associated matrix will be denoted $P_1$.
 Choosing $\mathcal{P}=\{10,11\}$ and
$\mu(10)=\mu(11)=\dfrac{1}{2}$ provides the PRNG with steps of lengths
10 or 11 with the same probability.
\end{exe}


\begin{exe}
With the same notation, choosing the same $S$, but
$\nu(e_i)=\dfrac{1}{2n}$ if $i \geq 1$ and $\nu(e_0)=1/2$ leads to the
the classical lazy random walk on $\mathbb{B}^N$ (also known as the
lazy random walk on the hypercube or as the Ehrenfest Urn Model).
The associated matrix will be denoted $P_2$.
\end{exe}

\begin{exe}
Choosing $S=G$ and the uniform distribution for $\nu$ corresponds to
the xor approach of the paper with Raphael.
\end{exe}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}

The main result is that if the minimal element of $\mathcal{P}$ is
greater or equal to the mixing time of $P$, then the PRNG provides a distribution 
whose distance to the uniform distribution is at most $\varepsilon$. 

Let $t_P(\varepsilon)$ be the $\varepsilon$ mixing time for $P$.
Without loss of generality we assume that if $k\in \mathcal{P}$, then
$\mu(k)>0$.

\begin{proposition}
Let  $k_0=\min \{ k\mid k\in \mathcal{P}\}$.
If $k_0 \geq
t_P(\varepsilon)$, and if $\nu(s)>0$ for all $s\in S$, then one has
$\tv{P_{\mathcal{P},\mu}(x,\cdot)-\pi}\leq \varepsilon$, where $\pi$
is the uniform distribution.
\end{proposition}

\begin{proof}
The fact that $\nu(s)>0$ for all $s\in S$ ensures that the uniform
distribution is the limits of the markov chains induced by $P$
(classical results on random walks).

Now,
\begin{align*}
\tv{P_{\mathcal{P},\mu}(x,\cdot)-\pi}&=\tv{\sum_{k\in\mathcal{P}}\mu(k)P^k(x,\cdot)-\pi}\\
&=\frac{1}{2}\sum_{y\in\mathbb{B}^N}|\sum_{k\in\mathcal{P}}\mu(k)P^k(x,y)-\dfrac{1}{2^N}|\\
&=\frac{1}{2}\sum_{y\in\mathbb{B}^N}|\sum_{k\in\mathcal{P}}\mu(k)P^k(x,y)-\dfrac{1}{2^N}\sum_{k\in\mathcal{P}}\mu(k)|\\
&=\frac{1}{2}\sum_{y\in\mathbb{B}^N}|\sum_{k\in\mathcal{P}}\mu(k)(P^k(x,y)-\dfrac{1}{2^N})|\\
&\leq \frac{1}{2}\sum_{y\in\mathbb{B}^N}\sum_{k\in\mathcal{P}}\mu(k)|P^k(x,y)-\dfrac{1}{2^N}|\\
&\leq \sum_{k\in\mathcal{P}}\mu(k)\left(\frac{1}{2}\sum_{y\in\mathbb{B}^N}|P^k(x,y)-\dfrac{1}{2^N}|\right)\\
&\leq \sum_{k\in\mathcal{P}}\mu(k)\tv{P^k(x,\cdot)-\pi}\\
&\leq \sum_{k\in\mathcal{P}}\mu(k)\varepsilon\\
&\leq \varepsilon\\
\end{align*}
\end{proof}


Therfore it suffices to study the mixing time of $P$. 



%%%%%%%%%%%%%%%%%%%%
\section{Mixing time of $P_1$}

See the  Ehrenfest Urn Model. One can prove that for $P_1$,

$$t_{\rm mix}(\varepsilon)\leq N \log N+ \log (\frac{1}{\varepsilon})N.$$

Better results exist see \cite[page 83, page 267]{mixing}

%%%%%%%%%%%%%%%%%%%%
\section{Mixing time of $P_2$}

In practice one can compute egenvalues and  use \cite[page 155]{mixing}.

There are theoretical results \cite[page 321-322]{rwfg} and~\cite{WilsonHyper}.


%%%%%%%%%%%%%%%%%%%%
\section{To do}

Experiments for computing mixing time for $P_2$.

Experiments for other $P$ (handly built)

Which $\varepsilon$ makes possible to pass statistical tests for our PRNGs. Other tests can be performed. 

%%%%%%%%%%%%%%%%%%%%%%
\section{Future}

Look at \cite{rwfg} for theoretical results. Explore random random walk on the hypercube. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{alpha}
\bibliography{markovbib}
\end{document}
