Non-uniform random mappings and the exploration process of the ICRT

(ongoing joint work with Jim Pitman and Gregory Miermont).

In this context a 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 [3] showed how the asymptotic joint distributions of numerous statistics of a uniform random mapping are identifiable as corresponding joint distributions of reflecting Brownian bridge. Motivated in part by recent work of O'Cinneide and Pokrovskii [10] we are currently studying the case of $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 [8,5] of limits of random $p_n$-trees, we have analyzed [1] 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 [4,5] to the stochastic additive coalescent has recently been complemented by more direct constructions using Brownian excursion with drift [6] and then more general Levy or exchangeable-increment processes [7,9] such as the following. For suitable fixed positive parameters $a, \theta_1,\theta_2,\ldots$ use Brownian bridge ${B_s^{\rm br}}$ to construct a ``bridge" process

$$a {B_s^{\rm br}}+ \sum_i \theta_i (1_{(U_i \leq s)} - s), \quad 0 \leq s \leq 1 .$$

Use the 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 [2] we show how to use $(X_s)$ to construct a certain continuous-path excursion process $(X^*_s, 0 \leq s \leq 1)$ which is the 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.