# Random mappings

2.31 Definition Let *T _{n}* denote the collection of all functions (mappings) from a finite domain of size

*n*to a finite codomain of size

*n.*

Models where random elements of *T _{n}* are considered are called

*random mappings models.*In this section the only random mappings model considered is where every function from

*T*is equally likely to be chosen; such models arise frequently in cryptography and algorithmic number theory. Note that

_{n}*J-*| = n", whence the probability that a particular function from

_{n}*T*is chosen is 1

_{n}*/тг*

^{п}.- 2.32 Definition Let / be a function in
*T*with domain and codomain equal to {1.2,... , ?г}. The_{n}*functional graph*of / is a directed graph whose*points*(or*vertices*) are the elements {1,2,... , n} and whose*edges*are the ordered pairs*(x, f(x))*for all a: € {1.2,... , ?г}. - 2.33 Example
*(fmctionalgraph)*Consider the function / : {1,2,... , 13} —> {1,2,... , 13} defined by /(1) = 4, /(2) = 11, /(3) = 1, /(4) = 6, /(5) = 3, /(6) = 9, /(7) = 3, /(8) = 11, /(9) = 1, /(10) = 2, /(11) = 10, /(12) = 4, /(13) = 7. The functional graph of / is shown in Figure 2.1. □

As Figure 2.1 illustrates, a functional graph may have several *components* (maximal connected subgraphs), each component consisting of a directed *cycle* and some directed *trees* attached to the cycle.

- 2.34 Fact As
*n*tends to infinity, the following statements regarding the functional digraph of a random function / from*T*are true:_{n}- (i) The expected number of components is In ?г.

**Figure 2.1: ***Afunctional graph (see Example 2.33).*

- (ii) The expected number of points which are on the cycles is
*у/тпг/2.* - (iii) The expected number of
*terminal points*(points which have no preimages) is*n/e.* - (iv) The expected number of
*k-th iterate image points (x*is a A -th iterate image point if*x*= /(/(• • • /*(y) ■ ■*■)) for some*y)*is (1 - тд)п, where the тд satisfy the recurrence

*к* times

*To =* 0, *Tk*+1 = *e~ ^{1+Tk}* for

*к*> 0.

2.35 Definition Let / be a random function from {1,2,... , n} to {1,2,... , n} and let *и* e

{1,2,... *,n}.* Consider the sequence of points tto, *u, ..* . defined by *щ* = *u, u, =*

/(mj_ i ) for *i **>* 1. In terms of the functional graph of /, this sequence describes a path that connects to a cycle.

- (i) The number of edges in the path is called the
*tail length*of*u,*denoted A*(u).* - (ii) The number of edges in the cycle is called the
*cycle length*of*u,*denoted*p(u).* - (iii) The
*rho-lengtli*of*и*is the quantity*p(u) = X(u)*+*p(u).* - (iv) The
*tree size*of*и*is the number of edges in the maximal tree rooted on a cycle in the component that contains*u.* - (v) The
*component size*of*и*is the number of edges in the component that contains*u.* - (vi) The
*predecessors size*of*и*is the number of iterated preimages of*u.* - 2.36 Example The functional graph in Figure 2.1 has 2 components and 4 terminal points. The

point *и =* 3 has parameters A(u) = 1, *p(u)* = 4, *p(u) =* 5. The tree, component, and predecessors sizes of *и =* 3 are 4, 9, and 3, respectively. □

- 2.37 Fact As
*n*tends to infinity, the following are the expectations of some parameters associ- ated with a random point in {1,2,... , n} and a random function from*T*(i) tail length:_{n}*фrnj8*(ii) cycle length:*y/wn/8*(iii) rho-length:*yJmi/2*(iv) tree size:*nj*3 (v) component size: 2n/3 (vi) predecessors size:*^ттп/8.* - 2.38 Fact As n tends to infinity, the expectations of the maximum tail, cycle, and rho lengths in a random function from
*T*are ci_{n}*y/n, c*2*y/n,*and C3*y/n,*respectively, where c_{x}ss 0.78248, c_{2}и 1.73746, and c_{3}и 2.4149.

Facts 2.37 and 2.38 indicate that in the functional graph of a random function, most points are grouped together in one giant component, and there is a small number of large trees. Also, almost unavoidably, a cycle of length about *y/n* arises after following a path of length *y/n* edges.