Random mappings with constraints on coalescence and number of origins

James Arney and Edward A. Bender

Vol. 103 (1982), No. 2, 269–294

DOI: 10.2140/pjm.1982.103.269

Abstract

In §2 we tabulate for easy reference probability distributions associated with some functions of random mappings on large sets (e.g., number of points on cycles, size of the component containing x) when the number of immediate predecessors of each point is required to lie in some set 𝒟.

Our results allow the number of origins to be restricted, a useful constraint in some shift register situations. Although limiting the number of immediate predecessors to {0,1,2} and constraining the number of origins is in some ways a poor model for random shift registers, we show in §§3 and 4 that most of the tabulated results fit shift register data quite well.

Derivations of our results are given in §§5 through 9.

Mathematical Subject Classification 2000

Primary: 05C80

Secondary: 60C05

Milestones

Received: 3 October 1979

Published: 1 December 1982