%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                             %
%   Exact Mixing in an Unknown Markov Chain   %
%                                             %
%      by Laszlo Lovasz and Peter Winkler     %
%                                             %
%       LaTeX source for a 12 p. article      %
%                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[11pt]{article}

\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R15\hfill} 
\thispagestyle{empty} 

\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-.35in}
\addtolength{\textwidth}{1.2in}
\addtolength{\textheight}{1.5in}
\def\E{{\rm E}}
\newlength{\originalbase}
\setlength{\originalbase}{\baselineskip}
\newcommand{\spacing}[1]{\setlength{\baselineskip}{#1\originalbase}}
\newcommand{\ep}{\epsilon}
\begin{document}
\spacing{1.5}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{guess}{Conjecture}
\newtheorem{conjecture}{Conjecture}
\def\proofend{\hfill$\Box$\medskip}
\def\Proof{\noindent{\bf Proof. }}
\begin{center}
{\Large\bf Exact Mixing in an Unknown Markov Chain}\\[5mm]
{\bf L\'aszl\'o Lov\'asz} and {\bf Peter Winkler}\\[8mm]
Submitted: May 2, 1995; Accepted: May 27, 1995.\\[12mm]
\end{center}
 
 
\begin{abstract}
We give a simple stopping rule which will stop an unknown, irreducible
$n$-state Markov chain at a state whose probability distribution is
exactly the stationary distribution of the chain.  The expected
stopping time of the rule is bounded by a polynomial in the maximum
mean hitting time of the chain.  Our stopping rule can be made
deterministic unless the chain itself has no random transitions.
\end{abstract}
 
\medskip

\noindent {\small\em Mathematics Subject Classification:} 60J10

\noindent {\small\em Key Words and Phrases:} Markov chain, stopping time,
mixing, stationary distribution

\medskip
 
\section{Introduction}
 
Suppose a Markov process $s_0, s_1, s_2, \ldots$ on the state space
$\{1,2, \ldots, n\}$ is observed, with no knowledge either of the
transition probabilities or the distribution of $s_0$.  Unless the process
is reducible (some states inaccessible from others) or periodic,
the probability distribution of the state $s_m$ will be
approximately equal to the stationary distribution $\pi$ of the process,
for $m$ sufficiently large.
 
In fact, this approach to sampling from a state space according to
the stationary distribution is the basis for numerous recent estimation
algorithms (see, e.g., \cite{A1}, \cite{DFK}, \cite{JS}).  Typically
the initial state is fixed, the process is reversible (representable
as a random walk on a graph) and some bound is obtained for the
``mixing time'' $m$.  The payoff has been polynomial time randomized
approximation algorithms for counting combinatorial objects such as
matchings \cite{JS,B}, linear extensions \cite{KK}, and Eulerian
orientations \cite{MW}; estimating the volume of a convex
body \cite{DFK,LS}; and for Monte Carlo integration \cite{AK}.
 
There is no {\em a priori} reason why a state must be sampled at a
fixed number of steps.  If the transition probabilities are known,
a stopping rule which ``looks where it is going'' is capable of reaching
the stationary distribution rapidly and exactly; in \cite{ALW}
a construction is given for intelligent stopping rules that
achieve any target distribution in both the minimum expected number
of steps and the minimum maximum number of steps. Several formulas
and bounds are given for the number of steps $T_{\rm mix}$
required by an optimal stopping rule (starting from the worst state).
 
When the transition probabilities are not known, an intelligent stopping
rule can be used to examine the process and then estimate how many
steps must be taken to approximate the stationary distribution.  Using
this approach Aldous \cite{A93} comes within total variation
$\epsilon$ of the stationary distribution in time polynomial in
$1/\epsilon$ and linear in the maximum hitting time of the chain.
 
Since it is obviously impossible to {\em compute} the stationary
distribution of an unknown chain exactly, it seems a bit surprising that
one can {\em achieve} it exactly.  Nonetheless that is what is done in
Asmussen et al.\ \cite{AGT}.   However, the algorithm employed there is
complex and requires perfect generation of random variables with
certain exponential distributions.  The expected number of steps
required appears to be super-polynomial in the maximum hitting
time, although no bound or estimate is given in the paper.
 
It turns out, however, that there is a simple, 
combinatorial stopping rule which
can reach the stationary distribution exactly, in any irreducible,
$n$-state Markov chain; the rule requires only coin-flips for its
randomization and can even be made deterministic unless the
chain itself is completely deterministic.  The expected stopping time
of the randomized rule is bounded by a polynomial (namely, $6h^4$) in the
maximum hitting time of the chain. 

We point out that this time bound is not good enough for
the randomized algorithms mentioned above, since in them the approximately
stationary distribution is achieved in a time $O(T_{\rm mix})$,
which is typically polylogarithmic in $h$. But this shortcoming of our
algorithm cannot be fixed; we will show that mixing in an
unknown Markov chain cannot be achieved in time less than $h$.
 
 
\medskip
 
\section{Notation and Preliminaries}
 
In what follows $M =  \{p_{ij}\}$ is the transition matrix for an
irreducible Markov chain on the state space $S = \{1,2, \ldots, n\}$.
Let $\pi = (\pi_1, \ldots, \pi_n)$ be the stationary distribution of
the chain, so that $\pi^{\sf T} M = \pi^{\sf T}$.
 
Following the notation of Aldous (see e.g.\ \cite{A1}), we let
$T_j$ be the number of steps before first arrival at state $j$,
with $\E_iT_j$ being the expected value of $T_j$ when the
process is begun in state $i$.  Then what we have been calling the
``maximum hitting time'' is $\max_{i,j \in S}\E_iT_j$ and will
be denoted here by the letter $h$. The maximum hitting time is a lower
bound on the {\it cover time}, which is the expected number of steps before
all states are visited, maximized over all starting states.
 
We think of a stopping rule as a (possibly randomized) algorithm which,
based on states so far seen, decides at each step whether to stop the
Markov chain. Since we are interested in stopping rules that work for an
unknown chain, the rule must decide when to stop based on the {\it pattern}
of the states visited.
This implies that such a rule needs substantial time; for example, we
cannot rely on repetitions before $n$ steps. (The ``time'' taken by a
stopping rule is merely the expected number of steps before stopping, and
has nothing to do with the computational complexity of the algorithm
itself. However, our algorithm will only use polynomial time computations.)
In fact, we show that the cover time is a lower bound on the expected
number of steps. This follows immediately from the next observation.
 
\begin{prop}
Let the number $n$ of states be fixed. Consider any stopping rule that
decides when to stop based on the pattern of the states seen before, and
assume that for every Markov chain on $n$ states, the distribution of the
state where it stops is the stationary distribution. Then it never
stops without visiting all nodes.
\end{prop}
 
\Proof Consider any Markov chain $M$ on $n$ states, and consider a walk
$(v_0,\dots,v_t)$ that is stopped before seeing all states, and let $j$ be
state not visited.  We replace $j$ by a nearly absorbing state as follows.
Construct a new Markov chain $M'$ by replacing $p_{ji}$
by $\delta p_{ji}$ for all $i\not= j$ and $p_{ii}$ by $1-\delta(1-p_{jj})$,
where $\delta$ is very small. The stationary distribution of the new chain
is $\pi'_i=\delta\pi_i/(\pi_i+\delta-\delta\pi_i)$ for $i\not= j$ and
$\pi'_j= \pi_j/(\pi_j+\delta-\delta\pi_j)$. The walk $(v_0,\dots, v_t)$
has the same probability in the old chain as in the new, and hence it must
not exceed $\pi'(v_t)$, which tends to $0$ as $t\to\infty$. This is a
contradiction. \proofend
 
The same argument holds if we assume only that the probability of stopping
at any state is at most some constant times its stationary probability.
 
\section{Random Trees}
 
\noindent {\bf Definition.}
Let $j \in S$.  A {\em $j$-assignment} is a function $A_j:~S \setminus
\{j\} \longrightarrow S$.  The {\em weight} $w(A_j)$ is defined by
$$
w(A_j) := \prod_{i \not= j} p(i,A_j(i))~.
$$
We may, for example, define a $j$-assignment $A_j^t$ by ``first exit
after time $t$'', that is, $A_j^t(i) = w_{k+1}$ where $k = \min\{t':~
t' \geq t\ {\rm and } w_{t'}=j\}$.  Then we can interpret $w(A_j)$ as
the probability $\Pr (A_j^t = A_j)$ that a particular assignment $A_j$
occurs in this construction, since all the exits are independent.
 
A $j$-assignment $A_j$ defines a directed graph on $S$ by placing
an arc from $i$ to $A_j(i)$ for each $i \not= j$; we say that $A_j$ is
a {\em $j$-tree} if this graph is a tree, necessarily an in-directed
tree rooted at $j$.  We denote by $\Upsilon_j$ the set of all $j$-trees
on $S$.  The following ``random tree lemma'' (which can be verified by
straightforward substitution) has been, according to Aldous \cite{A2},
frequently rediscovered; the earliest explicit reference we know of is
\cite{FW}, but it also follows easily from Tutte's matrix-tree theorem
(see e.g \cite{Berge}).
 
\begin{lemma}\label{tree}
For any state $j \in S$,
$$
\pi_j = w(\Upsilon_j)/\sum_{i \in S} w(\Upsilon_i)
$$
where $w(\Upsilon_i) := \sum_{A \in \Upsilon_i} w(A)$.
\end{lemma}
 
\noindent {\bf Remark.} It may be instructive to describe the following
construction related to the lemma.
Run the Markov process given by $M$ from $-\infty$ to $+\infty$ and
for each time $t$, define a $k$-assignment $A^t$ by {\em last prior exit},
where $k$ is the state of the chain at time $t$.  In other words,
for each $i \not= k$, if $t_i$ is the last time before $t$ at which the
chain is in state $i$, then $A^t(i)$ is defined to be the state of
the chain at time $t_i+1$.  Note that $A^t$ must be a tree, rooted at $k$,
since all the arcs are oriented forward in time.  Furthermore, $A^{t+1}$
depends only on $A^t$ and the state at time $t+1$, so we now have a
stationary Markov process on trees.
 
Suppose now that the probability distribution of the tree observed at
time $t$ is given by $\Pr(A^t) = cw(A^t)$, where $c$ is (necessarily)
the reciprocal of the sum of the weights of all trees on the state space $S$.
If a certain fixed tree $A$ rooted at $k$ is to occur at time $t+1$,
then its predecessor, the tree $A^t$ at time $t$, must be constructible
from $A$ by adding the arc $k \rightarrow i$ for some $i$, and then
removing exactly the arc $i \rightarrow j$ where $j = j(i)$ is the
last state before $k$ in the path from $i$ to $k$ in $A$.  For such an
$A^t$ the {\em a priori} probability of achieving $A$ at the next step is
just $p_{j,k}$, thus the total probability of seeing $A$ at time $t+1$ is
$$
\sum_{i \in S} \left[ p_{j(i),k} \left( cw(A) \cdot
{p_{k,i} \over p_{j(i),k}} \right) \right] = cw(A)~.
$$
It follows that $cw( \cdot )$ is the stationary distribution for our
tree process, but of course the stationary distribution for the roots
is just $\pi$ so we have that $\pi_i$ is proportional to
$w(\Upsilon_i)$.
 
Aldous \cite{A2} and Broder \cite{B1} use a closely related 
construction to design an
elegant algorithm to generate a random spanning tree of a graph.
 
\medskip
 
Lemma \ref{tree} already provides a stopping rule, described below, that
attains the stationary distribution. In contrast to the procedure described
above, the stopping rule constructs a random $j$-assignment by looking {\em
forward} in time; then, as previously noted, the probability of a given
assignment is exactly its weight, independent of the starting state.  The
price we pay is that the assignment is no longer necessarily a tree.
 
\begin{enumerate}
\item
Choose a state $j$ uniformly from $S$, and set current time equal to 0.
\item
For each $i \in S \setminus \{j\}$ let $t_i$ be the least $t \ge 0$ at
which the chain is in state $i$, and set $A_j(i)$ to be the state of the chain
at time $t_i+1$.
\item
By the time every state $i \in S \setminus \{j\}$ has been exited,
we will know whether the resulting assignment $A_j$ is a tree.  If it is,
we continue until the chain reaches $j$ and then stop; if not, we repeat
step 1.
\end{enumerate}
 
Since the chain is irreducible, step 2 is finite with probability 1 and
there must be some tree assignment which is eventually reached, say
at iteration $k$.  Letting $T_i$ be the tree assignment constructed
at that time, we have that Pr(the rule stops at $j$) = Pr($i=j$) =
Pr($T_i \in \Upsilon_j~|~T_i$ is a tree assignment) = $\pi_j$.
Unfortunately it may be the case that Pr($A_j$ is a tree) is
exponentially small in $n$, even when the Markov chain has no small positive
transition probabilities.  For example, in a simple random walk on an
$n$-cycle, where $p_{i,i+1} = p_{i+1,i}=1/2$ for $i=0,\dots,n-1$ mod $n$,
our stopping rule takes more than $2^n$ steps on average while the
maximum expected time to hit a given state is only $n^2/4$.
 
To speed up the stopping rule, we make use of the fact that for an
independent stochastic process (i.e.\ a Markov chain whose transition matrix
has identical rows) the probability that a random assignment
is a tree is fairly high---in fact, surprisingly, it depends only on $n$.
The following lemma has appeared in many guises and is deducible, for
example, from Theorem 37 of Chapter XIV in Bollob\'as \cite{BOL}; we give
an independent proof.
 
\begin{lemma}\label{indep}
Let $X_1,\dots,X_n$ be i.i.d.\ random variables with values in $S$.
Define an assignment $A_j$ by choosing $j \in S = \{1,2, \ldots, n\}$
uniformly at random, then setting $A_j(i) = X_i$ for $i \not= j$.
Then Pr($A_j \in \Upsilon_j) = 1/n$.
\end{lemma}
 
\Proof
Let $m_1, \ldots, m_n$ be non-negative integers which sum to $n-1$.
We may build an in-directed tree in which vertex $i$ has in-degree
$m_i$ as follows:  assuming that the in-neighbor sets $N^{\rm in}(1),
\ldots, N^{\rm in}(k-1)$ have already been chosen, we select
$N^{\rm in}(k)$ from
$$
S \setminus \cup_{i=1}^{k-1}N^{\rm in}(i) \setminus \{j\}
$$
where $j$ is the root (possibly $k$ itself) of the component currently
containing $k$.  It follows that the number of such trees is
$$
{n-1 \choose m_1}\cdot{n-m_1-1 \choose m_2}\cdot{n-m_1-m_2-1 \choose m_3}
\cdot \cdots \cdot{m_n \choose m_n} = {n-1 \choose {m_1,m_2, \ldots,
m_n}}~.
$$
Since the weight of such a tree is $\prod_{i=1}^n p_i^{m_i}$ where
$p_i$ = Pr($X = i$), we have that the sum of the weights of all the
in-directed trees is
$$
\sum_{m_1+ \cdots +m_n = n-1}{n-1 \choose {m_1,m_2, \ldots, m_n}}
\prod_{i=1}^n p_i^{m_i} = (p_1+ \cdots +p_n)^{n-1} = 1
$$
and thus the desired probability is
$$
{1 \over n}\sum_{j=1}^n {\rm Pr}(A_j \in \Upsilon_j)~=~{1 \over n}~.
$$
\proofend
 
\medskip
 
\section{A Randomized Stopping Rule}
 
To make use of Lemma \ref{indep} we need to replace the transition
matrix $M$ by a new matrix $N$ having the same stationary distribution
but which represents a nearly independent process; in other words,
the rows of $N$ should be similar to one another (and therefore
to the stationary vector $\pi$).
 
An obvious candidate for $N$ is $M^t$, for $t$ some polynomial in
$n$ and the maximum hitting time $h$, and in fact this
choice will suffice for reversible Markov chains.  In general,
however, ``mixing time'' may be exponentially larger than both $n$
and $h$.  For example, suppose $p_{i,i+1}=1$ for $i=1, \ldots, n-1$,
$p_{n,1} = 1-2^{-n}$, $p_{n,n} = 2^{-n}$ and all other transitions
are forbidden.  Then $h$ is only about $n$ but the state of the chain
$t$ steps after being at state $j$ is $j+t$ (mod $n$) with high
probability for fixed $t < 2^n$.
 
Instead we take $N$ to be an average of the matrices $M^k$ for $k$
between 1 and some sufficiently large bound $t$.
 
\begin{lemma}\label{mix}
Let $M$ be the transition matrix for an $n$-state irreducible Markov
chain $(v^0,v^1,\dots)$
with stationary distribution $\pi$ and maximum hitting time $h$, and
let $t\ge 1$. Let $Z$ be chosen uniformly from $\{1,\dots, t\}$. 
Then for every state $j$,
$$
\Pr(v^Z=j) \geq (1 - {h \over t})\pi_j.
$$
\end{lemma}

\Proof
Let $s$ be any positive integer, and let $Y_j^s$ be a random variable
which counts the number of hits of state $j$ in the next $s$ steps
of the chain $M$.  Again using Aldous' notation, we
let $\E_{\sigma}Y_j^s$ be the expected value of $Y_j^s$ when the chain
is begun in a state drawn from the distribution $\sigma$; if $\sigma$ is
concentrated at $i$ we just write $\E_iY_j^s$.
 
For any $i$ and $s$, we have $\E_iY_j^s \leq 1 + \E_jY_j^s$
(by waiting for the first occurrence of $j$) and thus in particular,
$\pi_j = {1 \over s}\E_{\pi}Y_j^s \leq {1 \over s}(1 + \E_jY_j^s)$.
 
Fix $i$ and $j$ and let $q_s$ be the probability that, when started at
state $i$, the first occurrence of state $j$ is at step $s$.  By definition
of $N$, we have
\begin{eqnarray*}
\Pr(v^Z=j) &=& {1 \over t}\E_iY_j^t = {1 \over t}\sum_{s=1}^t q_s
(1 + \E_jY_j^{t-s}) \\
 &\ge& {1 \over t}\sum_{s=1}^t q_s(\pi_j(t-s)) \\
 &=& \pi_j - {\pi_j \over t}\sum_{s=1}^t sq_s  \\
 &\ge& \pi_j - {\pi_j \over t} \E_i T_j \\
 &\ge&\pi_j - {\pi_j \over t}h
\end{eqnarray*}
as desired.
\proofend
 
Below we shall need that $N_{ij}\ge (1-(1/n))\pi_j$ for all $i$ and $j$.
We can achieve this by choosing $t=\lceil nh\rceil$. This is good enough
if we are only interested in polynomiality, but the
time bounds we get this way are too pessimistic on
two counts. We could apply the
``multiplicativity property'' in Aldous \cite{Abook}
to show that the factor $n$ could be replaced by $\log n$, and 
results from \cite{ALW} to show that $h$ can 
be replaced by the mixing time $T_{\rm mix}$.

More exactly, let $M=\lceil \log n\rceil$ and
$s=8\lceil T_{\rm mix}\rceil$, and let $Z$ be the sum of $M$
independent random variables $Y_1,\dots,Y_M$, each distributed uniformly in
$\{0,\dots, s-1\}$. Then results from \cite{ALW} imply that
for any starting point,
$$
\Pr(v^Z = j) \ge \left(1- {1\over n}\right)\pi_j.
$$
  
To get around the difficulty that the maximum hitting time $h$ is
not known, we start with $t = 1$ and double $t$ until we are
successful in constructing a tree; for each $t$ we construct $3n$
assignments (the proof below uses $3>e$).  Altogether our randomized
stopping rule $\Theta$ runs as follows:
 
\begin{description}
  \item For $t = 1, 2, 4, 8, \ldots$ do
    \begin{description}
      \item For $k = 1,2,3, \ldots, 3n$ do
        \begin{description}
          \item Choose a state $j$ uniformly from $S$
          \item Put $U = \{j\}$
          \item Do until $U=S$
            \begin{description}
              \item Proceed until a state $i \not\in U$ is reached
              \item Choose a random number $m$ uniformly from
                    $1, \ldots, t$
              \item Proceed $m$ steps and designate the current state
                    as $A_j(i)$
              \item Update $U \leftarrow U \cup \{i\}$
              \item End
            \end{description}
          \item If the assignment $A_j$ is a tree,
                proceed to state $j$ and STOP
        \end{description}
      \item Next $k$
    \end{description}
  \item Next $t$
\end{description}
 
\begin{theorem}\label{main}
Stopping Rule $\Theta$ runs in expected number of steps polynomial in
$h$, and stops at state $j$ with probability exactly $\pi_j$.
\end{theorem}
 
\noindent{\bf Remark.} The proof below gives that the expected 
number of steps is $O(n^2h^2)=O(h^4)$.
Using the bounds mentioned after Lemma \ref{mix}
we get the tighter bound $O(hT_{\rm mix}n\log n)=
O(h^2n\log n)= O(h^3\log n)$ by the same argument.

\Proof
For each fixed $t$ and $k$, the expected number of steps taken by
the assignment construction is no more than $3nh(t+1)/2$, hence before
$t$ reaches $nh$ the algorithm expects to take fewer than
$3n^2h^2$ steps.  Afterwards the probability of ``success'' (achieving
a tree and stopping) for given $t$ and $k$ is at least
$$
{1 \over n}\left(1-{1 \over n}\right)^{n-1} > {1 \over en}
$$
on account of Lemmas \ref{indep} and \ref{mix}, since each
factor in the expression for the weight of any assignment
(in particular, any tree) is short by at most a factor of $1 - 1/n$
of the corresponding stationary probability.
 
It follows that for fixed $t \geq nh$ the success probability is at
least
$$
1 - \left( 1 - {1 \over en}\right)^{3n} > 1 - e^{-3/e} > 2/3~.
$$
Setting $t_0$ equal to the first value of $t$ above $nh$, and letting
$m$ be such that the algorithm stops at $t = 2^m t_0$, we have that
the expected total number of steps is less than
$$
3n^2h^2 + \sum_{m=0}^{\infty}(2/3)(1/3)^m 2^m (3nht_0/2) < 6n^2h^2~.
$$
 
It remains only to argue that Pr(the rule stops at state $i) = \pi_i$,
but this follows from previous remarks plus the fact that the
stationary distribution for $N = {1 \over t}\sum_{k=1}^t M^k$
is the same as for $M$.
\proofend
 
\medskip
 
As an example, suppose $M$ has only two states $a$ and $b$, with
transition probabilities $p_{a,b}=p>0$ and $p_{b,a}=q>0$.  We may
achieve the stationary distribution $\pi = (q/(p+q),p/(p+q))$ by the
following procedure: flip a fair coin; if ``heads'' wait for the first
exit from state $a$ and if ``tails'', the first exit from $b$.  If the
exit is to the opposite state, stop right there; else flip again.
After 6 unsuccessful flips, repeat but take 1- or 2-step exits with
equal probability; then 1-, 2-, 3- or 4-step etc.
 
This two-state algorithm can be generalized to an $n$-state stopping rule
by recursion, giving another solution to our problem (with about the same
bound on expected number of steps).
 
\medskip
 
\section{Derandomization}
 
The randomization required for Stopping Rule $\Theta$ is easily
accomplished by coin flips, since we need only uniform choices
between 1 to $n$ and between 1 to $t$, with $n$ and $t$ both known.
But coin flips can be done using the Markov process itself as long
as there is some transition probability $p_{i,j}$ which lies in the
open interval (0,1). (Otherwise there is no hope, as we cannot
reach a random state in a deterministic process without outside
randomization.)  The technique is ``von Neumann's trick'' for
getting a fair decision from a bent coin.
 
To obtain from $\Theta$ a deterministic stopping rule $\Delta$,
we observe the process for a while and make a list $L$ of states
$i$ with corresponding sets $U_i \subset S$ such that
$$
\pi_i \left( \sum_{j \in U_i} p_{i,j} \right) \left( 1
- \sum_{j \in U_i} p_{i,j} \right)
$$
is about as high as possible.
 
Then we proceed with $\Theta$ but
when a coin flip is needed, we wait until some state in $L$ occurs.
Suppose this happens at time $t_1$ with state $i$; we then proceed to
the next occurrence of $i$, say at time $t_2$, and we take one further
step.  We now check whether we were in $U_i$ at exactly one of the
two times $t_1+1$ and $t_2+1$.  If so we have made a successful
coin flip, the result being ``heads'' if our state at time $t_1+1$ is
in $U_1$ and ``tails'' otherwise.
 
If we hit $U_i$ both times or neither time we try again, waiting for
another state in $L$ to occur.
 
For ``most'' Markov processes the time to consummate a coin flip will
be negligible but if all transition probabilities are close to 0 or 1,
or if the only exceptional $p_{i,j}$'s correspond to states $i$ with
very low stationary probability, then the derandomization may cost
$\Theta$ its polynomiality in $h$.  The deterministic stopping rule
$\Delta$ will, however, be polynomial in $h$ and $r$ where $1/r$ is the
stationary frequency of the most common transition $i \rightarrow j$
such that $p_{i,j} < p_{i,j'}$ for some $j'$.
 
\medskip

{\large\bf Remark.}

A faster (randomized) algorithm for exact mixing in an unknown chain has
now been devised by J.G.\ Propp and D.B.\ Wilson, using the elegant notion
of ``coupling from the past.''  Their stopping rule runs in expected time
bounded by a constant times the expected cover time (thus best possible),
and will appear in a paper entitled ``How to get an exact sample from a
generic Markov chain.''

\medskip
 
{\large\bf Acknowledgments.}
 
The authors are indebted to David Aldous and Eric Denardo for many useful
comments and corrections.
 
\medskip

\noindent {\small\bf Authors' addresses:}

\noindent {\small Dept.\ of Computer Science, Yale University, New Haven CT
06510 USA, lovasz@cs.yale.edu}

\noindent {\small AT\&T Bell Laboratories 2D-147, 600 Mountain Ave., Murray Hill
NJ 07974 USA, pw@research.att.com}

\begin{thebibliography}{99}
 
\bibitem{A1} D.J.\ Aldous, Applications of random walks on graphs,
{\it preprint} (1989).
 
\bibitem{A2} D.J.\ Aldous, The random walk construction of uniform
spanning trees and uniform labelled trees, {\it SIAM J.\ Disc.\ Math.}
{\bf 3} (1990), 450--465.
 
\bibitem{A93} D.J.\ Aldous, On simulating a Markov chain stationary
distribution when transition probabilities are unknown, prepint (1993).
 
\bibitem{Abook} D.J.\ Aldous, {\it Reversible Markov Chains and Random
Walks on Graphs} (book), to appear.

\bibitem{ALW} D.J.\ Aldous, L.\ Lov\'{a}sz and P.\ Winkler, Fast mixing in a
Markov chain, in preparation (1995).
 
\bibitem{AK} D.\ Applegate and R.\ Kannan, Sampling and integration of
near log-concave functions, {\it Proc.\ 23rd ACM Symp.\ on
Theory of Computing} (1991), 156--163.
 
\bibitem{AGT} S.\ Asmussen, P.W.\ Glynn and H.\ Thorisson, Stationary
detection in the initial transient problem, {\it ACM Transactions
on Modeling and Computer Simulation} {\bf 2} (1992), 130--157.
 
\bibitem{Berge}
C.\ Berge, {\it Graphs and Hypergraphs}, North-Holland, Amsterdam, 1973.

\bibitem{BOL}
B.\ Bollob\'as, {\em Random Graphs}, Academic Press, London, 1985.

\bibitem{B}
A.Z.\ Broder, How hard is it to marry at random? 
(on the approximation of the permanent),
{\it Proc.\ 18th ACM Symp.\ on Theory of Computing} (1986), 50--58.
 
\bibitem{B1}
A.Z.\ Broder, Generating random spanning trees, {\it Proc.\ 30th
IEEE Symp.\ on Found.\ of Computer Science} (1989),
442--447.

\bibitem{CRRST} A.K.\ Chandra, P.\ Raghavan, W.L.\ Ruzzo,
R.\ Smolensky, and P.\ Tiwari, The electrical resistance of a graph
captures its commute and cover times, {\it Proc.\ 21st
ACM Symp.\ on Theory of Computing} (1989), 574--586.
 
\bibitem{CTW}
D.\ Coppersmith, P.\ Tetali, and P.\ Winkler,
Collisions among Random Walks on a Graph, {\it SIAM J.
on Discrete Mathematics} {\bf 6} No.\ 3 (1993), 363--374.
 
\bibitem{DS} P.G.\ Doyle and J.L.\ Snell,
{\it Random Walks and Electric Networks},
Mathematical Assoc.\ of America, Washington, DC, 1984.
 
\bibitem{FW} M.I.\ Friedlin and A.D.\ Wentzell, Random perturbations of
dynamical systems, {\it Russian Math.\ Surveys} (1970) 1--55.
 
\bibitem{DFK}
M.\ Dyer, A.\ Frieze and R.\ Kannan, A random polynomial time
algorithm for estimating volumes of convex bodies,
{\it Proc.\ 21st ACM Symp.\ on Theory of Computing}
(1989), 375--381.
 
\bibitem{JS} M.\ Jerrum and A.\ Sinclair, Conductance and the rapid mixing
property for Markov chains: the approximation of the permanent resolved,
{\it Proc.\ 20th ACM Symp.\ on Theory of Computing}
(1988), 235--243.

\bibitem{KK} A.\ Karzanov and L.\ Khachiyan, On the conductance of order
Markov chains, Technical Report DCS TR 268, Rutgers University,
June 1990.

\bibitem{LS} L.\ Lov\'asz and M.\ Simonovits, Random walks in a convex
body and an improved volume algorithm, {\it Random Structures and
Algorithms} {\bf 4} (1993), 359-412.
 
\bibitem{MW} M.\ Mihail and P.\ Winkler, On the number of Eulerian
orientations of a graph, {\it Algorithmica}, to appear.
 
\bibitem{Sy} D.E.\ Symer, Expanded ergodic Markov chains and cycling
systems, senior thesis, Dartmouth College, Hanover NH (1984).
 
\bibitem{T} P.\ Tetali, Random walks and effective resistance of
networks, {\it J.\ Theor.\ Prob.} {\bf 1} (1991), 101-109.
 
\end{thebibliography}
\end{document}

.
