Coalescence under Preimage Constraints

MaRDI QIDQ6314894zbMATH OpenFDO

Authors Benjamin Allen Otto

Publication date 1 March 2019

Abstract: The primary goal of this document is to record the asymptotic effects that preimage constraints impose upon the sizes of the iterated images of a random function. Specifically, given a subset $mathcalPsubseteqmathbb{Z}_{geq0}$ and a finite set $S$ of size $n$, choose a function uniformly from the set of functions $f:SightarrowS$ that satisfy the condition that $|f^{-1}(x)|inmathcalP$ for each $xinS$, and ask what $|f^k(S)|$ looks like as $n$ goes to infinity. The robust theory of singularity analysis allows one to completely answer this question if one accepts that $0inmathcalP$, that $mathcalP$ contains an element bigger than 1, and that $gcd(mathcalP)=1$; only the third of these conditions is a meaningful restriction. The secondary goal of this paper is to record much of the background necessary to achieve the primary goal.

This page was built for publication: Coalescence under Preimage Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314894)