text:
\newcommand{\orb}{\mathop{\mathrm{Orb}}\nolimits}
\newcommand{\wchain}[1]{\widetilde{P}_{#1}}

\section{Preliminaries}

\subsection{A primer on the Chinese Restaurant Process}
\label{sec:CRPprimer}
The Chinese Restaurant Process,
introduced by Dubins and Pitman, is a particular example of a two parameter family of stochastic processes that constructs sequentially random exchangeable partitions of the positive integers via the cyclic decomposition of a random permutation. Our short description is taken from \cite[Section 3.1]{Pit}.

An initially empty restaurant has an unlimited number of circular tables numbered $1,2,\ldots$, each capable of seating an unlimited number of customers. Customers numbered $1,2,\ldots$ arrive one by one and are seated at the tables according to the following plan. Person $1$ sits at table $1$. For $n \ge 1$ suppose that $n$ customers have already entered the restaurant, and are seated in some arrangement, with at least one customer at each of the tables $j$ for $1\le j \le k$ (say), where $k$ is the number of tables occupied by the first $n$ customers to arrive. Let customer $n + 1$ choose with equal probability to sit at any of the following
$n + 1$ places: to the left of customer $j$ for some $1\le j \le n$, or alone at table $k+1$.

Define $\pi^{(n)}\colon[n]\to[n]$ as the permutation
whose cyclic decomposition is given by the tables; that is, if
after $n$ customers have entered the restaurant, customers $i$ and $j$ are
seated at the same table, with $i$ to the left of
$j$, then $\pi^{(n)}(i)=j$, and if customer $i$ is seated alone at some table
then $\pi^{(n)}(i)=i$. The sequence $(\pi^{(n)})$ is then a tower of random permutations
as defined in Section~\ref{sec:growingrrg}.

\subsection{Combinatorics on words}\label{sec:wordcombinatorics}
  Recall the discussion on p.~\pageref{permmodeldiscussion} on viewing
  the graph formed from independent permutations
  $\pi^{(n)}_1,\ldots,\pi^{(n)}_d$ as a directed,
  edge-labeled
  graph. As we did there, we drop the subscripts
  and let $\pi_l=\pi^{(n)}_l$.
  We previously discussed the word formed as we walked around a cycle
  by writing
  down the label of each edge as it is traversed, putting
  $\pi_i$ or $\pi_i^{-1}$ according to the direction
  we walk over the edge.
  Now, we will treat this more rigorously.

    \begin{figure}

      \begin{center}
        \begin{tikzpicture}[scale=1.5,vert/.style={circle,fill,inner sep=0,
              minimum size=0.15cm,draw},>=stealth]
          \node[vert] (s0) at (270:1) {};
            \node[vert] (s1) at (330:1) {};
            \node[vert] (s2) at (30:1) {};
            \node[vert] (s3) at (90:1) {};
            \node[vert] (s4) at (150:1) {};
            \node[vert] (s5) at (210:1) {};
            \draw[thick,->] (s0) to node[auto,swap] {$\pi_2$} (s1);
            \draw[thick,<-] (s1) to node[auto,swap] {$\pi_1$} (s2);
            \draw[thick,->] (s2) to node[auto,swap] {$\pi_2$} (s3);
            \draw[thick,->] (s3) to node[auto,swap] {$\pi_1$} (s4);
            \draw[thick,->] (s4) to node[auto,swap] {$\pi_2$} (s5);
            \draw[thick,<-] (s5) to node[auto,swap] {$\pi_3$} (s0);
        \end{tikzpicture}
      \end{center}
    \caption{A cycle whose word
    is the equivalence class of
    $\pi_2\pi_1^{-1}\pi_2\pi_1\pi_2\pi_3^{-1}$ in $\Ww_6/D_{12}$.}
    \label{fig:cycleword}
  \end{figure}
    Let $\Ww_k$ denote the set
  of cyclically reduced words of length $k$.
  We would like to associate each $k$-cycle in $G_n$
  with the word in $\Ww_k$ formed
  by the above procedure, but since we can start the walk
  at any point in the cycle and walk in either of two directions, there
  are actually up to $2k$ different words that could be
  formed by it.  Thus we identify
  elements of $\Ww_k$ that differ only by rotation and inversion
  (for example, $\pi_1\pi_2^{-1}\pi_1\pi_2$ and
  $\pi_1^{-1}\pi_2\pi_1^{-1}\pi_2^{-1}$) and denote the resulting
  set by $\Ww_k/D_{2k}$, where $D_{2k}$ is the dihedral group acting
  on the set $\Ww_k$ in the natural way.

  \begin{definition}[Properties of words]
     For any $k$-cycle
     in $G_n$, the element of $\Ww_k/D_{2k}$ given by walking
     around the cycle is called the \emph{word} of the cycle  (see
     Figure~\ref{fig:cycleword}).
  For any word $w$, let $\abs{w}$ denote the length of $w$.
  Let $h(w)$ be the largest number $m$ such that
  $w=u^m$ for some word $u$.  If $h(w)=1$, we call $w$ \emph{primitive}.
  For any $w\in\Ww_k$, the orbit of $w$ under the action

  of $D_{2k}$ contains $2k/h(w)$ elements, a fact which we will frequently use.
  Let $c(w)$ denote the number of pairs of double letters in $w$, i.e.,
  the number of integers $i$ modulo $|w|$ such that $w_i=w_{i+1}$.
  For example, $c(\pi_1\pi_1\pi_2^{-1}\pi_2^{-1}\pi_1)=3$.
  If $\abs{w}=1$, we take $c(w)=0$.
  We will also consider $|\cdot|$, $h(\cdot)$, and $c(\cdot)$ as
  functions on $\Ww_k/D_{2k}$, since they are invariant
  under cyclic rotation and inversion.
  \end{definition}

  To more easily refer to words in $\Ww_k/D_{2k}$, choose some
  canonical representative $w_1\cdots w_k\in\Ww_k$ for
  every $w\in\Ww_k/D_{2k}$.  Based on this, we will often
  think of elements of $\Ww_k/D_{2k}$ as words instead of equivalence
  classes, and we will make statements about the $i$th letter
  of a word in $\Ww_k/D_{2k}$.  For $w=w_1\cdots w_k\in\Ww_k/D_{2k}$,
  let $w^{(i)}$ refer
  to the word in $\Ww_{k+1}/D_{2k+2}$ given by
  $w_1\cdots w_i w_i w_{i+1}\cdots w_k$.  We refer to this
  operation as \emph{doubling} the $i$th letter of $w$.
  A related operation is to
  \emph{halve} a pair of double letters, for example producing
  $\pi_1\pi_2\pi_3\pi_4$ from $\pi_1\pi_2\pi_3\pi_4\pi_1$.
  (Since we apply these operations
  to words identified with their rotations, we do not need
  to be specific about which letter of the pair is deleted.)
  The following technical lemma underpins most
  of our combinatorial calculations.
  \begin{lem}\label{lem:doublehalve}
    Let $u\in\Ww_k/D_{2k}$ and $w\in\Ww_{k+1}/D_{2k+2}$.
    Suppose that $a$ letters in $u$ can be doubled to form $w$,
    and $b$ pairs of double letters in $w$ can be halved to form $u$.
    Then
    \begin{align*}
      \frac{a}{h(u)}=\frac{b}{h(w)}.
    \end{align*}
  \end{lem}
  \begin{rmk}
    At first glance, one might expect that $a=b$.  The example
    $u=\pi_1\pi_2\pi_1\pi_1\pi_2$ and $w=\pi_1\pi_1\pi_2\pi_1\pi_1\pi_2$
    shows that this is wrong, since only one letter in $u$ can
    be doubled to give $w$, but two different pairs in $w$ can
    be halved to give $u$.
  \end{rmk}
  \begin{proof}
    Let $\orb(u)$ and $\orb(w)$ denote the orbits of $u$ and $w$

    under the action of the dihedral group
    in $\Ww_k$ and $\Ww_{k+1}$,
    respectively.
    When we speak of halving
    a pair of letters in a word in $\orb(w)$, always delete the second of
    the two letters (for example, $\pi_1\pi_2\pi_1$ becomes $\pi_1\pi_2$, not
    $\pi_2\pi_1$).  When we double a letter in a word in $\orb(u)$,
    put the new letter after the doubled letter (for example, doubling
    the second letter of $\pi_1\pi_2^{-1}$ gives $\pi_1\pi_2^{-1}\pi_2^{-1}$,
    not $\pi_2^{-1}\pi_1\pi_2^{-1}$.)

    For each of the $2k/h(u)$ words in $\orb(u)$, there are
    $a$ doubling operations yielding a word in $\orb(w)$.
    For each of the $(2k+2)/h(w)$ words in $\orb(w)$, there
    are $b$ halving operations yielding a word in $\orb(u)$.
    For every halving operation on a word in $\orb(w)$,
    there is a corresponding doubling operation on a word in $\orb(u)$
    and vice versa, except for halving operations that
    straddle the ends of the word, as in $\pi_1\pi_2\pi_1$.
    There are $2b/h(w)$ of these, giving us
    \begin{align*}
      \frac{2ka}{h(u)} &= \frac{(2k+2)b}{h(w)}-\frac{2b}{h(w)}\\
        &=\frac{2kb}{h(w)},
    \end{align*}
    and the lemma follows from this.
  \end{proof}

  Let $\Ww'=\bigcup_{k=1}^{\infty}\Ww_k/D_{2k}$, and let
  $\Ww'_K=\bigcup_{k=1}^K\Ww_k/D_{2k}$.
  We will use the previous lemma to prove the following
  technical property of the $c(\cdot)$ statistic.
\begin{lem}\label{lem:wordcounts}
  In the vector space with basis $\{q_w\}_{w\in\Ww_K'}$,
  \begin{align*}
    \sum_{w\in\Ww_{K-1}'}\sum_{i=1}^{|w|}\frac{1}{h(w)}q_{w^{(i)}}
      &= \sum_{w\in\Ww_K'}\frac{c(w)}{h(w)}q_w.
  \end{align*}
\end{lem}
\begin{proof}
  Fix some $w\in\Ww_k/D_{2k}$, and
  let $a(u)$ denote the number of letters of $u$ that can be doubled to give
  $w$, for any $u\in\Ww_{k-1}/D_{2k-2}$.  We need to prove that
  \begin{align*}
    \sum_{u\in\Ww_{k-1}/D_{2k-2}}\frac{a(u)}{h(u)}=\frac{c(w)}{h(w)}.
  \end{align*}
  Let $b(u)$ be the number of pairs in $w$ that can be halved to give $u$.
  By Lemma~\ref{lem:doublehalve},
  \begin{align*}
    \sum_{u\in\Ww_{k-1}/D_{2k-2}}\frac{a(u)}{h(u)} &= \sum_{u\in\Ww_{k-1}/
    D_{2k-2}}
    \frac{b(u)}{h(w)},
  \end{align*}
  and $\sum_{u\in\Ww_{k-1}/D_{2k-2}}b(u)=c(w)$.
\end{proof}

 \section{The process limit of the cycle structure}\label{sec:lim}
As the graph $G(t)$ grows, new cycles form, which we can classify into two
types.  Suppose a new vertex numbered $n$ is inserted at time
$t$, and this insertion creates a new cycle.
If the edges entering and leaving vertex
$n$ in the new cycle have the same edge label, then the new cycle has ``grown'' from a cycle with one fewer vertex, as in
Figure~\ref{fig:growth}.  If the edges entering and leaving $n$ in the cycle
have different labels, then the cycle has formed ``spontaneously'' as in
Figure~\ref{fig:spontaneous}, rather
than growing from a smaller cycle.
This classification will prove essential in understanding
the evolution of cycles in $G(t)$.
\begin{figure}

  \begin{center}
    \begin{tikzpicture}[scale=1.2,>=stealth,auto=right]
      \begin{scope}
      \fill[black!10,rounded corners] (-1.5,-2.9) rectangle (1.5,1.5);
      \path  (270:1) node[vert,label=270:$1$] (s0){}
             (342:1) node[vert,label=right:$2$] (s1){}
             (54:1) node[vert,label=above right:$3$] (s2){}
             (126:1) node[vert,label=above left:$4$] (s3){}
             (198:1) node[vert,label=left:$5$] (s4){};
      \draw[thick,->] (s0) -- node{$\pi_1$} (s1);
      \draw[thick,->] (s1) -- node{$\pi_1$} (s2);
      \draw[thick,<-] (s2) -- node{$\pi_2$} (s3);
      \draw[thick,<-] (s3) -- node{$\pi_1$} (s4);
      \draw[thick,->] (s4) -- node{$\pi_2$} (s0);
      \path (0,-2) node[text width=4cm] {
        \begin{align*}
          \pi_1&=(1\ 2\ 3)(4\ 5)\\[-6pt]
          \pi_2&=(1\ 5)(4\ 3)(2)
        \end{align*}
      };
      \end{scope}
      \draw[->, decorate, decoration={snake,amplitude=.4mm,
          segment length=2mm,post length=1.5mm}]
          (1.65, -.55)--+(1.85,0);

      \begin{scope}[xshift=5.2cm]
      \fill[black!10,rounded corners] (-1.5,-2.9) rectangle (1.9,1.5);
      \path  (270:1) node[vert,label=270:$1$] (s0){}
             (342:1) node[vert,label=342:$2$] (s1){}
             (54:1) node[vert,label=54:$3$] (s2){}
             (126:1) node[vert,label=126:$4$] (s3){}
             (198:1) node[vert,label=198:$5$] (s4){}
             (18:1.5) node[vert,label=18:$6$] (new) {};
      \draw[thick,->] (s0) -- node{$\pi_1$} (s1);
      \draw[thick,->] (s1) -- node{$\pi_1$} (new);
      \draw[thick,->] (new) -- node{$\pi_1$} (s2);
      \draw[thick,<-] (s2) -- node{$\pi_2$} (s3);
      \draw[thick,<-] (s3) -- node{$\pi_1$} (s4);
      \draw[thick,->] (s4) -- node{$\pi_2$} (s0);
      \path (0.25,-2) node[text width=4cm] {
        \begin{align*}
          \pi_1&=(1\ 2\ \mathbf{6}\ 3)(4\ 5)\\[-6pt]
          \pi_2&=(1\ 5)(4\ 3)(2\ \mathbf{6})
        \end{align*}
      };
      \end{scope}
    \end{tikzpicture}
  \end{center}
  \caption{The vertex $6$ is inserted between
  vertices $2$ and $3$ in $\pi_1$, causing the above
  cycle to grow.}\label{fig:growth}
\end{figure}
\begin{figure}

  \begin{center}
    \begin{tikzpicture}[scale=1.15,>=stealth,auto=right]
      \begin{scope}
        \fill[black!10,rounded corners] (-0.35,-1.9) rectangle (4.35,1.6);
        \path (0,0) node[vert,label=below:$1$] (s1) {}
              (1,0) node[vert,label=below:$2$] (s2) {}
              (2,0) node[vert,label=below:$3$] (s3) {}
              (3,0) node[vert,label=below:$4$] (s4) {}
              (4,0) node[vert,label=below:$5$] (s5) {};
        \draw[<-,thick] (s1)--node {$\pi_2$} (s2);
        \draw[->,thick] (s2)--node {$\pi_1$} (s3);
        \draw[->,thick] (s3)--node {$\pi_2$} (s4);
        \draw[<-,thick] (s4)--node {$\pi_1$} (s5);
        \path (2,-1) node[text width=4cm] {
          \begin{align*}
            \pi_1&=(2\ 3\ 1)(4\ 5)\\[-6pt]
            \pi_2&=(2\ 1\ 3\ 4\ 5)
          \end{align*}
        };
      \end{scope}
      \draw[->, decorate, decoration={snake,amplitude=.4mm,
          segment length=2mm,post length=1.5mm}]
          (4.4, -.1)--+(1.2,0);
      \begin{scope}[xshift=6cm]
        \fill[black!10,rounded corners] (-0.35,-1.9) rectangle (4.35,1.6);
        \path (0,0) node[vert,label=below:$1$] (s1) {}
              (1,0) node[vert,label=below:$2$] (s2) {}
              (2,0) node[vert,label=below:$3$] (s3) {}
              (3,0) node[vert,label=below:$4$] (s4) {}
              (4,0) node[vert,label=below:$5$] (s5) {}
              (2,1) node[vert,label=above:$6$] (s6) {};
        \draw[<-,thick] (s1)--node {$\pi_2$} (s2);
        \draw[->,thick] (s2)--node {$\pi_3$} (s3);
        \draw[->,thick] (s3)--node {$\pi_2$} (s4);
        \draw[<-,thick] (s4)--node {$\pi_1$} (s5);
        \draw[->,thick,bend left] (s1) to node[swap] {$\pi_1$} (s6);
        \draw[->,thick,bend left] (s6) to node[swap] {$\pi_2$} (s5);
        \path (2,-1) node[text width=4cm] {
          \begin{align*}
            \pi_1&=(2\ 3\ 1\ \mathbf{6})(4\ 5)\\[-6pt]
            \pi_2&=(2\ 1\ 3\ 4\ \mathbf{6}\ 5)
          \end{align*}
        };
      \end{scope}
    \end{tikzpicture}
  \end{center}
  \caption{A cycle forms ``spontaneously'' when the vertex $6$
  is inserted into the graph.}\label{fig:spontaneous}
\end{figure}

Once a cycle comes into existence in $G(t)$, it remains until a new vertex
is inserted into one of its edges.  Typically, this results in the cycle
growing to a larger cycle, as in Figure~\ref{fig:growth}.
If a new vertex is simultaneously inserted into multiple
edges of the same cycle, the cycle is instead split into
smaller cycles
as in Figure~\ref{fig:split}.  These new cycles
are spontaneously formed, according to the classification of new cycles
given in the previous paragraph.
Tracking the evolution of these smaller cycles in turn,
we see that as the graph evolves,
a cycle grows into a cluster of overlapping cycles.
However, it will follow from
Proposition~\ref{prop:nooverlaps} that for short cycles, this behavior is not
typical.  Thus in our limiting object,
 cycles will grow only into larger cycles.\label{par:split}
\begin{figure}

  \begin{center}
    \begin{tikzpicture}[scale=1.2,>=stealth,auto=right]
      \begin{scope}
      \fill[black!10,rounded corners] (-1.5,-2.9) rectangle (1.5,1.6);
      \path  (270:1) node[vert,label=270:$1$] (s0){}
             (342:1) node[vert,label=right:$2$] (s1){}
             (54:1) node[vert,label=above right:$3$] (s2){}
             (126:1) node[vert,label=above left:$4$] (s3){}
             (198:1) node[vert,label=left:$5$] (s4){};
      \draw[thick,->] (s0) -- node{$\pi_1$} (s1);
      \draw[thick,->] (s1) -- node{$\pi_1$} (s2);
      \draw[thick,<-] (s2) -- node{$\pi_2$} (s3);
      \draw[thick,<-] (s3) -- node{$\pi_1$} (s4);
      \draw[thick,->] (s4) -- node{$\pi_2$} (s0);
      \path (0,-2) node[text width=4cm] {
        \begin{align*}
          \pi_1&=(1\ 2\ 3)(4\ 5)\\[-6pt]
          \pi_2&=(1\ 5)(4\ 3)(2)
        \end{align*}
      };
      \end{scope}
      \draw[->, decorate, decoration={snake,amplitude=.4mm,
          segment length=2mm,post length=1.5mm}]
          (1.65, -.55)--+(1.85,0);

      \begin{scope}[xshift=5.2cm]
      \fill[black!10,rounded corners] (-1.5,-2.9) rectangle (1.9,1.6);
      \path  (270:1) node[vert,label=270:$1$] (s0){}
             (342:1) node[vert,label=342:$2$] (s1){}
             (54:1) node[vert,label=54:$3$] (s2){}
             (126:1) node[vert,label=126:$4$] (s3){}
             (198:1) node[vert,label=198:$5$] (s4){}
             (0:0) node[vert,label=135:$6$] (new) {};
      \draw[thick,->] (s0) -- node{$\pi_1$} (s1);
      \draw[thick,->] (s1) -- node{$\pi_1$} (new);
      \draw[thick,->] (new) -- node[swap,yshift=-0.1cm,xshift=0.1cm]{$\pi_1$} (s2);
      \draw[thick,<-] (s2) -- node{$\pi_2$} (s3);
      \draw[thick,<-] (s3) -- node{$\pi_1$} (s4);
      \draw[thick,->] (s4) -- node[xshift=-0.2cm]{$\pi_2$} (new);
      \draw[thick,->] (new) -- node[swap]{$\pi_2$} (s0);
      \path (0,-2) node[text width=4cm] {
        \begin{align*}
          \pi_1&=(1\ 2\ \mathbf{6}\ 3)(4\ 5)\\[-6pt]
          \pi_2&=(1\ 5\ \mathbf{6})(4\ 3)(2)
        \end{align*}
      };
      \end{scope}
    \end{tikzpicture}
  \end{center}
  \caption{The vertex $6$ is inserted into the cycle
  in two different places in the same step, causing
  the cycle to split in two.  Note that
  each new cycle would be classified as spontaneously
  formed.}\label{fig:split}
\end{figure}

\subsection{Heuristics for the limiting process}\label{sec:heuristics}
We give some estimates that will motivate
the definition of the limiting process in Section~\ref{sec:limdef}.
This section is entirely motivational, and
we will not attempt to make anything rigorous.

Suppose that vertex $n$ is inserted into $G(t)$ at some
time $t$.
First, we consider the rate that cycles form spontaneously
with some word $w\in\Ww_k/D_{2k}$.  There are
$2k/h(w)$ words in the orbit of $w$ under
the action of $D_{2k}$, and out of these, $2(k-c(w))/h(w)$
have nonequal first and last letters.
For each such word $u=u_1\cdots u_k$, we can
give a walk on the graph by starting at vertex $n$
and following the edges indicated by $u$, going from
$n$ to $u_1(n)$ to $u_2(u_1(n))$ and so on.
If this walk happens to be a cycle, the condition
$u_1\neq u_k$ implies that
it would be spontaneously formed.

In a short interval $\Delta t$ when $G(t)$ has $n-1$ vertices,
the probability that vertex $n$ is inserted is about $n\,\Delta t$.

For any word $u$,
the walk from vertex $n$ generated by $u$
is a cycle with probability approximately $1/n$, since
after applying the random permutations $u_1,\ldots,u_k$ in turn,
we will be left at an approximately uniform random vertex.
Any new spontaneous cycle formed with word $w$
will be counted by one of these walks,
with $u$ in the orbit of $w$, and it will be counted again
by the walk generated by
$u_k^{-1}\cdots u_1^{-1}$.

The expected number of spontaneous
cycles formed in a short interval $\Delta t$ is then approximately
\begin{align*}
  \frac{1}{h(w)}(k-c(w))\frac{n\,\Delta t}{n}&=
  \frac{1}{h(w)}(k-c(w))\,\Delta t.
\end{align*}
Thus we will model the spontaneous formation of cycles with word $w$
by a Poisson process with rate $(k-c(w))/h(w)$.

Next, we consider how often a cycle with word $w\in\Ww_k$ grows into a larger
cycle.
Suppose that $G(t)$ has $n-1$ vertices, and that it contains a cycle of
the form
\begin{center}

  \begin{tikzpicture}[xscale=1.4,vert/.style={circle,fill,inner sep=0,
        minimum size=0.15cm,draw},>=stealth]
    \foreach \i in {0,1,2}
      \node[vert, label=below:{$s_{\i}$}] (s\i) at (\i,0) {};
    \node (s3) at (3,0) {$\ldots$};
    \node[vert, label=below:{$s_{k-1}$}] (s4) at (4,0) {};
    \draw[thick,->] (s0) to node[auto] {$w_1$} (s1);
    \draw[thick,->] (s1) to node[auto] {$w_2$} (s2);
    \draw[thick,->] (s2) to node[auto] {$w_3$} (s3);
    \draw[thick,->] (s3) to node[auto] {$w_{k-1}$} (s4);
    \draw[thick,->,] (s4) to[out=90,in=90] node[auto,swap] {$w_k$} (s0);
  \end{tikzpicture}
\end{center}
When vertex $n$ is inserted into the graph,
the probability that it is inserted after $s_{i-1}$ in permutation
$w_i$ is $1/n$.  Thus, after a spontaneous cycle with word $w$
has formed, we can model the evolution of its word as a
continuous-time Markov chain
where each letter is doubled with rate one.

\subsection{Formal definition of the limiting process}\label{sec:limdef}
\newcommand{\N}[2]{N_{#1}
                          \ifthenelse{\equal{#2}{}}{}{({#2})}}
\newcommand{\bN}[2]{\overleftarrow{N}_{#1}
                          \ifthenelse{\equal{#2}{}}{}{({#2})}}
\newcommand{\bM}[2]{\overleftarrow{M}_{#1}
                          \ifthenelse{\equal{#2}{}}{}{({#2})}}

Consider the measure $\mu$
on $\Ww'$ given by
\[
\mu(w)= \frac{|w|-c(w)}{h(w)}.
\]
Consider a Poisson point process $\chi$ on
$\Ww' \times[0,\infty)$ with an intensity measure given by the product measure
$\mu \otimes \leb$, where $\leb$ refers to the Lebesgue measure. Each atom
$(w,t)$ of $\chi$ represents a new spontaneous cycle with word $w$ formed at time $t$.

Now, we define
a continuous-time Markov chain on the countable space
$\Ww'$ governed by the following
rates: From state $w\in\Ww_k/D_{2k}$, jump with rate one to each
of the $k$ words
in $\Ww_{k+1}/D_{2k+2}$ obtained by doubling a letter of $w$.
If a word can be formed in more than one way by doubling a letter in $w$,
then it receives a correspondingly higher rate.  For example, from
$w=\pi_1\pi_1\pi_2$, the chain jumps to $\pi_1\pi_1\pi_1\pi_2$ with rate
two and to $\pi_1\pi_1\pi_2\pi_2$ with rate one.  Let $\wchain{w}$
denote the law of this process started from $w\in\Ww'$.

Suppose we are given a realization of $\chi$. For any
atom $(w,s)$ of the countably many atoms of $\chi$,
we start an independent process $(X_{w,s}(t),\, t\ge 0)$ with law
$\wchain{w}$. Define the stochastic process
\[
\N{w}{t}\defeq  \sum_{\substack{(u,s)\in \chi\\s\leq t}} 1
  \left\{\text{$X_{u,s}(t-s)=w$}  \right\}.
\]
Interpreting these processes as in the previous section,
$\N{w}{t}$ counts the number of cycles
formed spontaneously at time $s$ that have grown to have word $w$ at time $t$.

The fact that the process exists is obvious since one can define the countably
many independent Markov chains on a suitable product space.
The following lemma establishes some of its key properties.

\begin{lem}\label{lem:chainprops}
Recall that $\Ww_L'=\bigcup_{k=1}^L\Ww_k/D_{2k}$.
We have the following conclusions:
\begin{enumerate}[(i)]
\item For any $L \in \NN$, the stochastic process $\{ (\N{w}{t},\,
  w\in \Ww_L'), \; t\ge 0 \}$ is a time-homogeneous Markov
  process with respect to its natural filtration, with RCLL paths.

  \label{item:markov}

\item Recall that for
  $w\in\Ww_k/D_{2k}$, the element $w^{(i)}\in\Ww_{k+1}/D_{2k+2}$ is
  the word formed by doubling the $i$th letter of $w$.
  The generator for the Markov process
  $\{ (\N{w}{t},\,
  w\in \Ww_L'), \; t\ge 0 \}$ acts on $f$ at
  $x=(x_{w},\,w\in \Ww_L')$ by
\[\begin{split}
\mathcal{L} f(x) =  &\sum_{w\in\Ww_L'} \sum_{i=1}^{|w|}x_{w}
\left[ f(x-e_{w}+e_{w^{(i)}}) - f(x) \right]\\ &+ \sum_{w\in\Ww'_L}
 \frac{|w|-c(w)}{h(w)} \left[ f(x+e_{w}) - f(x) \right],
\end{split}\]
where $e_{w}$ is the canonical basis vector equal to one at entry $w$ and
equal to zero everywhere else.  For a word $u$ of length greater than
$L$, take $e_u=0$.\label{item:generator}
\item The product measure of $\Poi(1/h(w))$ over all $w\in \Ww_L'$ is
  the unique invariant measure for this Markov process.\label{item:invariant}
\end{enumerate}
\end{lem}

\begin{proof} Conclusion (i) follows from construction, as does conclusion (ii). To prove conclusion (iii), we start by the fundamental identity of the Poisson distribution: if $X\eqd \Poi(\lambda)$, then for any function $f$, we have
\begin{equation}\label{eq:poiiden}
\E X g(X)= \lambda \E g(X+1).
\end{equation}

We need to show that if the coordinates of $X=(X_{w},\,w\in \Ww'_L)$
are independent Poisson random variables with $\E X_{w}=1/h(w)$, then
\begin{align}
  \label{eq:poiinvpf}
\E \mathcal{L}f(X)=0.
\end{align}

Since the process is an irreducible Markov chain on countable state space, the existence of one invariant distribution shows that the chain is positive recurrent and that the invariant distribution is unique.

To argue \eqref{eq:poiinvpf} we will repeatedly apply identity \eqref{eq:poiiden} to functions $g$
constructed from $f$ by keeping all but one coordinate fixed.
Thus, for any $w\in\Ww_L'$ and $1\leq i\leq|w|$,
we condition on all $X_u$ with $u\neq w$ and hold
those coordinates of $f$ fixed to obtain,
\begin{align*}
\E X_w f\left( X - e_{w} + e_{w^{(i)}} \right)&= \frac{1}{h(w)} \E
f\left( X + e_{w^{(i)}} \right)
\end{align*}
taking $e_{w^{(i)}}=0$ when $|w|=L$.
In the same way,
\begin{align*}
\E X_{w} f\left( X \right)= \frac{1}{h(w)} \E f\left( X + e_{w} \right).
\end{align*}
By these two equalities,
\begin{align*}
  \E\sum_{w\in\Ww_L'}\sum_{i=1}^{|w|}&X_w[f(X-e_w+e_{w^{(i)}})-f(X)]\\
    &= \sum_{w\in\Ww_L'}\sum_{i=1}^{|w|}\frac{1}{h(w)}\E\big[ f(X+e_{w^{(i)}})
    -f(X+e_w)\big]\\
    &=\sum_{w\in\Ww_{L-1}'}\sum_{i=1}^{|w|}\frac{1}{h(w)}\E f(X+e_{w^{(i)}})
      + \sum_{w\in\Ww_L/D_{2L}}\frac{|w|}{h(w)}\E f(X)\\
    &\phantom{=}\quad  - \sum_{w\in\Ww'_L}\frac{|w|}{h(w)}\E f(X+e_w).
\end{align*}
Specializing Lemma~\ref{lem:wordcounts} to $q_w=\E f(X+e_w)$,
the first sum is
\begin{align*}
  \sum_{w\in\Ww_{L-1}'}\sum_{i=1}^{|w|}\frac{1}{h(w)}\E f(X+e_{w^{(i)}})
  &=\sum_{w\in\Ww'_L}\frac{c(w)}{h(w)}\E f(X+e_w),
\end{align*}
which gives us
\begin{align*}
  \E\sum_{w\in\Ww_L'}\sum_{i=1}^{|w|}&X_w[f(X-e_w+e_{w^{(i)}})-f(X)]\\
  &= \sum_{w\in\Ww'_L}\frac{c(w)-|w|}{h(w)}\E f(X+e_w)
    +\sum_{w\in\Ww_L/D_{2L}}\frac{|w|}{h(w)}\E f(X).
\end{align*}
All that remains in proving \eqref{eq:poiinvpf} is to show that
\begin{align*}
  \sum_{w\in\Ww_L'}\frac{|w|-c(w)}{h(w)}=\sum_{w\in\Ww_L/D_{2L}}
    \frac{|w|}{h(w)}.
\end{align*}
Specializing Lemma~\ref{lem:wordcounts} to $q_w=1$ shows that
$\sum_{w\in\Ww_L'}c(w)/h(w)=\sum_{w\in\Ww_{L-1}'}|w|/{h(w)}$.
Thus
\begin{align*}
  \sum_{w\in\Ww_L'}\frac{|w|-c(w)}{h(w)}&=
  \sum_{w\in\Ww_L'}\frac{|w|}{h(w)}-
  \sum_{w\in\Ww_{L-1}'}\frac{|w|}{h(w)}\\
  &=  \sum_{w\in\Ww_L/D_{2L}}\frac{|w|}{h(w)},
\end{align*}
establishing \eqref{eq:poiinvpf} and completing the proof.
\end{proof}
From now on, we will consider the process $(\N{w}{t},\,k\in\NN,\,t\geq 0)$
to be running under stationarity, i.e., with marginal distributions
given by conclusion~(\ref{item:invariant}) of the last lemma.
This process is easily constructed as described above, but with
additional point masses
of weight $1/h(w)$ for each $w\in\Ww'$ at $(w,0)$ added to the intensity
measure of $\chi$, thus giving us the correct distribution at time zero.

\subsection{Time-reversed processes}\label{sec:reversals}
Fix some time $T>0$.  We define the time-reversal
$\bN{w}{t}\defeq \N{w}{T-t}$ for
$0\leq t\leq T$.
\begin{lem}
  For any fixed $L\in\NN$, the process
  $\{(\bN{w}{t},\,w\in \Ww'_L),\,0\leq t\leq T\}$
  is a time-homogenous Markov process with respect to the natural
  filtration.

  A trivial modification at jump times renders RCLL paths.
  The transition rates of this chain are given
  as follows.
  Let $u\in\Ww_{k-1}/D_{2k-1}$ and $w\in\Ww_k/D_{2k}$, and
  suppose that $u$ can be obtained from $w$
  by halving $b$ different pairs.  Let $x = (x_w,\,w\in\Ww'_L)$.
  \begin{enumerate}[(i)]
    \item The chain jumps from $x$ to
        $x+e_{u}-e_{w}$ with rate $bx_{w}$.\label{item:shrink}
    \item The chain jumps from $x$ to
        $x-e_{w}$ with rate $(k-c(w))x_{w}$.\label{item:die}
    \item If $w\in\Ww_L/D_{2L}$, then the
      chain jumps from $x$ to $x+e_{w}$
      with rate $L/h(w)$.\label{item:dropin}
  \end{enumerate}
\end{lem}
\begin{proof}
  Any Markov process run backwards under stationarity is Markov.
  If the chain has transition rate $r(x,y)$ from states $x$ to $y$,
  then the transition rate of the backwards chain from $x$ to $y$
  is $r(y,x)\nu(y)/\nu(x)$, where
  $\nu$ is the stationary distribution.
  We will let $\nu$ be the stationary distribution
  from Lemma~\ref{lem:chainprops}\ref{item:invariant} and
  calculate the transition rates of the backwards chain,
  using the rates given in
  Lemma~\ref{lem:chainprops}\ref{item:generator}.

  Let $a$ denote the number of letters in $u$ that give $w$ when
  doubled.  The transition rate of the original chain
  from $x+e_u-e_w$ to $x$ is $a(x_u+1)$, so
  the transition rate of the backwards chain
  from $x$ to $x+e_{u}-e_{w}$ is
  \begin{align*}
    a(x_u+1)\frac{\nu(x+e_{k-1,c-1}-e_{k,c})}{\nu(x)}
      &=\frac{ah(w)x_w}{h(u)},
  \end{align*}
  and this is equal to $bx_w$ by Lemma~\ref{lem:doublehalve}.
  A similar calculation shows that the transition rate from $x$ to $x-e_{w}$ is
  \begin{align*}
    \frac{(k-c(w))\nu(x-e_{w})}{h(w)\nu(x)} &=(k-c(w))x_w,
  \end{align*}
  proving (\ref{item:die}).  The transition rate from $x$ to $x+e_{w}$
  for $w\in\Ww_L/D_{2L}$
  is
  \begin{align*}
    \frac{\nu(x+e_w)}{\nu(x)}(x_{w}+1)L = \frac{L}{h(w)},
  \end{align*}
  which completes the proof.
\end{proof}
By definition,
\begin{align*}
  \bN{w}{t} =
  \sum_{\substack{(u,s)\in \chi\\s\leq T-t}} 1\left\{\text{$X_{u,s}(T-t-s)=w$}
    \right\}.
\end{align*}
We will modify this slightly to define the process
\begin{align*}
  \bM{w}{t} \defeq
  \sum_{\substack{(u,s)\in \chi\\s\leq T-t}} 1\left\{\text{$X_{u,s}(T-t-s)=w$
      and $|X_{u,s}(T-s)|\leq L$}
    \right\}.
\end{align*}
The idea is that $\bM{w}{t}$ is the same as $\bN{w}{t}$, except
that it does not count cycles at time~$t$ that had more than $L$ vertices
at time zero.
The process $(\bM{w}{t},\,w\in\Ww_L')$
is a Markov chain with the same transition rates as
$(\bN{w}{t},\,w\in\Ww_L')$,
except that it does not jump from $x$ to $x+e_{w}$ for $w\in\Ww_L/D_{2L}$.
These two chains also have the same initial distribution, but
$(\bM{w}{t},\,w\in\Ww_L')$ is not stationary (in fact, it is eventually
absorbed at zero).

\section{Process convergence of the cycle structure}\label{sec:processconvergence}

Recall that $\Cy[s]{k}(t)$ is the number of cycles of length $k$ in the graph
$G(s+t)$, defined on p.~\pageref{page:chaindef}.
For $w\in\Ww'$, let $\Cy[s]{w}(t)$ be the number of cycles in $G(s+t)$
with word $w$. We will prove that
$\big(\Cy[s]{w}(\cdot),\,w\in\Ww'\big)$ converges to a distributional limit,
from which the convergence of $\big(\Cy[s]{k}(\cdot),\,k\in\NN\big)$ will follow.
The proof depends on knowing the limiting \emph{marginal} distribution of
$\Cy[s]{w}(t)$. The following corollary of \thref{thm:processapprox}
gives the facts we need:
\begin{cor}\label{cor:marginals}
  Let $\{Z_w,\,w\in\Ww'_K\}$
  be a family of independent Poisson random variables
  with $\E Z_w=1/h(w)$.  For any fixed integer $K$ and $d\geq 1$,
  \begin{enumerate}[(i)]
    \item as $t\to\infty$,\label{item:margC}
      \begin{align*}
        (C_w(t),\,w\in\Ww'_K)
        \toL (Z_w,\,w\in\Ww'_K);
      \end{align*}
    \item as $t\to\infty$, the probability that there exist
      two
      cycles of length $K$ or less sharing a vertex in $G(t)$
      approaches zero.\label{item:margoverlap}
  \end{enumerate}
\end{cor}
\begin{proof}
  When $d=1$, there is only one word of each length in $\Ww'_K$,
  and statement~(\ref{item:margC}) reduces to the well-known fact that the cycle
  counts of a random permutation converge to independent Poisson random
  variables (see \cite{AT} for much more on this subject).
  In this case, $G(t)$ is made up of disjoint cycles for all times $t$,
  so that statement~(\ref{item:margoverlap}) is trivially satisfied.

  When $d\geq 2$, let $\Cy[n]{w}$ be the number of cycles with word $w$ in
  $G_n$. Observe that $\Cy[n]{w} = \sum_\alpha I_\alpha$, with $I_\alpha$ as in
  the statement of \thref{thm:processapprox} and the sum over all cycles in $\Ii$
  with word~$w$. The random variable $Z_w$ is the analogous sum over $Z_\alpha$,
  since the number of cycles in $\Ii$ with word $w$ is $[n]_k/h(w)$.
  By \thref{thm:processapprox},
  \begin{align}
    (\Cy[n]{w},\,w\in\Ww'_K)
      \toL (Z_w,\,w\in\Ww'_K).\label{eq:discretetimeconvergence}
  \end{align}

  Now, we just extend this to continuous time.
  The random vector
  $(C_w(t),\,w\in\Ww'_K)$ is a mixture of the random
  vectors $(\Cy[n]{w},\,w\in\Ww'_K)$ over different values of $n$.
  That is,
  \begin{align*}
    \P\left[\bigl(C_w(t),\,w\in\Ww'_K\bigr)\in A\right]
      &=\sum_{n=1}^{\infty}\P[M_t=n]\P\left[
      \bigl(\Cy[n]{w},\,w\in\Ww'_K\bigr)\in A\right]
  \end{align*}
  for any set $A$, recalling that $G(t)=G_{M_t}$.
  Equation~\eqref{eq:discretetimeconvergence} together
  with the fact that $\P[M_t>N]\to 1$ as $t\to\infty$ for
  any $N$ imply that $(C_w(t),\,w\in\Ww'_K)$ converges
  in law to $(Z_w,\,w\in\Ww'_K)$, establishing
  statement~(\ref{item:margC}).

  The discrete time version of statement~(\ref{item:margoverlap}) is
  given by \cite[Corollary~16]{DJPP}.
  Statement~(\ref{item:margoverlap})
  follows from it in the same way.
\end{proof}

Now, we turn to the convergence of the processes.
We will often need to transfer the convergence of a process to its limit
to the convergence of a functional of the process.
The following criterion, which we present without proof,
lets us apply the continuous mapping theorem to do so.
\begin{lem}[{\cite[Section~3.11, Exercise~14]{EK}}]\thlabel{lem:EKcont}
  Let $E$ and $F$ be metric spaces, and let $f\colon E\to F$
  be continuous. Then the mapping $x\mapsto f\circ x$ from
  $D_E[0,\infty)\to D_F[0,\infty)$ is continuous.
\end{lem}

\begin{thm}\thlabel{thm:convergence}
  The process $\big(\Cy[s]{w}(\cdot),\,w\in\Ww'\big)$ converges in law
  as $s\to\infty$ to
  $(\N{w}{\cdot},\,w\in\Ww')$ in
  the space $D_{\RR^{\infty}}[0,\infty)$.
\end{thm}
\newcommand{\bG}[2]{\overleftarrow{G}_{#1}(#2)}
\newcommand{\bCy}[2][\infty]{\overleftarrow{C}^{(#1)}_{#2}}
\newcommand{\bX}[4][s]{\overleftarrow{M}_{#2\ifthenelse{\equal{#3}{}}{}{,#3}}^{(#1)}(#4)}
  \newcommand{\bGraph}[2]
  {\ifthenelse{\equal{#1}{}}{\overleftarrow{\Gamma}(#2)}
  {\overleftarrow{\Gamma}_{#1}(#2)}}
\begin{proof}
  The main difficulty in
  turning the intuitive ideas of Section~\ref{sec:heuristics}
  into an actual proof is that $\big(\Cy[s]{w}(t),\,w\in\Ww'\big)$
  is not Markov.
  We now sketch how we evade this problem.
  We will run our chain backwards, defining  $\bG{s}{t}=G(s+T-t)$
  for some fixed $T>0$.  Then,
  we ignore all of $\bG{s}{0}$ except for the subgraph consisting of cycles
  of size $L$ and smaller, which we will call $\bGraph{s}{0}$.

  The graph $\bGraph{s}{t}$ is the evolution of this subgraph as time
  runs backward, ignoring the rest of  $\bG{s}{t}$.
  Then, we consider the number of cycles with word $w$ in $\bGraph{s}{t}$,
  which we call $\phi_w(\bGraph{s}{t})$.

Choose $K \ll L$. Then $\phi_w(\bGraph{s}{t})$ is likely to be the same as $\Cy[s]{w}(T-t)$
  for any word $w$ with $|w|\leq K$.
  The remarkable fact that makes $\phi_w(\bGraph{s}{t})$
  possible to analyze is that
  if $\bGraph{s}{0}$
  consists of disjoint cycles, then $\big(\phi_w(\bGraph{s}{t}),\,
  w\in\Ww'_L\big)$
  is a Markov chain governed by the same transition rates
  as $\big(\bM{w}{t},\,w\in\Ww'_L\big)$.

  Another important idea of the proof is to ignore the vertex labels
  in $\bG{s}{t}$, so that we do not know in what order the vertices
  will be removed. Thus we can view $\bG{s}{t}$ as a Markov
  chain with the following description:
  Assign each
  vertex an independent $\Exp(1)$ clock.  When the clock of vertex $v$
  goes off, remove it from the graph, and patch together the $\pi_i$-labeled
  edges entering and leaving $v$ for each $1\leq i\leq d$.
  \step{1}
  {Definitions of $\bGraph{s}{t}$ and $\phi_w$ and analysis of
  $\big(\phi_{w}(\bGraph{s}{t}),\,w\in\Ww_L'\big)$.}

  Fix $T>0$ and define $\bG{s}{t}=G(s+T-t)$.  As mentioned above,
  we will consider
  $\bG{s}{t}$ only up to relabeling of vertices, which makes it
  a process on the countable state space consisting
  of all edge-labeled graphs on finitely many unlabeled vertices.
  With respect to its natural filtration, it is a Markov chain
  in which each vertex is removed with rate one,
  as described above.

  To formally define
  $\bGraph{s}{t}$, fix integers $L>K$ and
  let $\bGraph{s}{0}$ be the subgraph of $\bG{s}{0}$ made up of all
  cycles  of length $L$ or less.
  We then evolve $\bGraph{s}{t}$ in parallel with $\bG{s}{t}$.
  When a vertex $v$ is deleted from $\bG{s}{t}$, the corresponding
  vertex $v$ in $\bGraph{s}{t}$ is deleted if it is present.  If $v$
  has a $\pi_i$-labeled edge entering and leaving it in
  $\bGraph{s}{t}$, then these two edges
  are patched together. Other edges
  in $\bGraph{s}{t}$ adjacent to $v$ are deleted.
  This makes $\bGraph{s}{t}$ a subgraph of $\bG{s}{t}$,
   as well as a
  continuous-time Markov chain on the countable
  state space consisting
  of all edge-labeled graphs on finitely many unlabeled vertices.
  The transition probabilities of $\bGraph{s}{t}$ do not depend on $s$.

  From Corollary~\ref{cor:marginals}, we can find the limiting
  distribution of $\bGraph{s}{0}$.
  Suppose that $\gamma$ is a graph in the process's state space
  that is not a disjoint union
  of cycles.  By Corollary~\ref{cor:marginals}\ref{item:margoverlap},
  \begin{align*}
    \lim_{s\to\infty}\P[\bGraph{s}{0}=\gamma]=0.
  \end{align*}
  Suppose instead that
     $\gamma$ is made up of disjoint cycles,
  with $z_w$ cycles of word~$w$ for each $w\in\Ww'_L$.
  By Corollary~\ref{cor:marginals}\ref{item:margC},

  \begin{align}
    \lim_{s\to\infty}\P[\bGraph{s}{0}=\gamma]=\prod_{w\in\Ww_L'}
    \P[Z_w=z_w],\label{eq:Gammadist}
  \end{align}
  where $(Z_w,\,w\in\Ww'_L)$ are independent Poisson random
  variables with $\E Z_w=1/h(w)$.
  Thus $\bGraph{s}{0}$ converges in law as $s\to\infty$ to
  a limiting distribution supported on the graphs
  made up of disjoint unions of cycles.
  For different values of $s$, the chains $\bGraph{s}{t}$
  differ only in their
  initial distributions, and the convergence in law
  of $\bGraph{s}{0}$ as $s\to\infty$ induces the process convergence
  of $\{\bGraph{s}{t},\,0\leq t\leq T\}$
  to a Markov
  chain $\{\bGraph{}{t},\,0\leq t\leq T\}$ with the same transition rates
  whose initial distribution is the limit
  of $\bGraph{s}{0}$.

  For any finite
  edge-labeled graph $G$, let $\phi_{w}(G)$ be the number of
  cycles in $G$ with word~$w$.
  By \thref{lem:EKcont} and the continuous mapping theorem, the process
  $(\phi_{w}(\bGraph{s}{t}),\,
  w\in\Ww_L')$ converges in law to $(\phi_{w}(\bGraph{}{t}),\,w\in\Ww_L')$
  as $s\to\infty$.

  We will now demonstrate that this process has the same law
  as $(\bM{w}{t},\,w\in\Ww_L')$.
  The graph $\bGraph{}{t}$ consists of disjoint cycles at time $t=0$,
  and as it evolves, these cycles shrink or are destroyed.  The process
  $(\phi_{w}(\bGraph{}{t}),\,w\in\Ww_L')$
  jumps exactly when a vertex in a cycle in $\bGraph{}{t}$ is deleted.
  If the deleted
  vertex lies in a cycle
  between two edges with the same label, the cycle shrinks.
  If the deleted vertex lies in a cycle between two edges with different
  labels, the cycle  is destroyed.
  The only relevant consideration in where the process
  will jump at time $t$ is the number of vertices of these
  two types in $\bGraph{}{t}$, which can be deduced
  from
  $(\phi_{w}(\bGraph{}{t}),\,w\in\Ww_L')$.
  Thus this process is a Markov chain.

  Consider two words $u,w\in\Ww_K'$ such that $w$ can be
  obtained from $u$ by
  doubling a letter.  Suppose that $u$ can be obtained from
  $w$ by halving any of $b$ pairs of letters.  Suppose that
  the chain is at state
  $x=(x_v,\,v\in\Ww_L')$.  There are $bx_w$ vertices that when
  deleted cause the chain to jump from $x$ to $x-e_w+e_u$, each
  of which is removed with rate one.  Thus the chain jumps
  from $x$ to $x-e_w+e_u$ with rate $bx_w$.  Similarly, it
  jumps to $x-e_w$ with rate $(|w|-c(w))x_w$.  These are
  the same rates as the chain $(\bM{w}{t},\,w\in\Ww_L')$
  from Section~\ref{sec:reversals}.  The initial distribution
  given by \eqref{eq:Gammadist} is also the same as that
  of $(\bM{w}{t},\,w\in\Ww_L')$, demonstrating that the two processes
  $\big(\phi_{w}(\bGraph{}{t}),\,w\in\Ww_L'\big)$
  and $(\bM{w}{t},\,w\in\Ww_L')$ have the same law.
  \step{2}{Approximation of $\bCy[s]{w}(t)$ by $\phi_{w}(\bGraph{s}{t})$.}

  We will compare the two processes
  $\{(\bCy[s]{w}(t),\,w\in\Ww'_K),\,0\leq t\leq T\big\}$
  and $\{(\phi_w(\bGraph{s}{t}),\,w\in\Ww'_K),\,0\leq t\leq T\}$
  and
  show that for sufficiently large $L$, they are identical with
  probability arbitrarily close to one.

  Consider some cycle in $\bG{s}{t}$; we can divide its vertices
  into those that lie between two edges of the cycle with different labels,
  and those that lie between two edges with the same label.
  We call this second class the \emph{shrinking vertices} of the cycle,
  because if one is deleted from $\bG{s}{t}$ as it evolves, the cycle
  shrinks.  We define $E_s(L)$ to be the event that for some cycle
  in $\bG{s}{0}$ of size $l>L$, at least $l-K$ of its shrinking vertices
  are deleted by time $T$.

  We claim that outside of the event $E_s(L)$, the two processes
$\{(\bCy[s]{w}(t),\,w\in\Ww'_K),\,0\leq t\leq T\}$
  and $\{(\phi_w(\bGraph{s}{t}),\,w\in\Ww'_K),\,0\leq t\leq T\}$
    are identical.  Suppose that these two processes are not identical.
  Then there is some cycle $\alpha$ of size $K$ or less present in
  $\bG{s}{t}$ but not in $\bGraph{s}{t}$ for $0<t\leq T$.
  As explained in Section~\ref{sec:lim}, as a cycle evolves (in forward
  time), it grows into an overlapping cluster of cycles.
  Thus $\bG{s}{0}$ contains some cluster of overlapping cycles
  that shrinks to $\alpha$ at time $t$.  One of the cycles in this cluster
  has length greater than $L$, or the cluster would be contained
  in $\bGraph{s}{0}$ and $\alpha$ would have been contained in $\bGraph{s}{t}$.

  To see that $l-K$ shrinking vertices must be deleted from this
  cycle, consider the evolution of $\alpha$ into the cluster
  of cycles in both forward and reverse time.  If a vertex is inserted into
  a single edge of a cycle in forward time, we see in reverse time the deletion
  of a shrinking vertex.  If a vertex is simultaneously inserted into
  two edges of a cycle, causing the cycle to split,
  we see in reverse time the deletion of a non-shrinking
  vertex of a cycle.  As $\alpha$ grows, a cycle of size greater than $L$ can form
  only by single-insertion of at least $l-K$ vertices into the eventual
  cycle.  In reverse time, this is seen as deletion of $l-K$ shrinking
  vertices.
  This demonstrates
  that $E_s(L)$ holds.

  We will now show that for any $\eps>0$, there is an $L$ sufficiently large
  that
  $\P[E_s(L)]<\eps$ for any $s$.
  Let $w\in\Ww_l/D_{2l}$ with $l>L$, and let
  $I\subset[l]$
  such that $\abs{I}=l-K$ and
  $w_i=w_{i-1}$ for all $i\in I$,
  considering indices modulo $l$.
  For any cycle in $\bG{s}{0}$
  with word $l$, the set $I$ corresponds to a set of $l-K$
  shrinking vertices of the cycle.

  We define
  $F(w,I)$ to be the event that $\bG{s}{0}$ contains one or more
  cycles with word $w$,
  and that the vertices corresponding to $I$ in one of these
  cycles are all deleted within
  time $T$.
  By a union bound,
  \begin{align}
    \P[E_s(L)]\leq\sum_{w,I}\P[F(w,I)].\label{eq:EsL}
  \end{align}

  We proceed by enumerating all pairs of $w$ and $I$.
  For any pair $w, I$, deleting the letters in $w$ at positions given
  by $I$ results in a word $u\in \Ww_K/D_{2K}$.
  For any given $u=u_1\cdots u_K\in\Ww_K/D_{2K}$, the word $w\in\Ww_l/D_{2l}$
  must have the form
  \begin{align*}
     w=
     \underbrace{u_1\cdots u_1}_{\text{$a_1$ times}}
     \underbrace{u_2\cdots u_2}_{\text{$a_2$ times}}\cdots\cdots
     \underbrace{u_K\cdots
     u_K}_{\text{$a_K$ times}},
  \end{align*}
  with $a_i\geq 1$ and $a_1+\cdots+a_K=l$.
  The number of choices for $a_1,\ldots,a_K$ is $\binom{l-1}{K-1}$,
  the number of compositions of $l$ into $K$ parts, and each
  of these corresponds to a choice of $w$ and $I$.  There are fewer
  than $a(d,K)$
  choices for $u$, giving us a bound of $a(d,K)\binom{l-1}{K-1}$
  choices of pairs $w$ and $I$ for any fixed $l>L$.

  Next, we will show that
  for any pair $w$ and $I$ with $|w|=l$,
  \begin{align}
    \P[F(w,I)]\leq (1-e^{-T})^{l-K}.\label{eq:FuI}
  \end{align}
  Condition on $\bG{s}{0}$ having $n$ vertices.
  Consider any of the $[n]_l$ possible sequences of $l$ vertices.
  Choose some representative $w'\in\Ww_l$ of $w$.
  For each of these sequences,
  the probability that
  it forms a cycle with word $w'$ is at most $1/[n]_l$ (recall the original
  definition of our random graphs in terms of random permutations).
  Given that
  the sequence forms a cycle, the probability
  that the vertices of the cycle at positions
  $I$ are all deleted within time $T$
  is $(1-e^{-T})^{l-K}$.  Hence
  \begin{align*}
    \P\left[F(w,I)\mid \text{$\bG{s}{0}$ has $n$ vertices}\right]
    &\leq [n]_l\frac{1}{[n]_l}(1-e^{-T})^{l-K},\\
    &\leq (1-e^{-T})^{l-K}.
  \end{align*}
  This holds for any $n$,
  establishing \eqref{eq:FuI}.

  Applying all of this to \eqref{eq:EsL},
  \begin{align*}
    \P[E_s(L)] &\leq \sum_{l=L+1}^{\infty}a(d,K)\binom{l-1}{K-1}(1-e^{-T})^{l-k}.
  \end{align*}
  This sum converges, which means that for any $\eps>0$,
  we have $\P[E_s(L)]<\eps$ for large enough $L$, independent of
  $s$.
  \step{3}{Approximation of $\bN{w}{t}$ by $\bM{w}{t}$.}

  Recall that we defined the processes
  $\{(\bM{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$
  and $\{(\bN{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$
  on the same probability space.  We will show that for sufficiently
  large $L$, the two processes
  are identical with probability arbitrarily close to one.

  By their definitions, these two  processes
  are identical unless one of the processes $X_{u,s}(\cdot)$ started
  at each atom of $\chi$ grows from a word of size $K$ or less to
  a word of size $L+1$ before time $T$; we call this event $E(L)$.
  Let
  \begin{align*}
    Y=\big|\big\{(u,s)\in\chi\colon |u|\leq K,\,s\leq T\big\}\big|,
  \end{align*}
  the number of processes starting from a word of size $K$ or less
  before time $T$.

  Suppose that $X(\cdot)$ has law
  $\wchain{w}$ for some word $w\in\Ww_k/D_{2k}$.
  We can choose $L$ large enough that
  $\P\big[|X(T)|>L\big]<\eps$ for all $k\leq K$.
  Then
  $\P[E(L)\mid Y]<\eps Y$ by a union bound, and so
  $\P[E(L)]<\eps\E Y$.  Since $\E Y<\infty$, we can
  make $\P[E(L)]$ arbitrarily small by choosing sufficiently large $L$.
  \step{4}{Weak convergence of $\{(\bCy[s]{w}(t),\,w\in\Ww'_K),\,0\leq t\leq T
    \}$
   to $\{(\bN{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$.}

  If two processes are identical with probability
  $1-\eps$, then the total variation distance between their laws is at most
  $\eps$.  Thus, by steps~2 and~3, we can choose $L$ large enough that
  the laws of the processes
  $\{(\bCy[s]{w}(t),\,w\in\Ww'_K),\,0\leq t\leq T\}$ and
  $\{(\phi_w(\bGraph{s}{t},\,w\in\Ww'_K),\,
  0\leq t\leq T)\}$ are arbitrarily close in total variation distance,
  uniformly in $s$, and so that the laws of
  $\{(\bM{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$ and
     $\{(\bN{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}\}$
     are arbitrarily close in total variation distance.
  Since total variation distance dominates the Prokhorov metric (or any other
  metric for the topology of weak convergence), we can
  choose $L$ such that these two pairs are each within $\eps/3$ in
  the Prokhorov metric.
  Since $\{(\phi_w(\bGraph{s}{t}),\,w\in\Ww'_K),\,0\leq t\leq T\}$
  converges in law to $\{(\bM{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$
  as $s\to\infty$, there is an $s_0$ such that for all $s\geq s_0$, the laws
  of these processes are within $\eps/3$ in the Prokhorov metric.
  We have thus shown that for every $\eps>0$,
  the laws of $\{(\bCy[s]{w}(t),\,w\in\Ww_K'),\,0\leq t\leq T\}$
  and
     $\{(\bN{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$
     are within $\eps$
  for sufficiently large $s$, which proves that the first process
  converges in law to the second in the space $D_{\RR^{\abs{\Ww'_K}}}[0,T]$
  as $s\to\infty$.
  \step{5}{Weak convergence of $\{(\Cy[s]{w}(t),\,w\in\Ww'),\,t\geq 0\}$
  to $\{(\N{w}{t},\,w\in\Ww'),\,t\geq 0\}$.}

    It follows
  immediately from the previous step that
  the (not time-reversed) process
  $\{(\Cy[s]{w}(t),\,w\in\Ww'_K),\,0\leq t\leq T\}$
  converges in law to
  $\{(\N{w}{t},\,w\in\Ww'_K),\,0\leq t\leq T\}$ for any $T>0$.
  By Theorem~16.17 in \cite{Bil},
  $\{(\Cy[s]{w}(t),\,w\in\Ww'_K),\,t\geq 0\}$
  converges in law to
  $\{(\N{w}{t},\,w\in\Ww'_K),\,t\geq 0\}$.
  By \cite[Section~3.11, Exercise~23]{EK}, this also also proves that
  $\{(\Cy[s]{w}(t),\,w\in\Ww'),\,t\geq 0\}$
  converges in law to
  $\{(\N{w}{t},\,w\in\Ww'),\,t\geq 0\}$.

\end{proof}

\begin{proof}[Proof of Theorem~\ref{mainthm:cycles}]
We will express the graph cycle counts as functionals
of $\big(\Cy[s]{w}(t),\,w\in\Ww'\big)$.  The number of $k$-cycles in $G(s+t)$ is given by
$\Cy[s]{k}(t)=\sum_{w\in\Ww_k/D_{2k}}\Cy[s]{w}(t)$.
Let
\[
\N{k}{t}=\sum_{w\in\Ww_k/D_{2k}}\N{w}{t}.
 \]
 By \thref{lem:EKcont} and
the continuous mapping theorem, $\{(\Cy[s]{k}(t),\,k\in\NN),\,t\geq 0\}$
converges in law to $\{(\N{k}{t},\,k\in\NN),\,t\geq 0\}$ as $s\to\infty$.

It is not hard to see that this limit is Markov and admits the following
representation: Cycles of size $k$ appear spontaneously with rate
$\sum_{w\in\Ww_k/D_{2k}}\mu(w)$. The size of each
cycle then grows as a pure birth process with generator
$L f(i) = i\left( f(i+1) - f(i)\right)$.
The only thing we need to verify is that
\begin{align}
  \label{eq:ratecount}
\sum_{w\in\Ww_k/D_{2k}}\mu(w)=\sum_{w\in\Ww_k/D_{2k}}\frac{k-c(w)}{h(w)}=\frac{a(d,k)-a(d,k-1)}{2}.
\end{align}
This follows from Lemma~\ref{lem:wordcounts} in the following way. From that lemma we get
\[
\sum_{w \in \Ww_k/D_{2k}} \frac{c(w)}{h(w)}= (k-1) \sum_{w\in \Ww_{k-1}/D_{2(k-1)}}\frac{1}{h(w)}.
\]
Thus
\[
\sum_{w\in\Ww_k/D_{2k}}\mu(w)=\sum_{w \in \Ww_k/D_{2k}}\frac{k}{h(w)} -  \sum_{w\in \Ww_{k-1}/D_{2(k-1)}}\frac{k-1}{h(w)}.
\]
The two terms on the right side of the above equation are simply half the total number of cyclically reduced words possible, of size $k$ and $k-1$ respectively. The total number of cyclically reduced words of size $k$ on an alphabet of size $d$ is by definition $a(d,k)$, showing \eqref{eq:ratecount} and completing the proof.
\end{proof}

So far, we have considered $d$ as a constant. We now view
it as a parameter of the graph and allow it to vary.
Recall that $(\pi_d^{(n)},\,n\geq 1)$ are towers of random
permutations independent for each $d$, and that
$G(n,2d)$ is defined from $\pi_1^{(n)},\ldots,\pi_d^{(n)}$.
For each $d$, we follow the construction used to define
$G(t)$ and construct $G(t,2d)$, a continuous-time version
of $(G(n,2d),\,n\in\NN)$.  Let $\Ww'(d)$ be the set of equivalence
classes of cyclically reduced words as before, with the parameter $d$
made explicit.  Define $\Cy[s]{d,k}(t)$
as the number of $k$-cycles in $G(s+t, 2d)$ and consider
the convergence of the two-dimensional field $\{(\Cy[s]{d,k}(t),\,
d,k\in\NN),\,t\geq 0\}$ as $s\to\infty$.

Again, we will consider this process as a functional of another one.
Define $\Ww'(\infty)=\bigcup_{d=1}^{\infty}\Ww'(d)$,
noting that $\Ww'(1)\subset\Ww'(2)\subset\cdots$.
For any $w\in\Ww'(d)$, the number of cycles in $G(s+t,2d')$
with word $w$ is the same for all $d'\geq d$.
We define $\Cy[s]{w}(t)$ by this, so that
\begin{align*}
  \Cy[s]{d,k}(t)=\sum_{\substack{w\in\Ww'(d)\\|w|=k}}\Cy[s]{w}(t).
\end{align*}
Then we will
prove convergence of $\{(\Cy[s]{w}(t),\,w\in\Ww'(\infty)),\,t\geq 0\}$
as $s\to\infty$.

To define a limit for this process,
we extend $\mu$ to a measure on all of $\Ww'(\infty)$ and define
the Poisson point process $\chi$ on $\Ww'(\infty)\times[0,\infty)$.
The rest of the construction is identical to the one in
Section~\ref{sec:limdef}, giving
us random variables $\big(\N{w}{t},\,w\in\Ww'(\infty)\big)$.

\begin{thm}\thlabel{thm:jointdconvergence}
  The process $\big(\Cy[s]{w}(\cdot),\,w\in\Ww'(\infty)\big)$ converges in law
  as $s\to\infty$ to
  $\big(\N{w}{\cdot},\,w\in\Ww'(\infty)\big)$.
\end{thm}
\begin{proof}
  For every $d$, we have shown in \thref{thm:convergence} that
  $\big(\Cy[s]{w}(\cdot),\,w\in\Ww'(d)\big)$ converges in law
  as $s\to\infty$ to
  $(\N{w}{\cdot},\,w\in\Ww'(d))$.
  The rest of the proof then just amounts to the statement that weak convergence
  in $D_{\RR^k}[0,\infty)$ for each $k$ amounts to convergence in $D_{\RR^{\infty}}[0,\infty)$,
  just as in the very end of the proof of \thref{thm:convergence}.
\end{proof}

\begin{thm}\thlabel{mainthm:intertwining}
There is a joint process convergence of $(C_{i,k}^{(s)}(t), \; k \in \NN,\; i \in [d],\; t \ge 0)$ to a limiting process $(\limitN_{i,k}(t),\; k \in \NN,\; i\in [d], \; t\ge 0)$. This limit is a Markov process whose marginal law for every fixed $d$ is described in Theorem~\ref{mainthm:cycles}.

Moreover, for any $d\in \NN$, the process $(\limitN_{d+1, k}(\cdot) - \limitN_{d,k}(\cdot), \; k \in \NN)$ is independent of the process $(\limitN_{i,k}(\cdot),\; k \in \NN,\; i\in [d])$ and evolves as a Markov process.

Its generator (defined on functions dependent on finitely many coordinates) is given by
\[
Lf(x)= \sum_{k=1}^\infty k x_k\left[ f\left( x + e_{k+1} - e_k  \right) - f(x)\right] + \sum_{k=1}^\infty \nu(d,k) \left[ f(x + e_k) - f(x) \right],
\]
where $x$ is a nonnegative sequence, $(e_k, k \in \NN)$ are the canonical orthonormal basis of $\ell^2$, and
\[
\nu(d,k)=\frac{1}{2}\left[ a(d+1, k) - a(d+1,k-1) - a(d,k) + a(d, k-1)  \right].
\]
\end{thm}

\begin{proof}
  Let
  \begin{align*}
    \N{d,k}{t}= \sum_{\substack{w\in\Ww'(d)\\|w|=k}}\N{w}{t}.
  \end{align*}
  By \thref{lem:EKcont}, the continuous mapping theorem, and
  \thref{thm:jointdconvergence}, $(\N{d,k}{\cdot},\,d,k\in\NN)$
  is the limit of $(\Cy[s]{d,k}(\cdot),\,d,k\in\NN)$ as $s\to\infty$.

 Let us now describe what the limiting process is. It is obvious that $(\N{d,k}{\cdot},\; k\in \NN, \; d \in \NN)$ is jointly Markov. For every fixed $d$, the law of the corresponding marginal is given by Theorem~\ref{mainthm:cycles}. To understand the relationship across $d$, notice that cycles of size $k$ in $G(t,2(d+1))$ consist of cycles of size $k$ in $G(t,2d)$ and the extra cycles that contain an edge labeled by $\pi_{d+1}$ or $\pi_{d+1}^{-1}$. Thus
 \begin{align}
 N_{d+1, k}(t) - N_{d, k}(t)= \sum_{\substack{w\in \Ww'(d+1)\backslash \Ww'(d)\\ \abs{w}=k}} N_w(t)
 \label{eq:d+1-d}
 \end{align}
 This process is independent of
 $(N_{i, \cdot}$, $i\in [d])$, since the set of words involved are disjoint. Moreover, the rates for this process are clearly the following: cycles of size $k$ grow at rate $k$ and new cycles of size $k$ appear at rate $[a(d+1, k) - a(d+1, k-1) - a(d,k) + a(d, k-1)]/2$. This completes the proof of the result.
\end{proof}

\section{Process limit for linear eigenvalue statistics}
\label{sec:processlimitforlinear}
\subsection{The limiting cycle structure}
As in Section~\ref{sec:eigenfluc}, we must transfer our results from cycles
to cyclically non-backtracking walks.
  Call a cyclically non-backtracking walk \emph{bad} if it is anything other
  than a repeated walk around a cycle.

\begin{prop}\thlabel{prop:nooverlaps}
  Fix an integer $K$.  There is a random time $T$, almost surely finite,
  such that there are no bad cyclically non-backtracking walks of
  length $K$ or less in $G(t)$ for all $t\geq T$.
\end{prop}
\begin{proof}
  We will work with the discrete-time version of our process $(G_n,\,n\in\NN)$.
  We first define some machinery
  introduced in \cite{LP}.
  Consider some cyclically non-backtracking walk of length $k$
  on the edge-labeled complete graph $K_n$ of the form
  \begin{align*}
  \begin{tikzpicture}[baseline, auto]
    \begin{scope}[anchor=base west]
      \path (0,0) node (s0) {$s_0$}
            (s0.base east)+(1.1,0) node (s1) {$s_1$}
            (s1.base east)+(1.1,0) node (s2) {$s_2$}
            (s2.base east)+(1.1,0) node (s3) {$\cdots$}
            (s3.base east)+(1.1,0) node (s4) {$s_k=s_0.$};
    \end{scope}
    \foreach\i [remember=\i as \lasti (initially 0)] in {1, ..., 3}
      \draw[->] (s\lasti.mid east)-- node {$w_\i$} (s\i.mid west);
    \draw[->] (s3.mid east)--node {$w_k$} (s4.mid west);
  \end{tikzpicture}
  \end{align*}
    Here, $s_i\in[n]$ and $w=w_1\cdots w_k$ is the word
    of the walk (that is, each $w_i$
    is $\pi_j$ or $\pi_j^{-1}$ for some $j$, indicating which
    permutation provided the edge for the walk).
    We say that $G_n$ contains the walk if the random permutations
    $\pi_1,\ldots,\pi_d$ satisfy $w_i(s_{i-1})=s_i$.  In other words,
    $G_n$ contains a walk if considering both as edge-labeled directed
    graphs, the walk is a subgraph of $G_n$.

    If $(s'_i,\,0\leq i\leq k)$ is another walk with the same word, we say
    that the two walks are of the same \emph{category} if $s_i=s_j\iff
    s'_i=s_j'$.  In other words, two walks are of the same category
    if they are identical up to relabeling vertices.
    The probability that $G_n$ contains a walk depends only on its category.
    If a walk contains $e$ distinct edges, then
    $G_n$ contains the walk with probability at most $1/[n]_e$.

    Let $X_k^{(n)}$ be the number of bad walks of length $k$
    in $G_n$ that
    start at vertex $n$.
    We will first prove that with probability one, $X_k^{(n)}>0$
    for only finitely many $n$.
    Call a category bad if the walks in the category are bad.
    Let $\Tt_{k,d}$ be the number
    of bad categories of walks of length $k$.  For any particular
    bad category whose walks contain $v$ distinct vertices, there
    are $[n-1]_{v-1}$ walks of that category whose first vertex is
    $n$.  Any bad walk contains
    more edges than vertices, so
    \begin{align*}
      \E X_k^{(n)} \leq
        \frac{\Tt_{k,d}[n-1]_{v-1}}{[n]_{v+1}}\leq
     \frac{\Tt_{k,d}}{n(n-k)}.
     \end{align*}
     Since $X_k^{(n)}$ takes values in the nonnegative integers,
     $\P[X_k^{(n)}>0]\leq \E X_k^{(n)}$.
       By the Borel-Cantelli lemma, $X_k^{(n)}>0$ for only
       finitely many values of $n$.

     Thus, for any fixed $r+1$, there exists a random time $N$
     such that there are no bad walks on $G_n$ of length $r+1$ or less
     starting with vertex $n$,
     for $n\geq N$.  We claim that for $n\geq N$, there are no bad walks
     at all
     on $G_n$ with length $r$ or less.
     Suppose that $G_m$ contains some bad walk of length $k\leq r$, for some
     $m\geq N$.  As the graph evolves, it is easy to compute that with
     probability one, a new vertex is eventually inserted into an edge
     of this walk.
     But at the time $n>m\geq N$ when this occurs, $G_n$ will contain
     a bad walk of length $r+1$ or less starting with vertex $n$, a
     contradiction.  Thus we have proven that $G_n$ eventually contains
     no bad walks of length $r$ or less.  The equivalent statement
     for the continuous-time version of the graph process follows easily
     from this.
\end{proof}

\newcommand{\nGamma}{\widehat{\Gamma}}
Define
\begin{align*}
  \nGamma_0(x) & = 1, \\
  \nGamma_{2k}(x) &= 2 T_{2k}(x) + \frac{2d-2}{(2d-1)^k}
  &\text{for $k \geq 1$,}\\
  \nGamma_{2k+1}(x) &= 2 T_{2k+1}(x)&\text{for $k \geq 0$.}
\end{align*}
Note that $\nGamma_i(x)$ is the same as $\Gamma_i(x)$
from Section~\ref{sec:flucresults}, except that
$x$ and $d$ are replaced by $2x$ and $2d$.
\begin{definition}\thlabel{def:tr}
  Let $G$ be a $2d$-regular graph on $n$ vertices.
  Let $f(x)$ be a polynomial expressed in the basis $\{\nGamma_i(x),\,i\geq 0\}$
  as
  \begin{align*}
    f(x) = \sum_{j=0}^k a_j\nGamma_j(x).
  \end{align*}
  We define $\tr f(G)$ as
  \begin{align*}
    \sum_{i=1}^n f(\lambda_i) - na_0,
  \end{align*}
  where $\lambda_1\geq\cdots\geq\lambda_n$ are the eigenvalues
  of the adjacency matrix of $G$ divided by $2\sqrt{2d-1}$.

\end{definition}
\begin{rmk}\thlabel{rmk:tr}
  The polynomial $f(x)-a_0$ is orthogonal to $1$ with respect to the Kesten--McKay law \eqref{eq:kmlaw},
  since $\nGamma_1(x),\nGamma_2(x),\ldots$ are orthogonal to $1$ with respect to this measure.
  (To prove this, observe that each of these polynomials can
  be written in terms of the orthogonal polynomials of \cite[Example~5.3]{Sodin}.
  This is done in the proof of \cite[Proposition~32]{DJPP}.)
  This orthogonalization keeps $\tr f(G_n)$ of constant order when
  $n\to\infty$. One can calulate $a_0$ by integrating $f$ against the Kesten-McKay law:
  \begin{align*}
    a_0 = \int_{-2}^2 f(x)\frac{2d(2d-1)\sqrt{4-x^2}}{2\pi \bigl(4d^2 - (2d-1)x^2\bigr)}\,dx.
  \end{align*}
  The most important set of functions for us will be the Chebyshev
  polynomials. For $T_k(x)$ with $k\geq 1$,
  \begin{align*}
    a_0 &= \begin{cases}
      0 &\text{if $k$ is odd,}\\
      -\frac{d-1}{(2d-1)^{k/2}} & \text{if $k$ is even.}
    \end{cases}
  \end{align*}
\end{rmk}

       \newcommand{\BadW}[2][\infty]{B_{#2}^{(#1)}}
\begin{proof}[Proof of Theorem~\ref{mainthm:eigenvalues}]
  Let $\CNBW[s]{k}(t)$ denote the number of cyclically non-backtracking
  walks of length $k$ in $G(s+t)$.  We decompose these into
  those that are repeated walks around cycles of length $j$ for some
  $j$ dividing $k$, and the remaining bad walks, which
  we denote $\BadW[s]{k}(t)$, giving us
  \begin{align*}
    \CNBW[s]{k}(t)=\sum_{j\mid k}2j\Cy[s]{j}(t)+\BadW[s]{k}(t).
  \end{align*}

  Proposition~\ref{prop:nooverlaps} implies that
  \begin{align*}
    \lim_{s\to\infty}\P\big[\text{$\BadW[s]{k}(t)=0$ for all
      $k\leq K$, $t\geq 0$}\big]=1.
  \end{align*}
  This together with \thref{lem:EKcont} and Theorem~\ref{mainthm:cycles}
  shows that
  as $s$ tends to infinity,
  \begin{align}\label{eq:wrongbasis}
    \big(\CNBW[s]{k}(\cdot),\,1\leq k\leq K\big)\toL
    \bigg(\sum_{j\divides k}2j\N{j}{\cdot},\,1\leq k\leq K\bigg).
  \end{align}

  Now, we modify the polynomials $\nGamma_k$
  to form a new basis $\{f_k,\,k\in\NN\}$ with the right properties,
  which amounts to expressing each $\N{k}{t}$ as a linear combination
  of terms $\sum_{j\divides l}2j\N{j}{t}$.  We do this
  with the M\"obius inversion formula.  Define the polynomial

  \begin{align}
    f_k(x) = \frac{1}{2k}\sum_{j\divides k}\mu
    \left(\frac{k}{j}\right)
      (2d-1)^{j/2}\nGamma_j(x),\label{eq:fbasis}
  \end{align}
  where $\mu$ is the M\"obius function, given by
  \begin{align*}
    \mu(n) = \begin{cases}
       (-1)^a&\text{if $n$ is the product of $a$ distinct primes,}\\
       0&\text{otherwise.}
    \end{cases}
  \end{align*}
  From \thref{prop:cnbweigenvalues},
  \eqref{eq:wrongbasis}, and the continuous mapping
  theorem,
  \begin{align*}
    \bigl( \tr f_k(G(s+\cdot)), \, k \in [K]\bigr) \toL
    \bigl(N_k(\cdot),\,k\in[K]\bigr)
  \end{align*}
  as desired.

  For an arbitrary polynomial~$f$, let $\hat{f}$ denote $f-a_0$, the orthogonalized
  version of $f$ from \thref{def:tr}. The polynomial $\hat{f}$ is a linear combination
  of $f_1,f_2,\ldots$, and so the process $\tr f(G(s+\cdot))$ converges to a linear
  combination of the coordinate processes of $(N_k(\cdot),\,k\in\NN)$.
\end{proof}
\subsection{Some properties of the limiting object}
  To prove the process convergence in \thref{mainthm:chebycov,thm:diagonallimit}, we need to know more
  about the limiting cycle process $(N_k(\cdot),\,k\in\NN)$.
  Though the limiting object is not defined in terms of graphs,
  we will nonetheless refer to $N_k(t)$ as the number of $k$-cycles at time~$t$
  in the limiting object. Similarly, if one of the Yule processes counted to define
  the limiting object increases from $j$ to $k$, we will refer to this as a cycle growing
  from size~$j$ to~$k$.

  We start our study of the limiting object
  by decomposing $N_k(t)$ into independent summands in terms
  of the process at time~$s$.
  We first give a definition related to this decomposition.
  \begin{definition}
    Let the random variable $\alpha_{s,t}(j,k)$ be
    the portion of $j$-cycles at time~$s$ that grow to be $k$-cycles
    at time~$t$ in the limiting object. When $s$ and $t$ are clear from context, we will just
    write this as $\alpha(j,k)$.
  \end{definition}
  \begin{lem}\thlabel{lem:Ealphaval}
    For $j\leq k$ and $s\leq t$,
    \begin{align}
      \E \alpha_{s,t}(j,k) = \binom{k-1}{k-j}e^{j(s-t)}\bigl(1-e^{s-t}\bigr)^{k-j}.\label{eq:Ealphaval}
    \end{align}
  \end{lem}
  \begin{proof}
    The quantity $\E \alpha_{s,t}(j,k)$ is the probability that a Yule process
    started from $j$ is at $k$ at time~$t-s$.
    It is known that this is given
    by \eqref{eq:Ealphaval} (see \cite[Exercise~2.11]{Lig}, for example),
    but we will give a proof of it anyhow.

    We start with the case that $j=1$, and we assume $s=0$.
    Let $X_t$ be a Yule process from $1$. We would like to show that
    \begin{align}
      \P[X_t=k] = e^{-t}\bigl(1-e^{-t}\bigr)^{k-1},\label{eq:X_tgeo}
    \end{align}
    or equivalently that $X_t-1\sim\Geo\bigl(e^{-t}\bigr)$.
    Let $S_1,S_2,\ldots$ be the holding times of the Yule process. By definition,
    they are independent, with $S_i\sim\Exp(i)$.
    Then
    \begin{align*}
      \P[X_t> k] = \P[S_1+\cdots+S_{k}\leq t].
    \end{align*}
    Now, let $\tau_1,\ldots,\tau_k$ be i.i.d.\ with distribution $\Exp(1)$,
    and consider a counting process with these $k$ points as its jump times.
    Then the first holding time is $\Exp(k)$, the next $\Exp(k-1)$, and so on.
    Thus
    \begin{align*}
      \P[S_1+\cdots+S_{k}\leq t] = \P[\tau_1,\ldots,\tau_k\leq t] = \bigl(1-e^{-t}\bigr)^k,
    \end{align*}
    which shows that $X_t-1\sim\Geo\bigl(e^{-t}\bigr)$, confirming \eqref{eq:X_tgeo}.

    To extend this to $j>1$, let $Y_t$ be the sum of $j$ independent Yule processes starting
    from $1$.
    This makes $Y_t$ a Yule process starting from $j$. The random variable $Y_t-j$ is a sum of independent
    $\Geo(e^{-t})$ random variables and thus is negative binomial, the distribution of the number of
    failures before $j$ successes occur in independent Bernoulli trials with a success rate of $e^{-t}$.
    Consulting \cite[eq.~VI.8.1]{Feller} for a formula for this distribution,
    \begin{align*}
      \P[Y_t-j = k-j] &= \binom{k-1}{j-1}e^{-jt}(1-e^{-t}\bigr)^{k-j},
    \end{align*}
    which matches \eqref{eq:Ealphaval} after the substitution of $t-s$ for $t$.
  \end{proof}

  We now give our decomposition of $N_k(t)$:
  \begin{lem}\thlabel{lem:decomp}
    Let $j\leq k$ and $s\leq t$.
    The random variable $N_k(t)$ can be decomposed
    into independent, Poisson-distributed summands as
    \begin{align}
      N_k(t) = \sum_{j=1}^k \alpha_{s,t}(j,k)N_{j}(s) + Z.\label{eq:decompN}
    \end{align}
  \end{lem}
  \begin{proof}
    All $k$-cycles at time~$t$ are either $j$-cycles at time~$s$
    that grow to size~$k$, or they are spontaneously formed.
    The random variable $\alpha_{s,t}(j,k)N_j(s)$ is the number of $j$-cycles that grow to
    size~$k$, and we define $Z$ to be the number of cycles that form spontaneously at times in $(s,t]$
    and have size~$k$ at time~$t$. We then have \eqref{eq:decompN}, and we just need to
    to confirm that the summands are independent and Poisson.
    Cycles at time~$s$ grow independently of each other and of the spontaneously formed cycles,
    which confirms the independence.
    By Raikov's theorem on decompositions of the Poisson distribution into independent
    sums \cite[19.2A]{Loeve}, each summand is Poisson, completing the proof.

    This last step is needlessly slick: The random variable $\alpha_{s,t}(j,k)N_j(s)$ is a thinned
    version of a Poisson random variable and hence Poisson itself. A similar argument applies to $Z$.
  \end{proof}

Next, we compute the covariance structure of our limiting object.
\begin{prop}\thlabel{cor:cyclecov}
For any $s \leq t$ and $j,k\in \NN$,
\[
\cov(N_k(t), N_j(s)) =
\begin{cases}
\frac{a(d,j)}{2j}\binom{k-1}{k-j}e^{j(s-t)}\bigl(1-e^{s-t}\bigr)^{k-j} & \text{if $j\leq k$,}\\
0 &\text{otherwise.}
\end{cases}
\]
\end{prop}

\begin{proof}

   Suppose $j>k$. As $\{N_i(s),\, i\geq 1\}$ are independent,
   the decomposition~\eqref{eq:decompN} shows that $N_k(t)$ is independent of $N_j(s)$.
   Intuitively, cycles of size greater than $k$ at time~$s$ do not affect
   the cycles of size~$k$ at time~$t$.

When $j\leq k$, the result follows immediately from \thref{lem:Ealphaval,lem:decomp} by decomposing
$N_k(t)$ and taking expectations.
\end{proof}

  \subsection{The process convergence}

  \begin{lem}\thlabel{lem:prm}
    Let $\xi$ be a Poisson random measure on $[0,\infty)$
    with arbitrary $\sigma$-finite intensity measure.
    Let $T_1,T_2,\ldots$ denote the atoms of $\xi$.
    Let $(\tau_i,\,i\geq 1)$ be arbitrary nonnegative
    i.i.d.\ random variables.
    Form a new point process $\zeta$ with atoms
    $T_i+\tau_i$.
    Then $\zeta$ is also a Poisson random measure on $[0,\infty)$.
  \end{lem}
  \begin{proof}
    Let $\mu$ be the intensity measure of $\xi$, and let $P$ be the distribution
    of $\tau_i$.
    We have made $\xi$ into a marked point process, giving
    each atom $T_i$ an independent mark $\tau_i$.
    This is equivalent
    to defining $\{(T_i,\tau_i),\,i\geq 1\}$ to be the atoms
    of a Poisson random measure on $[0,\infty)^2$ with intensity
    measure $\mu\otimes P$ \cite[Corollary~VI.3.5]{Cinlar}. The point process~$\zeta$
    is a deterministic transformation of this one by the map
    $(x,y)\mapsto x+y$, and is hence also a Poisson random measure \cite[Remark~VI.2.4b]{Cinlar}.
  \end{proof}

  The following technical lemma will be used in both \thref{mainthm:chebycov,thm:diagonallimit}.
\begin{lem}\thlabel{lem:tightness}
  Fix $k$ and $T$, and consider $\bigl\{(2d-1)^{-k/2}\bigl(2kN_k(\cdot)-a(d,k)\bigr),\,d\geq 1\bigr\}$,
  a collection of processes in $D[0,T]$ indexed by $d$. This collection is tight.
\end{lem}
\begin{proof}
  Fix $d$, and  define $Y_k(t)$ as the process that starts at $0$ and increases at each point of
  increase of $N_k(t)$; define $Z_k(t)$ as the process that starts at $0$ and increases
  at each point of decrease of $N_k(t)$. Thus, we have $N_k(t)-N_k(0)=Y_k(t)-Z_k(t)$.
  As $N_k(t)$ almost surely jumps
  only by $1$ and $-1$, both $Y_k(t)$ and $Z_k(t)$ are counting processes.
  Observe that $Y_k(t)$
  counts $k$-cycles formed spontaneously or by growth in the time interval $(0,t]$,
  and $Z_k(t)$ counts $k$-cycles that jump to size~$k+1$ in the time interval $(0,t]$.
  \begin{claim}
    The processes $Y_k(t)$ and $Z_k(t)$ are (non-independent) Poisson processes
    with rate $a(d,k)/2$.
  \end{claim}
  \begin{proof}
  We argue by induction on $k$. As our base case,
  the process $Y_1(t)$ jumps
  when $1$-cycles form spontaneously, which happen according to a Poisson process
  of rate~$a(d,1)/2$. Now, assume that $Y_k(t)$ is a Poisson process of rate~$a(d,k)/2$.
  First, we argue that $Z_k(t)$ is as well.
  Let $\xi$ be the Poisson point process whose atoms are the points of increase of $Y_k(t)$,
  with an extra $N_k(0)$ atoms at $0$. Each atom $T_i$ of $\xi$ is the time that a $k$-cycle
  forms (or $0$ if it was present from the start). Let $\tau_i$ be the amount of time after $T_i$
  that the corresponding $k$-cycle jumps to $k+1$. Then $(\tau_i,\,i\geq 1)$ are i.i.d.,
  and $T_i+\tau_i$ are the jump times of $Z_k(t)$. By \thref{lem:prm},
  $Z_k(t)$ is a (possibly inhomogeneous) Poisson process.
  By the stationarity of the limiting object, $\E N_k(t)=\E N_k(0)$, and hence
  $\E Z_k(t)=\E Y_k(t)=a(d,k)/2$, showing that $Z_k(t)$ is a homogeneous Poisson process
  with rate $a(d,k)/2$.

  To complete the induction, we must show that $Y_{k+1}(t)$ is a Poisson process
  of rate $a(d,k+1)/2$. To see this, observe that $Z_k(t)$ counts all $(k+1)$-cycles
  that form by growth in the time interval $(0,t]$. As $Y_{k+1}(t)$ counts all $(k+1)$-cycles
  that form by growth or spontaneously in that interval, it is the sum of $Z_k(t)$
  and an independent Poisson process of rate $\bigl(a(d,k+1)-a(d,k)\bigr)/2$. Thus
  it is a Poisson process of rate $a(d,k+1)/2$.
  \end{proof}
  Now, fix $k$ and let
   $ X_d(t) = (2d-1)^{-k/2}\bigl(2kN_k(t) - a(d,k)\bigr)$.
   We need to show that $\{X_d,\,d\geq 1\}$ is tight.
  As $N_k(t)-N_k(0) = Y_k(t)-Z_k(t)$, we have
  \begin{align*}
    \frac{1}{2k}X_d(t)  &= A_d+B_d(t) - C_d(t)
  \end{align*}
  where
  \begin{align*}
    A_d &= (2d-1)^{-k/2}\biggl(N_k(0) - \frac{a(d,k)}{2k}\biggr),\\
    B_d(t) &= (2d-1)^{-k/2}\biggl(Y_k(t)-\frac{a(d,k)t}{2}\biggr),\\
    C_d(t) &= (2d-1)^{-k/2}\biggl(Z_k(t)-\frac{a(d,k)t}{2}\biggr).
  \end{align*}
  with $Y_k(t)$ and $Z_k(t)$ implicitly depending on $d$.

  As $d\to\infty$, the random variable $A_d$ converges in law to Gaussian, and $B_d(t)$ and $C_d(t)$
  converge in law to Brownian motion.
  Viewing $A_d$, $B_d(t)$, and $C_d(t)$ as elements of $D[0,T]$, each thus converges
  weakly to a limit in $C[0,T]$. As tightness in a product space is equivalent to tightness
  of the marginals, the sequence $(A_d,B_d,C_d)$ is tight in $D^3[0,t]$, with all weak limit
  points lying in $C^3[0,t]$.

  Given a subsequence of $\{X_d(\cdot)$\}, choose a further subsequence $\{X_{d_i}(\cdot)\}$
  such that $(A_{d_i},B_{d_i},C_{d_i})$ converges. The map
  \begin{align*}
    (x(t),y(t),z(t))\mapsto x(t) + y(t) - z(t)
  \end{align*}
  is not in general continuous from $D^3[0,T]\to D[0,T]$, but it is continuous
  at $C^3[0,T]$. (This holds because Skorokhod convergence to a continuous function implies
  uniform convergence.) By the continuous mapping theorem, $A_{d_i}+B_{d_i}-C_{d_i}$
  has a weak limit. Thus we have shown that every subsequence of $\{X_d(\cdot)\}$ has a subsequence
  with a weak limit.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{mainthm:chebycov}]
  By \thref{prop:cnbweigenvalues} and \eqref{eq:wrongbasis},
  \begin{align}
2 \tr  T_k\left( G(\infty + t) \right)  = (2d-1)^{-k/2} \sum_{j\mid k} 2j \limitN_j(t).\label{eq:cheblimit}
  \end{align}

Now, we will prove finite-dimensional convergence to the stated Ornstein-Uhlenbeck process.
Fix $K\in\NN$ and a sequence of times $t_1<\cdots<t_n$.
We first show that the random vector
\begin{align}
  \Bigl( (2d-1)^{-k/2}\bigl(N_k(t_i)-\E N_k(t_i)\bigr),\;k\in[K],\,i\in[n]\Bigr) \label{eq:mvg}
\end{align}
converges to a multivariate Gaussian, using a slight extension of the decomposition
from \thref{lem:decomp}.
Let $\Ss$ be the set of sequences $s_1,\ldots,s_n$ with $s_i\in\{\delta\}\cup\NN$
that satisfy a certain set of conditions.
Each sequence will represent the history of a growing cycle, with $s_i$ the size of
the cycle at time $t_i$. The symbol $\delta$ will mean ``not yet born.''
Thus, a sequence is in $\Ss$ if it consists of zero or more $\delta$s followed
by a nondecreasing sequence of positive integers. We do not include the sequence of all $\delta$s
in $\Ss$.

Let $S=(s_1,\ldots,s_n)\in\Ss$ and suppose that $s_i$ is the first non-$\delta$ in the sequence.
When $i=1$, define $X_S$ as the number of cycles that have size~$s_j$ at time $t_j$
for all $1\leq j\leq n$. If $i>1$,
define $X_S$ as the number of cycles that form spontaneously between times $t_{i-1}$
and $t_i$ and have size $s_{j}$ at time~$t_{j}$ for $j\geq i$.

We claim that $\{X_S,\,S\in\Ss\}$ is a collection of independent Poisson random variables.
The number of cycles of each size at time~$t_1$
and the number of cycles of each size at time~$t_i$ that formed after time~$t_{i-1}$
for all $2\leq i\leq n$
are independent Poissons. Each of these random variables is then thinned to form
$\{X_S,\,S\in\Ss\}$, which thus consists of independent Poissons as well.

Now, we will write \eqref{eq:mvg} in terms of this Poisson field.
First, let $\varphi(S)$ denote the first non-$\delta$ character in $S$,
and consider the normalized field
\begin{align}
  \Bigl\{(2d-1)^{-\varphi(S)/2}(X_S-\E X_S),\,S\in\Ss\Bigr\}.\label{eq:scaledpfield}
\end{align}
Fix some $S=(s_1,\ldots,s_n)\in\Ss$ with $s_i=\varphi(S)$ the first non-$\delta$ character.
The expected number of cycles that form spontaneously between
times $t_{i-1}$ and $t_{i}$ with size~$\varphi(S)$ at time $t_i$ is $O\bigl((2d-1)^{\varphi(S)}\bigr)$
(here, we are interpreting all elements of the big-O expression as constants except for $d$).
The portion of these that grow according to $S$ is in expectation a fixed fraction of these,
with no dependence on $d$.
Thus $\E X_S = O\bigl((2d-1)^{\varphi(S)}\bigr)$.
By the Gaussian approximation to Poisson, the field~\eqref{eq:scaledpfield} converges
as $d\to\infty$ to independent Gaussians.

For each $k\in[K]$ and $i\in[n]$, we have
\begin{align*}
  (2d-1)^{-k/2}\bigl(N_k(t_i) -\E N_k(t_i)\bigr) = \sum_S (2d-1)^{-k/2}(X_S-\E X_S),
\end{align*}
where the sum ranges over all $S=(s_1,\ldots,s_n)\in\Ss$ with $s_i=k$.
Every term of the sum
with $\varphi(S)<k$ vanishes in probability, and the terms with $\varphi(S)=k$ are elements
of the field \eqref{eq:scaledpfield}. By the Gaussian convergence of \eqref{eq:scaledpfield}, the random vector \eqref{eq:mvg}
converges to Gaussian as $d\to\infty$.

Now, consider a finite-dimensional slice of the process
\begin{align}
  \left( \tr T_{k} \left(G(\infty + t) \right) - \E \tr T_{k} \left(G(\infty + t) \right),\; t\ge 0, \; k\in \NN \right),\label{eq:process}
\end{align}
choosing finitely many choices of $k$ and $t$ and forming a random vector.
Each component has the form given by \eqref{eq:cheblimit} for some $k$ and $t$.
The scaling causes all the terms of the sum there with $j<k$ to vanish in probability.
Subtracting off these terms, we have a random vector whose components are a subset of those
of \eqref{eq:mvg}. Thus the finite-dimensional distributions of \eqref{eq:process}
converge to Gaussian as $d\to\infty$.

Next, we compute the covariances.
For a fixed $d$,  from \eqref{eq:cheblimit} we have
\begin{align}\label{eq:covt}
\cov\left( \tr T_i\left( G(\infty + t) \right), \tr T_j\left( G(\infty + s) \right)  \right)= \frac{1}{4}\left( 2d-1 \right)^{-(i+j)/2}\sum_{k\mid i, \; l \mid j} 4 lk \cov\left( \limitN_k(t), \limitN_l(s) \right)
\end{align}
for $s\leq t$.
We now fix any $i, j, t, s$ and take $d$ to infinity, using the following expression
from \thref{cor:cyclecov}:
\[
\cov(N_k(t), N_l(s)) =
\begin{cases}
\frac{a(d,l)}{2l}\binom{k-1}{k-l} p^{l} (1-p)^{k-l}, \qquad p=e^{s-t}, \quad \text{if $k \ge l$}.\\
0, \quad \text{otherwise}.
\end{cases}
\]

 Any term $a(d,r)$ is asymptotically the same as $(2d-1)^r$. Thus the highest order term in $d$ on the right side of \eqref{eq:covt} is $(2d-1)^{\min(i, j)}$. Unless $i=j$, this term is negligible compared to $(2d-1)^{(i+j)/2}$. This shows that the limiting covariance is zero unless $i=j$.
On the other hand, when $i=j$, every term on the right side of \eqref{eq:covt} vanishes, except when $k=i= l=j$. Hence,
\[
\lim_{d\rightarrow \infty}\cov\left( \tr T_i\left( G(\infty + t) \right), \tr T_i\left( G(\infty + s) \right)  \right)=\frac{1}{4}2i p^{i}= \frac{i}{2}e^{i(s-t)}.
\]
Thus we have shown convergence of the finite-dimensional distributions
to the limiting process.

To show the process convergence, we appeal to \thref{lem:tightness}.
This lemma shows that all but the highest term of the sum in \eqref{eq:cheblimit}
vanishes in probability, and the remainder is a tight sequence in $d$.
This immediately gives the convergence of
  \[
\left( \tr T_{k} \left(G(\infty + t) \right) - \E \tr T_{k} \left(G(\infty + t) \right),\; t\ge 0, \; k\in \NN \right)
\]
to the limiting process not in $D_{\RR^{\infty}}[0,\infty)$, but in $D^{\infty}[0,\infty)$.
As the limit lies in $C^{\infty}[0,\infty)$, an argument as in the end of
\thref{lem:tightness} shows that the convergence holds in $D_{\RR^{\infty}}[0,\infty)$ as well.
\end{proof}