Invariance Principles for Non-uniform Random Mappings and Trees.
David Aldous and Jim Pitman
In the context of uniform random mappings of an $n$-element set to
itself, Aldous and Pitman (1994) established a strong invariance
principle, showing that many $n \to \infty$ limit distributions can
be described as distributions of suitable functions of reflecting
Brownian bridge. To study non-uniform cases, in this paper we formulate
a {\em weak invariance principle} in terms of iterates of a fixed number
of random elements. We show that the weak invariance principle implies
many, but not all, of the distributional limits implied by the strong
invariance principle. We give direct verifications of the weak invariance
principle in two different settings, $p$-mappings and $P$-mappings.
We compare with parallel results in the simpler setting of random trees.