Random mappings

2.31 Definition Let Tn 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 Tn are considered are called random mappings models. In this section the only random mappings model considered is where every function from Tn is equally likely to be chosen; such models arise frequently in cryptography and algorithmic number theory. Note that J-n | = n", whence the probability that a particular function from Tn is chosen is 1 /тгп.

  • 2.32 Definition Let / be a function in Tn with domain and codomain equal to {1.2,... , ?г}. The 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 Tn are true:
    • (i) The expected number of components is In ?г.
Afunctional graph (see Example 2.33)

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 Tn (i) tail length: фrnj8 (ii) cycle length: y/wn/8 (iii) rho-length: yJmi/2 (iv) tree size: nj3 (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 Tn are ci y/n, c2 y/n, and C3 y/n, respectively, where cx ss 0.78248, c2 и 1.73746, and c3 и 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.

< Prev   CONTENTS   Source   Next >