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.