Premium
Brownian bridge asymptotics for random mappings
Author(s) -
Aldous David J.,
Pitman Jim
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050402
Subject(s) - random walk , brownian motion , mathematics , brownian bridge , limit (mathematics) , bridge (graph theory) , statistical physics , random compact set , stochastic process , random function , discrete mathematics , combinatorics , random field , mathematical analysis , physics , statistics , medicine
Uniform random mappings of an n ‐element set to itself have been much studied in the combinatorial literature. We introduce a new technique, which starts by specifying a coding of mappings as walks with ± 1 steps. The uniform random mapping is thereby coded as a nonuniform random walk, and our main result is that as n →∞ the random walk rescales to reflecting Brownian bridge. This result encompasses a large number of limit theorems for “global” characteristics of uniform random mappings. © 1994 John Wiley & Sons, Inc.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom