\documentclass[11pt]{article}
\addtolength{\textwidth}{1.0cm}
\newcommand{\Bbr}{{B_s^{\rm br}}}
\newcommand{\GG}{\mbox{${\cal G}$}}
\newcommand{\SS}{\mbox{${\cal S}$}}
\newcommand{\sfrac}[2]{{\textstyle\frac{#1}{#2}}}
\newcommand{\CC}{\mbox{${\cal C}$}}
\newcommand{\ed}{\ \stackrel{d}{=} \ }
\newcommand{\cd}{\ \stackrel{d}{\rightarrow} \ }
\newcommand{\bx}{{\bf x}}
\pagestyle{empty}
\begin{document}

\section{Non-uniform random mappings and the exploration process of the ICRT}
(ongoing joint work with Jim Pitman and Gregory Miermont).

In this context a {\em mapping}
$\{1,2,\ldots,n\} \to 
\{1,2,\ldots,n\}$
is just a function, represented by its directed graph with
edges $(i,f(i))$.
An old paper \cite{me61} showed how the 
asymptotic joint distributions of numerous statistics of a
{\em uniform} random mapping are identifiable as corresponding
joint distributions of reflecting Brownian bridge.
Motivated in part by recent work of O'Cinneide and Pokrovskii
\cite{op00} we are currently studying the case of
{\em $p_n$-mappings}, where for fixed $n$ the random variables
$f(i), 1 \leq i \leq n$ are i.i.d. with some distribution $p_n$.
Using Joyal's bijection between mapping and trees
and our recent theory \cite{jpmc97b,me87} of limits of random
$p_n$-trees,
we have analyzed \cite{me102}
the ``uniform asymptotic negligibility" case where
the limit is Brownian bridge.  In work in preparation we study the general case where the
limit should be describable in terms of the ICRT
(inhomogeneous continuum random tree)
limit of general $p_n$-trees,
along lines indicated below.

Our ``continuum tree" approach \cite{me82,me87} to the stochastic
additive coalescent has recently been complemented by more
direct constructions using Brownian excursion with drift
\cite{bertoin00f} and then more general Levy or exchangeable-increment
processes \cite{bertoin-EAC,miermont-OAC} such as the following.
For suitable fixed positive parameters
$a, \theta_1,\theta_2,\ldots$ use Brownian bridge $\Bbr$ to
construct a ``bridge" process
\[ a \Bbr + \sum_i \theta_i (1_{(U_i \leq s)} - s), \quad 0 \leq s \leq 1 . \]
Use the {\em Vervaat transform} -- relocate the space-time
origin to the location of the infimum -- to define an
``excursion" process
$(X_s, \ 0 \leq s \leq 1)$
which has positive but not negative jumps.
In \cite{me105} we show how to use $(X_s)$ to construct
a certain {\em continuous}-path excursion process $(X^*_s, 0 \leq s \leq 1)$
which is the {\em exploration process} of the ICRT,
that is to say identifies the ICRT as the random metrization of
$[0,1]$ given by
\[ d(u_1,u_2):= 
(X_{u_1} - \inf_{u_1<u<u_2} X_u)
+
(X_{u_2} - \inf_{u_1<u<u_2} X_u),
\quad 0<u_1<u_2<1 . \]
This in turn is the process needed to define, via a
continuous analog of Joyal's transformation, 
the limit process (generalizing reflecting Brownian bridge)
of the general random $p_n$-mapping.
Formalizing this is work in preparation.

%\bibliography{small,me,biology,misc,rwgbook,alg,coag,trees,/saruman/accounts/fac/pitman/search/pitman,/saruman/accounts/fac/pitman/search/bm3,/saruman/accounts/fac/pitman/search/general,/saruman/accounts/fac/pitman/search/comb}
%\bibliographystyle{plain}
\def\cprime{$'$} \def\polhk#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth
  \lower1.5ex\hbox{`}\hidewidth\crcr\unhbox0}}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$}
  \def\polhk#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth
  \lower1.5ex\hbox{`}\hidewidth\crcr\unhbox0}}} \def\cprime{$'$}
  \def\cprime{$'$} \def\polhk#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth
  \lower1.5ex\hbox{`}\hidewidth\crcr\unhbox0}}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cydot{\leavevmode\raise.4ex\hbox{.}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{me102}
D.J. Aldous, G.~Miermont, and J.~Pitman.
\newblock Brownian bridge asymptotics for random $p$-mappings.
\newblock Technical Report 624, Dept. Statistics, U.C. Berkeley, 2002.

\bibitem{me105}
D.J. Aldous, G.~Miermont, and J.~Pitman.
\newblock The exploration process of inhomogeneous continuum random trees and
  an extension of {J}eulin's local time identity.
\newblock Technical Report 640, Dept. Statistics, U.C. Berkeley, 2003.

\bibitem{me61}
D.J. Aldous and J.~Pitman.
\newblock Brownian bridge asymptotics for random mappings.
\newblock {\em Random Structures Algorithms}, 5:487--512, 1994.

\bibitem{me82}
D.J. Aldous and J.~Pitman.
\newblock The standard additive coalescent.
\newblock {\em Ann. Probab.}, 26:1703--1726, 1998.

\bibitem{me87}
D.J. Aldous and J.~Pitman.
\newblock Inhomogeneous continuum random trees and the entrance boundary of the
  additive coalescent.
\newblock {\em Probab. Th. Rel. Fields}, 118:455--482, 2000.

\bibitem{bertoin00f}
J.~Bertoin.
\newblock A fragmentation process connected to {B}rownian motion.
\newblock {\em Probab. Theory Related Fields}, 117(2):289--301, 2000.

\bibitem{bertoin-EAC}
J.~Bertoin.
\newblock Eternal additive coalescents and certain bridges with exchangeable
  increments.
\newblock {\em Ann. Probab.}, 29:344--360, 2001.

\bibitem{jpmc97b}
M.~Camarri and J.~Pitman.
\newblock {Limit distributions and random trees derived from the birthday
  problem with unequal probabilities}.
\newblock {\em Electron. J. Probab.}, 5:Paper 2, 1--18, 2000.

\bibitem{miermont-OAC}
G.~Miermont.
\newblock Ordered additive coalescents and additive coalescents associated to
  {L}{\'e}vy processes with no positive jumps.
\newblock {\em Electron. J. Probab.}, 6:Paper 14, 1--13, 2001.

\bibitem{op00}
C.~A. O'Cinneide and A.~V. Pokrovskii.
\newblock Nonuniform random transformations.
\newblock {\em Ann. Appl. Probab.}, 10(4):1151--1181, 2000.

\end{thebibliography}

\end{document}
