Ctrlk
For the complete documentation index, see llms.txt. This page is also available as Markdown.
ChatGPT

Chapter 9: Words and Mappings

Exercise 9.1

Imagine placing NN labeled balls and M−1M-1 distinct sticks in a row. The total number of arrangements is (N+M−1)!(N+M-1)!. Sticks are markers for urns. For example, |21||3 denotes a configuration where urns 0 and 2 are empty, urn 1 contains balls 2 and 1 (in this specific order) and urn 3 contains 3. Now, in our case both the balls and the sticks are indistinguishable. Therefore,

CMN=(N+M−1)!N!(M−1)!=(N+M−1M−1).C_{MN}=\frac{(N+M-1)!}{N!(M-1)!}=\binom{N+M-1}{M-1}.

The general framework is known as the stars and bars method.

Exercise 9.2

Exercise 9.3

Exercise 9.4

In the previous exercise, we’ve already seen an instance of this, when the number of balls and urns equals N=M=2N=M=2. It turns out, that it’s also the necessary and sufficient condition (assuming N,M≥1N,M\ge 1) for the average number of empty urns to equal the average minimum urn occupancy.

Let XX be the average number of empty urns and YY be the average minimum urn occupancy. Since the probability of any single urn being empty is (1−1M)N(1 - \frac{1}{M})^N, by linearity of expectation, the expected number of empty urns is

X=M(1−1M)N.X = M \left(1 - \frac{1}{M}\right)^N.

The average minimum occupancy can be computed using the tail sum formula of expectation

Y=∑k=1⌊N/M⌋Pr⁡{min⁡≥k}.Y = \sum_{k=1}^{\lfloor N/M \rfloor} \Pr\{\min \ge k\}.

We are looking for conditions where X=YX=Y.

If there are fewer balls than urns (N<MN<M), at least one urn must be empty. Consequently, X>0X>0 and Y=0Y=0, which means this situation cannot result in these quantities to be equal.

The case N=M  ⟹  ⌊N/M⌋=1N = M \implies \lfloor N/M \rfloor=1, so YY simplifies to just the probability that every urn has exactly 1 ball; it’s the number of favorable permutations over the total configurations Y=M!MMY = \frac{M!}{M^M}. This gives

X=Y  ⟹  M(1−1M)M=M!MM  ⟺  (M−1)M=(M−1)!  ⟹  M=2✓X = Y \implies M \left(1 - \frac{1}{M}\right)^M = \frac{M!}{M^M} \iff (M - 1)^M = (M - 1)! \implies M=2 \quad \checkmark

For any M≥3M \ge 3, the LHS definitely exceeds the RHS.

Finally, we must check the case N>MN>M. Here, the expected number of empty urns decays exponentially toward 0, while the expected minimum occupancy grows toward roughly N/MN/M. Because their trajectories are fundamentally different in the limit, they only intersect once. It can be shown that no integer solution exists for this intersection point, although the proof itself is out of scope of this manual.

Exercise 9.5

According to the estimate, it needs N∼2×365×ln⁡100≈58N \sim \sqrt {2 \times365\times\ln 100} \approx 58 people, which slightly overestimates the true answer N=57N=57 (acquired using a quick computer calculation).

Exercise 9.6 🌟

This exercise connects the expectation of the Ramanujan Q-function with the Rayleigh distribution. Furthermore, it presents a generalized formula to compute expectation of a random variable raised to nnth power.

The variance is defined as Var(X)=E[X2]−(E[X])2Var(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2. We already have the asymptotic expected value (the mean) from Theorem 9.1

E[X]∼πM2  ⟹  (E[X])2∼πM2. \mathbb{E}[X] \sim \sqrt{\frac{\pi M}{2}} \implies ( \mathbb{E}[X])^2 \sim \frac{\pi M}{2}.

The book A First Course in Probability by Sheldon Ross provides a handy formula to compute E[X2]\mathbb{E}[X^2]. Its generalized form is

E[Xn]=∫0∞nxn−1P(X>x)dx.\mathbb{E}[X^n] = \int_0^\infty n x^{n-1} P(X > x) dx.

Based on Theorem 4.4 (Ramanujan Q-distribution), the probability of having no collisions after xx throws can be estimated as

Pr⁡{X>x}∼e−x22M.\Pr\{X > x\} \sim e^{\frac{-x^2}{2M}}.

This gives

E[X2]∼∫0∞2xe−x22Mdx=∫0−∞−2Meudu=2M.\mathbb{E}[X^2] \sim \int_{0}^{\infty} 2x e^{\frac{-x^2}{2M}} dx=\int_{0}^{-\infty} -2M e^u du = 2M.

After plugging back the pieces into the variance formula we get

Var(X)=M(2−π2).\boxed{Var(X) = M \left(2 - \frac{\pi}{2}\right)}.

The standard deviation is

σ=Var(X)=M(2−π2)≈0.655M.\sigma = \sqrt{Var(X)} = \sqrt{M\left(2 - \frac{\pi}{2}\right)} \approx 0.655 \sqrt{M}.

Apparently, it scales at the exact same rate as the mean and the median. The limit distribution of X/MX/\sqrt{M} is the Rayleigh distribution, which is right‑skewed. In any such distribution the long right tail pulls the mean to the right of the median. Because the shape of the distribution does not change as MM grows—it simply stretches—the proportional difference between the mean and median remains constant. This is a fundamental property of the Rayleigh limit.

Exercise 9.7

P32(z)=6z21−z  ⟹  [zN]P32(z)=6 for N≥2,P33(z)=6z3(1−z)(1−2z)  ⟹  [zN]P33(z)=6(2N−2−1) for N≥3.P_{32}(z)=\frac{6z^2}{1-z} \implies [z^N]P_{32}(z)=6 \quad \text{ for $N\ge2$}, \\ P_{33}(z)=\frac{6z^3}{(1-z)(1-2z)} \implies [z^N]P_{33}(z)=6(2^{N-2}-1) \quad \text{ for $N\ge3$}.

The coefficients of z4z^4 give back the counts from the above list (6 and 18).

Exercise 9.8 🌟

This exercise gives a detailed application of partial fraction decomposition using the limit method.

We want to find

[zN]PMM(z/M)=[zN](zM(M−1)!∏k=1M−1(M−kz))=[zN−M](M−1)!∏k=1M−1(M−kz)⏟R(z).[z^N] P_{MM}(z/M) = [z^N] \left( z^M \frac{(M-1)!}{\prod_{k=1}^{M-1} (M - kz)} \right) = [z^{N-M}] \underbrace{\frac{(M-1)!}{\prod_{k=1}^{M-1} (M - kz)}}_{R(z)}.

The partial fraction decomposition gives the following structural form

R(z)=∑k=1M−1BkM−kz.R(z) = \sum_{k=1}^{M-1} \frac{B_k}{M - kz}.

Thankfully to the limit method, each BkB_k can be handled in a consistent and uniform manner

Bk=lim⁡z→M/k(M−kz)R(z)=(M−1)!∏i=1,i≠kM−1(M−iz)∣z=Mk.B_k = \lim_{z \to M/k} (M - kz) R(z) = \left. \frac{(M-1)!}{\prod_{i=1, i \neq k}^{M-1} (M - iz)} \right|_{z = \frac{M}{k}}.

Plugging in z=M/kz = M/k into the denominator, we get

∏i≠k(M−iMk)=(Mk)M−2∏i=1,i≠kM−1(k−i).\prod_{i \neq k} \left(M - i\frac{M}{k}\right) = \left(\frac{M}{k}\right)^{M-2} \prod_{i=1, i \neq k}^{M-1} (k - i).

Split the remaining product into positive and negative factorials

∏i=1,i≠kM−1(k−i)=(k−1)!(−1)M−1−k(M−1−k)!.\prod_{i=1, i \neq k}^{M-1} (k - i) = (k-1)! (-1)^{M-1-k} (M-1-k)!.

We now assemble BkB_k

Bk=(M−1)!(Mk)M−2(k−1)!(M−1−k)!(−1)M−1−k=k(M−1k)(kM)M−2(−1)M−1−k=M(M−1k)(kM)M−1(−1)M−1−k.\begin{align*} B_k &= \frac{(M-1)!}{\left(\frac{M}{k}\right)^{M-2} (k-1)! (M-1-k)! (-1)^{M-1-k}} \\ &= k \binom{M-1}{k} \left(\frac{k}{M}\right)^{M-2} (-1)^{M-1-k} \\ &= M \binom{M-1}{k} \left(\frac{k}{M}\right)^{M-1} (-1)^{M-1-k}. \end{align*}

Substitute BkB_k back into the sum for R(z)R(z). This gives

[zN−M]R(z)=∑k=1M−1[zN−M]BkM−kz=∑k=1M−1[zN−M]Bk/M1−kMz=∑k=1M−1BkM(kM)N−M=∑k=1M−1(M−1k)(kM)M−1(−1)M−1−k(kM)N−M=∑k=1M−1(M−1k)(−1)M−1−k(kM)N−1=∑j=0M−2(M−1j)(−1)j(1−j+1M)N−1(j=M−1−k)=∑0≤j<M(M−1j)(−1)j(1−j+1M)N−1.\begin{align*} [z^{N-M}] R(z) &= \sum_{k=1}^{M-1} [z^{N-M}] \frac{B_k}{M - kz} \\ &= \sum_{k=1}^{M-1} [z^{N-M}] \frac{B_k / M}{1 - \frac{k}{M}z} \\ &= \sum_{k=1}^{M-1} \frac{B_k}{M} \left(\frac{k}{M}\right)^{N-M} \\ &= \sum_{k=1}^{M-1} \binom{M-1}{k} \left(\frac{k}{M}\right)^{M-1} (-1)^{M-1-k} \left(\frac{k}{M}\right)^{N-M} \\ &= \sum_{k=1}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} \left(\frac{k}{M}\right)^{N-1} \\ &= \sum_{j=0}^{M-2} \binom{M-1}{j} (-1)^j \left(1 - \frac{j+1}{M}\right)^{N-1} && \text{($j = M - 1 - k$)}\\ &= \sum_{0 \le j < M} \binom{M-1}{j} (-1)^j \left(1 - \frac{j+1}{M}\right)^{N-1}. \end{align*}

Exercise 9.9 🌟

This exercise demonstrates the inclusion-exclusion principle in action.

Let AiA_i be the event that a specific coupon ii is missing from our collection after opening N−1N-1 boxes. Therefore,

Pr⁡{X≥N}=Pr⁡{A1∪A2∪⋯∪AM}.\Pr\{X \ge N\} = \Pr\{A_1 \cup A_2 \cup \dots \cup A_M\}.

By the inclusion-exclusion principle, we’ve

Pr⁡{Union}=∑Pr⁡{Ai}−∑Pr⁡{Ai∩Aj}+∑Pr⁡{Ai∩Aj∩Ak}−… .\Pr\{\text{Union}\} = \sum \Pr\{A_i\} - \sum \Pr\{A_i \cap A_j\} + \sum \Pr\{A_i \cap A_j \cap A_k\} - \dots.

The probability of missing a specific set of jj coupons is (1−jM)N−1\left(1 - \frac{j}{M}\right)^{N-1}. There are (Mj)\binom{M}{j} such combinations of size jj, and the sign alternates based on (−1)j−1(-1)^{j-1}. After assembling the final formula, we get an equation very similar to the one from the previous exercise

Pr⁡{X≥N}=∑j=1M(−1)j−1(Mj)(1−jM)N−1.\Pr\{X \ge N\} = \sum_{j=1}^{M} (-1)^{j-1} \binom{M}{j} \left(1 - \frac{j}{M}\right)^{N-1}.

Exercise 9.10

The text of this exercise is vague, assume that we need to find the EGF for M-surjections instead of surjections.

Let FM(z)=∑N≥0fNMzN/N!F_M(z)=\sum_{N\ge 0}f_{NM}z^N/N! be our EGF for MM-surjections, where fNMf_{NM} denotes the number of MM-surjections of length NN. The largest urn MM may contain 1≤k≤N−M+11 \le k \le N-M+1 balls. For any fixed kk, the number of ways to form MM-surjections of length NN is

(Nk)(M−1)!{N−kM−1}.\binom{N}{k}(M-1)!\left\{ \begin{matrix} N-k \\ M-1 \end{matrix} \right\}.

Now, we just need to sum over kk

fNM=∑k(Nk)(M−1)!{N−kM−1}=∑k(Nk)f(N−k)(M−1).f_{NM}=\sum_k \binom{N}{k}(M-1)!\left\{ \begin{matrix} N-k \\ M-1 \end{matrix} \right\}=\sum_k \binom{N}{k}f_{(N-k)(M-1)}.

The RHS is a binomial sum operation, so

FM(z)=(ez−1)FM−1(z),F_M(z)=(e^z-1)F_{M-1}(z),

with the initial condition of F0(z)=1F_0(z)=1. The multiplicative factor of ez−1e^z-1 is due to kk being a positive integer (starts at 1). Iterating the equation, we get FM(z)=(ez−1)MF_M(z)=(e^z-1)^M, as expected.

Exercise 9.11

The next exercise shows that

N![zN]FM(z)=∑j=0M(Mj)jN(−1)M−j.N![z^N]F_M(z)=\sum_{j=0}^M \binom{M}{j}j^N(-1)^{M-j} .

The Python script below uses this formula to decide whether to print out the M-surjection or not. Another possibility would be to temporarily store words as they’re being generated and abort the process if the list becomes larger than the threshold. Otherwise, print the content of the list at the end.

Exercise 9.12

Based on Exercise 9.8 we’ve

∑j=0M−1(M−1j)(−1)j(1−j+1M)N−1=M!MN{N−1M−1}.\sum_{j=0}^{M-1} \binom{M-1}{j} (-1)^j \left(1 - \frac{j+1}{M}\right)^{N-1} = \frac{M!}{M^N} \begin{Bmatrix} N-1 \\ M-1 \end{Bmatrix}.

Get a common denominator inside the power: (M−j−1M)N−1\left(\frac{M - j - 1}{M}\right)^{N-1}. Now, substitute the index k=M−1−jk = M - 1 - j to get

∑k=0M−1(M−1k)(−1)M−1−kkN−1MN−1=M⋅(M−1)!M⋅MN−1{N−1M−1},\sum_{k=0}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} \frac{k^{N-1}}{M^{N-1}} = \frac{M \cdot (M-1)!}{M \cdot M^{N-1}} \begin{Bmatrix} N-1 \\ M-1 \end{Bmatrix},

which simplifies to

∑k=0M−1(M−1k)(−1)M−1−kkN−1=(M−1)!{N−1M−1}.\sum_{k=0}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} k^{N-1} = (M-1)! \begin{Bmatrix} N-1 \\ M-1 \end{Bmatrix}.

Because N−1N-1 is just a placeholder for the number of items being partitioned, this identity holds for any generic exponent ii.

We begin with the LHS in our exercise (recall that N![zN]ejz=jNN![z^N]e^{jz}=j^N from Table 3.4)

∑j=0M(Mj)(−1)M−jjN=∑j=1M(Mj)(−1)M−jj⋅jN−1=M∑j=1M(M−1j−1)(−1)M−jjN−1(j(Mj)=M(M−1j−1))=M∑k=0M−1(M−1k)(−1)M−1−k(k+1)N−1(k=j−1)=M∑k=0M−1(M−1k)(−1)M−1−k[∑i=0N−1(N−1i)ki]=M∑i=0N−1(N−1i)[∑k=0M−1(M−1k)(−1)M−1−kki]=M∑i=0N−1(N−1i)(M−1)!{iM−1}(see above)=M!∑i=0N−1(N−1i){iM−1}=M!{NM}.\begin{align*} \sum_{j=0}^{M} \binom{M}{j} (-1)^{M-j} j^N &= \sum_{j=1}^{M} \binom{M}{j} (-1)^{M-j} j \cdot j^{N-1} \\[0.4cm] &= M \sum_{j=1}^{M} \binom{M-1}{j-1} (-1)^{M-j} j^{N-1} && \text{$\left( j \binom{M}{j} = M \binom{M-1}{j-1} \right)$} \\[0.4cm] &= M \sum_{k=0}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} (k+1)^{N-1} && \text{($k = j - 1$)} \\[0.4cm] &= M \sum_{k=0}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} \left[ \sum_{i=0}^{N-1} \binom{N-1}{i} k^i \right] \\[0.4cm] &= M \sum_{i=0}^{N-1} \binom{N-1}{i} \left[ \sum_{k=0}^{M-1} \binom{M-1}{k} (-1)^{M-1-k} k^i \right] \\[0.4cm] &= M \sum_{i=0}^{N-1} \binom{N-1}{i} (M-1)! \begin{Bmatrix} i \\ M-1 \end{Bmatrix} && \text{(see above)}\\[0.4cm] &= M! \sum_{i=0}^{N-1} \binom{N-1}{i} \begin{Bmatrix} i \\ M-1 \end{Bmatrix} \\[0.4cm] &= M! \begin{Bmatrix} N \\ M \end{Bmatrix}. \end{align*}

Exercise 9.13

The EGF immediately follows from Table 3.6, but we can easily derive it using the symbolic method. A partition of elements into indistinguishable nonempty groups (subsets) can be structurally defined as a set of nonempty sets of elements. This can be expressed as

F=SET(SET>0(Z))  ⟹  F(z)=eez−1.\mathcal{F}=\text{SET}(\text{SET}_{>0}(\mathcal{Z})) \implies F(z)=e^{e^z-1}.

Exercise 9.14

Wikipedia has the full proof.

Exercise 9.15

This directly follows from marking the inner sets by uu (see Exercise 9.13). Therefore,

F=SET(u×SET>0(Z))  ⟹  F(z,u)=eu(ez−1).\mathcal{F}=\text{SET}(u \times \text{SET}_{>0}(\mathcal{Z})) \implies F(z,u)=e^{u(e^z-1)}.

The coefficient uku^k represents partitions into exactly kk subsets. The size of those individual subsets is tracked by the zz variable.

Exercise 9.16

The book contains a typo. The correct recurrence is FNM=∑k=0N(Nk)F(N−k)(M−1)F_{NM} = \sum_{k=0}^{N} \binom{N}{k} F_{(N-k)(M-1)}.

Here, the functional equation is simpler than in Exercise 9.10 (with the same initial condition). This gives

FM(z)=ezFM−1(z).F_M(z) = e^z F_{M-1}(z).

Let uu mark the alphabet size MM, and let's construct F(z,u)=∑M≥0FM(z)uMF(z, u) = \sum_{M\ge0} F_M(z) u^M. We can establish the following relationship from the functional equation

∑M≥1FM(z)uM=∑M≥1ezFM−1(z)uM.\sum_{M\ge1} F_M(z) u^M = \sum_{M\ge1} e^z F_{M-1}(z) u^M.

This is equivalent to

F(z,u)−F0(z)=uez∑M≥1FM−1(z)uM−1.F(z, u) - F_0(z) = u e^z \sum_{M\ge1} F_{M-1}(z) u^{M-1}.

Now, we can derive the requested BGF

F(z,u)−1=uezF(z,u)  ⟹  F(z,u)=11−uez.F(z, u) - 1 = u e^z F(z, u) \implies \boxed{F(z, u) = \frac{1}{1 - u e^z}}.

Exercise 9.17

The EGF for MM-words with all letter frequencies even is (see Table 3.3 in the book)

(1+z2/2!+z4/4!+...+z2k/(2k)!+...)M=(ez+e−z)M2M.(1 + z^2/2! + z^4/4!+... + z^{2k}/(2k)! + ...)^M = \frac{(e^z+e^{-z})^M}{2^M}.

Exercise 9.18

The EGF for an urn requiring >k>k balls is ez−∑i=0kzii!e^z - \sum_{i=0}^k \frac{z^i}{i!}. The lowest order term in this series is zk+1(k+1)!\frac{z^{k+1}}{(k+1)!}. When we raise this EGF to the power of MM, the very first non-zero term is

FM,>k(z)=(zk+1(k+1)!)M+⋯=zM(k+1)((k+1)!)M+…F_{M,>k}(z)= \left( \frac{z^{k+1}}{(k+1)!} \right)^M + \dots = \frac{z^{M(k+1)}}{\left((k+1)!\right)^M} + \dots

This gives

(M(k+1))![zM(k+1)]FM,>k(z)=(M(k+1))!((k+1)!)M.(M(k+1))! [z^{M(k+1)}] F_{M,>k}(z) =\boxed{ \frac{(M(k+1))!}{\left((k+1)!\right)^M}}.

Using Theorem 9.3, the EGF for an urn with <(k+2)<(k+2) balls is ∑i=0k+1zii!\sum_{i=0}^{k+1} \frac{z^i}{i!}. We want to extract the coefficient for M(k+1)−1M(k+1) - 1 from this EGF raised to the power of MM. To build zM(k+1)−1z^{M(k+1)-1} from the product of MM polynomials (where the max term is zk+1z^{k+1}), we are forced to pick the zk+1/(k+1)!z^{k+1}/(k+1)! term exactly M−1M-1 times and the zk/k!z^k/k! term exactly once. There are MM ways to choose which of the MM polynomials contributes the zkz^k term. Therefore, the extracted coefficient multiplied by (M(k+1)−1)!(M(k+1) - 1)! and MM is

(M(k+1)−1)!(M×1k!((k+1)!)M−1)=M(k+1)×(M(k+1)−1)!(k+1)×k!((k+1)!)M−1=(M(k+1))!((k+1)!)M.(M(k+1)-1)! \left( M \times \frac{1}{k! \left((k+1)!\right)^{M-1}} \right)=\frac{M(k+1) \times (M(k+1) - 1)!}{(k+1) \times k! \left((k+1)!\right)^{M-1}}= \boxed{\frac{(M(k+1))!}{\left((k+1)!\right)^M}}.

Exercise 9.19 🌟

This exercise builds upon the analysis of the birthday paradox and showcases an interesting fact about collisions in hash tables.

The text of this exercise asks us to derive a formula for NN urns, but we’ll denote the number of urns with MM to retain consistency.

Let XX be the number of balls thrown until the second collision occurs. The expected value can be computed using the tail sum formula

E[X]=∑kPr⁡{X>k}.\mathbb{E}[X]=\sum_k \Pr\{X>k\}.

Theorem 9.1 speaks in terms of UNTIL condition, whilst this exercise mentions BEFORE. Asymptotically there is no difference, but in discrete terms we have E[Before]=E[Until]−1\mathbb{E}[\text{Before}] = \mathbb{E}[\text{Until}] - 1.

The probability that there are no collisions when NN balls are thrown into MM urns is given by Theorem 9.1. Therefore,

Pr⁡0{X>N}=(MN)N!MN.\Pr_0\{X>N\} = \binom{M}{N}\frac{N!}{M^N}.

If exactly 1 collision occurred in NN throws, it means exactly N−1N-1 distinct urns are occupied. One urn contains exactly 2 balls, and the other N−2N-2 urns contain exactly 1 ball. Thus,

Pr⁡1{X>N}=(MN−1)(N−1)!(NN−2)MN.\Pr_1\{X>N\}=\frac{\dbinom{M}{N-1}(N-1)!\dbinom{N}{N-2}}{M^N}.

This gives

E[X]=∑k(Pr⁡0{X>k}+Pr⁡1{X>k}).\mathbb{E}[X]=\sum_k( \Pr_0\{X>k\} + \Pr_1\{X>k\}).

The first sum is (see Theorem 9.1) ∼πM2\sim \sqrt{\frac{\pi M}{2}}. To solve the second sum, let's rewrite it

Pr⁡1{X>k}=k(k−1)2M⋅M!(M−(k−1))!Mk−1=k(k−1)2MPr⁡0{X>k−1}.\Pr_1\{X>k\}=\frac{k(k-1)}{2M} \cdot \frac{M!}{(M-(k-1))! M^{k-1}} = \frac{k(k-1)}{2M} \Pr_0\{X>k-1\}.

Now, we proceed similarly as in Exercise 9.6

∑kPr⁡1{X>k}∼∫0∞x22Me−x22Mdx=12πM2.\sum_k \Pr_1\{X>k\} \sim \int_{0}^{\infty} \frac{x^2}{2M} e^{\frac{-x^2}{2M}} dx=\frac{1}{2} \sqrt{\frac{\pi M}{2}}.

The integral is listed as of similar form of the standard Gaussian integral on Wikipedia.

The total expected time until the second collision is the sum of both parts ∼32πM2\sim \frac{3}{2} \sqrt{\frac{\pi M}{2}}. It tells us that asymptotically, getting the second collision takes roughly 50% longer than getting the first one.

Exercise 9.20

The text of this exercise asks us to derive a formula for NN urns, but we’ll denote the number of urns with MM to retain consistency.

We can repeat more or less the same math as in the previous exercise to conclude that the leading asymptotic term remains intact. Instead, let’s argue in a different way. At the time the first collision happens, we have thrown ∼M\sim \sqrt{M} balls. At this exact moment, the board looks like this:

  • Exactly 1 urn has 2 balls.

  • Roughly M\sqrt{M} urns have exactly 1 ball.

The probability that the next thrown ball hits the single urn that already has 2 balls is 1/M1/M. The probability it hits one of the urns with 1 ball (triggering our new definition of a collision) is roughly MM=1M\frac{\sqrt{M}}{M} = \frac{1}{\sqrt{M}}. Because 1M\frac{1}{\sqrt{M}} is massively larger than 1M\frac{1}{M} as M→∞M \to \infty, it’s overwhelmingly statistically likely that the "next" collision will hit a 1-ball urn rather than the 2-ball urn. The events we’re trying to ignore (balls falling into urns with more than 2 balls) are so extremely rare, at this stage of the process, that they don’t affect the leading asymptotic term!

Exercise 9.21 🌟

This exercise demonstrates the multinomial theorem in action.

The book already defines for us the EGF for words comprising at most kk occurrences of each of MM different letters. Here, we have k=2k=2

FM(z)=(1+z+z22)M.F_M(z)= \left( 1 + z + \frac{z^2}{2} \right)^M.

We need to find the explicit expression for the number of words, which is N![zN]FM(z)N![z^N]F_M(z). Using the multinomial expansion, the EGF is

FM(z)=∑k0+k1+k2=MM!k0!k1!k2!(1)k0(z)k1(z22)k2.F_M(z) = \sum_{k_0 + k_1 + k_2 = M} \frac{M!}{k_0! k_1! k_2!} (1)^{k_0} (z)^{k_1} \left(\frac{z^2}{2}\right)^{k_2}.

Substitute k1=N−2k2k_1 = N - 2k_2, which also forces k0=M−N+k2k_0 = M - N + k_2. This gives

FM(z)=∑kM!(M−N+k)!(N−2k)!k!zN2k∴N![zN]FM(z)=N!∑kM!(M−N+k)!(N−2k)!k!12k=∑k=0⌊N/2⌋(MN−k)(N−kk)N!2k.F_M(z) = \sum_{k} \frac{M!}{(M - N + k)! (N - 2k)! k!} \frac{z^N}{2^k} \\[0.4cm] \therefore N![z^N]F_M(z) = N! \sum_{k} \frac{M!}{(M - N + k)! (N - 2k)! k!} \frac{1}{2^k}=\sum_{k=0}^{\lfloor N/2 \rfloor} \boxed{\binom{M}{N-k} \binom{N-k}{k} \frac{N!}{2^k}}.

Let kk be the number of letters that appear exactly twice. We can pick N−kN-k distinct letters in (MN−k)\binom{M}{N-k} ways from an alphabet of size MM. Among these, we can select (N−kk)\binom{N-k}{k} to be duplicates. Finally, there are N!/2kN!/2^k ways to reorder them. Summing over all kk gives our explicit formula.

Exercise 9.22

This is a variation of the previous exercise with M=365M=365. The probability of not having a triplet is

N!365N[zN](1+z+z22)365.\frac{N!}{365^N} [z^N] \left( 1 + z + \frac{z^2}{2} \right)^{365}.

We can computationally evaluate this exact coefficient extraction to build the curve shown below.

Exercise 9.23

The plot from the previous exercise already gives the answer for three people. The explicit formula for the probability of not having a four-person shared birthday is

N!365N[zN](1+z+z22!+z33!)365.\frac{N!}{365^N} [z^N] \left( 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} \right)^{365}.

It turns out, that crossing the 50% threshold for four people with shared birthday happens at N=187N = 187.

Exercise 9.24 🌟

This exercise introduces the double dixie cup problem.

Let XX be the number of balls thrown until every urn has at least 2 balls. The event X≤NX \le N means that after exactly NN throws, all MM urns contain at least two balls. Theorem 9.4 from the book immediately gives

Pr⁡{X≤N}=N!MN[zN](ez−1−z)M.\Pr\{X \le N\} = \frac{N!}{M^N} [z^N] (e^z - 1 - z)^M.

Therefore, the average number of balls thrown into MM urns before each urn is filled at least twice is

E[X]=∑N≥0(1−N!MN[zN](ez−1−z)M)=Mln⁡M+Mln⁡ln⁡M+O(M).\mathbb{E}[X] = \sum_{N\ge0} \left( 1 - \frac{N!}{M^N} [z^N] (e^z - 1 - z)^M \right) = M \ln M + M \ln \ln M + O(M).

Intuitively, we might think that filling every urn with at least 2 balls takes x2 times as much as filling them with 1 ball. But this is obviously not the case. By the time we finally fill the last empty urn, all the others already contain more than one ball. Filling them a second time requires barely any extra effort.

Exercise 9.25 🌟

This model is the direct "dual" to the double dixie cup work (see the previous exercise). While the dixie cup problem looks at the expected time NN to reach a certain occupancy, this model looks at the expected occupancy for a fixed time.

Let XX be the random variable representing the minimal occupancy (the number of balls in the least-filled urn) when distributing NN balls into MM urns. Theorem 9.4 gives

E[X]=∑k≥1P(X≥k)=1MN∑k≥1N![zN](ez−∑j=0k−1zjj!)M.\mathbb{E}[X] = \sum_{k\ge1} P(X \ge k) = \frac{1}{M^N} \sum_{k\ge1} N! [z^N] \left( e^z - \sum_{j=0}^{k-1} \frac{z^j}{j!} \right)^M.

If we multiply the average value with the total number of combinatorial objects, then we get the CGF

CM(z)=∑k=1∞(ez−∑j=0k−1zjj!)M.C_M(z) = \sum_{k=1}^{\infty} \left( e^z - \sum_{j=0}^{k-1} \frac{z^j}{j!} \right)^M.

The following Python code tabulates the values for M and N less than 20. The function count_valid_distributions uses dynamic programming and recurrence from Exercise 9.16 to maintain required precision and accuracy.

Exercise 9.26 🌟

This exercise highlights the utility of indicator random variables in solving combinatorial problems (see also the next exercise). They can also give an idea how to formally describe the corresponding combinatorial class using the symbolic method.

This problem can be easily solved using indicator random variables IiI_i for each position in the word

Ii={1if a block starts at position i,0if the block continues the previous letter.I_i= \begin{cases} 1 &\text{if a block starts at position } i, \\ 0 &\text{if the block continues the previous letter}. \end{cases}

We know that E[I1]=Pr⁡{I1=1}=1\mathbb{E}[I_1]=\Pr\{I_1=1\}=1, since the first block is always new. For the other blocks

E[Ii]=Pr⁡{Ii=1}=M−1M,\mathbb{E}[I_i] = \Pr\{I_i = 1\} = \frac{M-1}{M},

as M−1M-1 different characters may be at the previous position. If the current letter is different, then it starts a new block. The total number of blocks in the entire word is X=∑iIiX=\sum_i I_i. The average number of blocks of contiguous equal elements in a random word is

E[X]=E[I1]+∑i=2NE[Ii]=1+(N−1)(M−1M).\mathbb{E}[X] = \mathbb{E}[I_1] + \sum_{i=2}^{N} \mathbb{E}[I_i] = 1 + (N-1) \left( \frac{M-1}{M} \right).

As a quick sanity check, the predicted average for Table 9.2 in the book is 3, which perfectly matches the data.

Modeling via BGF

For the sake of completeness, let’s develop the BGF for this problem using the symbolic method. The average can be computed by using Table 3.5 from the book (we already know the answer).

B=SEQ(Z)−ϵF=ϵ+uMB⏟first block×SEQ(u(M−1)B⏟other block).\mathcal{B}=\text{SEQ}(\mathcal{Z})-\epsilon \\[0.2cm] \mathcal{F}=\epsilon+\underbrace{uM\mathcal{B}}_{\text{first block}} \times \text{SEQ}(\underbrace{\mathcal{u(M-1)B}}_{\text{other block}}).

Observe, that we mark blocks (nonempty contiguous equal elements). We’ve MM choices for the first block and M−1M-1 for all subsequent ones. The BGF immediately follows from the corresponding transfer theorem

F(z,u)=1+Muz1−z1−(M−1)uz1−z=1+Muz1−z−(M−1)uz.F(z, u) = 1 + \frac{ M \dfrac{uz}{1-z} }{ 1 - (M-1) \dfrac{uz}{1-z} }= \boxed{1 + \frac{M u z}{1 - z - (M-1) u z}}.

Exercise 9.27

Let's look at any adjacent pair of letters wiw_i and wi+1w_{i+1} from an MM-letter alphabet. Since the word is completely random, there are M2M^2 possible pairs for these two positions. We can partition them into three categories:

  1. wi<wi+1w_i < w_{i+1} (rise)

  2. wi>wi+1w_i > w_{i+1} (fall)

  3. wi=wi+1w_i = w_{i+1} (flat continuation)

Because of symmetry, the number of rising pairs exactly equals the number of falling pairs. Specifically, out of the M2M^2 pairs, exactly MM of them are flat (the two letters are the same). The remaining M2−MM^2 - M pairs are evenly split between rises and falls. Therefore, the number of rising/falling pairs is M2−M2=(M2)\frac{M^2 - M}{2} = \binom{M}{2}.

The probability of a rise at any specific position ii is

Pr⁡{Risei}=M2−M2M2=M−12M.\Pr\{\text{Rise}_i\} = \frac{\frac{M^2 - M}{2}}{M^2} = \frac{M-1}{2M}.

There are N−1N-1 adjacent pairs in a word of length NN. Let IiI_i be an indicator random variable that equals 1 if a rise occurs at position ii. By the linearity of expectation and symmetry

E[Falls]=E[Rises]=∑i=1N−1E[Ii]=∑i=1N−1Pr⁡{Risei}=(N−1)(M−12M).\mathbb{E}[\text{Falls}]=\mathbb{E}[\text{Rises}] = \sum_{i=1}^{N-1}\mathbb{E}[I_i] = \sum_{i=1}^{N-1} \Pr\{\text{Rise}_i\}= (N-1) \left( \frac{M-1}{2M} \right).

A run is a maximal contiguous subsequence of elements. We’ve to be careful about whether a run is strictly increasing or non-decreasing. Let’s use the latter. The first letter always starts a fresh run. A new run starts at position i+1i+1 if and only if wi>wi+1w_i > w_{i+1} (a fall). The expected number of non-decreasing runs is

E[Runs]=E[Falls]+1=1+(N−1)(M−12M).\mathbb{E}[\text{Runs}] = \mathbb{E}[\text{Falls}]+1=1 + (N-1) \left( \frac{M-1}{2M} \right).

This definition is aligned with the similar property of runs and falls for permutations, as explained in the book.

Exercise 9.28

The probability is 100×100−100=100−99100 \times100^{-100}=100^{-99}. We can sum the individual probabilities, as the events for different urns are mutually exclusive (only one urn can possibly hold all balls).

Exercise 9.29

The probability is 100!×100−100100! \times 100^{-100}, since we have 100! possible mappings of balls to urns.

Exercise 9.30

Since we are tracking empty urns, we set k=0k=0. Substituting this into the EBGF from the book (see the subsection about alternative derivations), we get

F(z,u)=(ez+u−1)M.F(z,u) = \left( e^z + u - 1 \right)^M.

Let UU be the number of empty urns. We get

E[U]=M(1−1/M)N.\mathbb{E}[U] = M(1 - 1/M)^N.

The second derivative of FF evaluated at u=1u=1 is

∂2F∂u2∣u=1=M(M−1)e(M−2)z.\left. \frac{\partial^2 F}{\partial u^2} \right|_{u=1} = M(M-1)e^{(M-2)z}.

The total cumulated cost of pairs of empty urns is

N![zN]M(M−1)e(M−2)z=M(M−1)(M−2)N.N! [z^N] M(M-1)e^{(M-2)z} = M(M-1)(M-2)^N.

Using Table 3.5 from the book, we are ready to plug in all parts into the variance formula

Var(U)=M(M−1)(1−2M)N+M(1−1M)N−M2(1−1M)2N.\text{Var}(U) = M(M-1)\left(1 - \frac{2}{M}\right)^N + M\left(1 - \frac{1}{M}\right)^N - M^2\left(1 - \frac{1}{M}\right)^{2N}.

Using ln⁡(1−x)∼−x−x2/2\ln(1-x) \sim -x - x^2/2, let's expand the terms for N/M=α>0N/M=\alpha >0 fixed as N,M→∞N,M \to \infty.

(1−2M)αM∼exp⁡(αM(−2M−2M2))=exp⁡(−2α−2αM)∼e−2α(1−2αM).\left(1 - \frac{2}{M}\right)^{\alpha M} \sim \exp\left( \alpha M \left( -\frac{2}{M} - \frac{2}{M^2} \right) \right) = \exp\left( -2\alpha - \frac{2\alpha}{M} \right) \sim e^{-2\alpha}\left(1 - \frac{2\alpha}{M}\right).

Therefore,

M(M−1)e−2α(1−2αM)≈M2e−2α−2αMe−2α−Me−2α.M(M-1) e^{-2\alpha} \left(1 - \frac{2\alpha}{M}\right) \approx M^2 e^{-2\alpha} - 2\alpha M e^{-2\alpha} - M e^{-2\alpha}.

The quadratic expectation term is

(1−1M)2αM∼exp⁡(2αM(−1M−12M2))=exp⁡(−2α−αM)∼e−2α(1−αM).\left(1 - \frac{1}{M}\right)^{2\alpha M} \sim \exp\left( 2\alpha M \left( -\frac{1}{M} - \frac{1}{2M^2} \right) \right) = \exp\left( -2\alpha - \frac{\alpha}{M} \right) \sim e^{-2\alpha}\left(1 - \frac{\alpha}{M}\right).

The book already provides E[U]\mathbb{E}[U], thus,

(E[U])2∼M2e−2α−αMe−2α.(\mathbb{E}[U])^2 \sim M^2 e^{-2\alpha} - \alpha M e^{-2\alpha}.

Put all three expanded pieces back into the variance formula

Var(U)∼[M2e−2α−2αMe−2α−Me−2α]+[Me−α]−[M2e−2α−αMe−2α]=Me−α(1−(1+α)e−α).\text{Var}(U) \sim \left[ M^2 e^{-2\alpha} - 2\alpha M e^{-2\alpha} - M e^{-2\alpha} \right] + \left[ M e^{-\alpha} \right] - \left[ M^2 e^{-2\alpha} - \alpha M e^{-2\alpha} \right]= M e^{-\alpha} \left( 1 - (1+\alpha)e^{-\alpha} \right).

Thus, the standard deviation is

σU∼M⋅e−α(1−(1+α)e−α). \sigma_U \sim \sqrt{M} \cdot \sqrt{e^{-\alpha}\bigl(1 - (1+\alpha)e^{-\alpha}\bigr)}.

Exercise 9.31 🌟

This exercise counterbalances the approach with indicator random variables; it showcases why EGFs are so incredibly powerful. Trying to solve this with discrete indicator variables or inclusion-exclusion principle would be a combinatorial nightmare.

The EGF for a single urn is (see Table 3.3 in the book)

Ueven(z)=∑k≥0z2k(2k)!=ez+e−z2.U_{\text{even}}(z) = \sum_{k\ge0} \frac{z^{2k}}{(2k)!} = \frac{e^z + e^{-z}}{2}.

The EGF for MM urns is simply an MM-sequence of the above EGF

F(z)=(ez+e−z2)M=12M∑j=0M(Mj)e(2j−M)z.F(z) = \left( \frac{e^z + e^{-z}}{2} \right)^M= \frac{1}{2^M} \sum_{j=0}^{M} \binom{M}{j} e^{(2j-M)z}.

The total number of valid distributions is

N![zN]F(z)=12M∑j=0M(Mj)(2j−M)N.N![z^N]F(z) = \frac{1}{2^M} \sum_{j=0}^{M} \binom{M}{j} (2j-M)^N.

Therefore, the probability that each urn will contain an even number of balls when NN balls are distributed among MM urns is

Pr⁡{All Even}=12MMN∑j=0M(Mj)(2j−M)N.\Pr\{\text{All Even}\} = \frac{1}{2^M M^N} \sum_{j=0}^{M} \binom{M}{j} (2j-M)^N.

Quick Sanity Check of our Formula

If NN is odd, then it’s impossible to divide an odd number of balls into a sum of strictly even numbers. So, the probability must be exactly 0. Interestingly, this is handled for us automatically by the EGF machinery. The binomial coefficient is symmetric, so (Mj)=(MM−j)\binom{M}{j} = \binom{M}{M-j}. Let’s see what do we get by summing such symmetric entries (for NN odd, (−x)N=−xN(-x)^N=-x^N)

(2j−M)N↔(2(M−j)−M)N=(M−2j)N=−(2j−M)N.(2j-M)^N \leftrightarrow (2(M-j)-M)^N = (M-2j)^N = -(2j-M)^N.

They annihilate each other, hence the total sum is zero. When MM is even, we also have one singular term for j=M/2j=M/2, but this trivially evaluates to zero.

Exercise 9.32

CNk[M]C^{[M]}_{Nk} represents the total number of MM-words of length NN such that a specific letter occurs exactly kk times. Assume N≥kN\ge k. The base case is C00[M]=1C^{[M]}_{00}=1. The recurrence relationship follows from the following observations:

  • We can select M−1M-1 different letters for expanding the MM-words of length N−1N-1 already containing kk occurrences of a specific letter.

  • We can append a letter to MM-words of length N−1N-1 containing k−1k-1 occurrences of that letter.

The Python script below computes these values.

Exercise 9.33

We need to use Theorems 6.6 (see also Exercise 6.37) and 9.6 from the book.

As the official errata points out, the formulae in Theorem 9.6 are different than those given in Table 9.9. Therefore, the results below eesentially illustrate the methodology, which is the most important part of the whole story.

In case of an unsuccessful search, we have:

  • For N=1000N=1000 we want 1000/M≤2H1001−2  ⟹  M≥781000/M \le 2H_{1001}-2 \implies M \ge 78.

  • For N=106N=10^6 we want 106/M≤2H106+1−2  ⟹  M≥3733410^6/M \le 2H_{10^6+1}-2\implies M \ge 37334.

In case of a successful search, we have:

  • For N=1000N=1000 we want 999/(2M)≤2H1000−3+2H1000/1000  ⟹  M≥42999/(2M) \le 2H_{1000}-3+ 2H_{1000}/1000 \implies M \ge 42.

  • For N=106N=10^6 we want (106−1)/(2M)≤2H106−3+2H106/106  ⟹  M≥19391(10^6-1)/(2M) \le 2H_{10^6}-3+ 2H_{10^6}/10^6 \implies M \ge 19391.

In essence, the analysis highlights the general relationship: to beat a binary search tree of size NN, we need a hash table of size M=Ω(Nln⁡N)M=\Omega(\frac{N}{\ln N}).

Exercise 9.34 🌟

This exercise introduces a powerful concept in probability theory called the law of total variance.

Let SS be the random variable representing the number of comparisons (probes) for a successful search. Imagine we pick one of the NN keys in the table uniformly at random. We want to find the search cost for this specific key. Let XX be the number of other keys that hashed into the exact same list as our target key. Since each of the remaining N−1N-1 keys had an independent p=1/Mp=1/M chance of landing in this list, XX perfectly follows a binomial distribution. From this, we know the mean and variance of XX:

  • E[X]=(N−1)p\mathbb{E}[X] = (N-1)p

  • Var(X)=(N−1)p(1−p)\text{Var}(X) = (N-1)p(1-p)

If there are XX other keys in the list, the total length of the chain is X+1X+1. Because our target key is equally likely to have been inserted at any position in this chain, the search cost SS given XX is uniformly distributed on the integers {1,2,…,X+1}\{1, 2, \dots, X+1\}. For a discrete uniform distribution on 1,…,n{1, \dots, n}, the mean is n+12\frac{n+1}{2} and the variance is n2−112\frac{n^2-1}{12}. Substituting n=X+1n = X+1, we get our conditional moments:

  • E[S∣X]=X+22=1+X2\mathbb{E}[S \mid X] = \frac{X+2}{2} = 1 + \frac{X}{2}

  • Var(S∣X)=(X+1)2−112=X2+2X12\text{Var}(S \mid X) = \frac{(X+1)^2 - 1}{12} = \frac{X^2 + 2X}{12}

According to the law of total variance, we have

Var(S)=E[Var(S∣X)]+Var(E[S∣X]).\text{Var}(S) = \mathbb{E}[\text{Var}(S \mid X)] + \text{Var}(\mathbb{E}[S \mid X]).

Let’s compute the pieces

Var(E[S∣X])=Var(1+X2)=14Var(X)=(N−1)p(1−p)4(Var(αX)=α2Var(X)),E[Var(S∣X)]=E[X2+2X12]=112(E[X2]+2E[X])=112((N−1)p(1−p)+(N−1)2p2+2(N−1)p)(E[X2]=Var(X)+(E[X])2).\begin{align*} \text{Var}( \mathbb{E}[S \mid X]) &= \text{Var}\left(1 + \frac{X}{2}\right) = \frac{1}{4}\text{Var}(X) = \frac{(N-1)p(1-p)}{4} && \text{($ \text{Var}(\alpha X)=\alpha^2\text{Var}(X)$)}, \\[0.5cm] \hline \\ \mathbb{E}[\text{Var}(S \mid X)] &= \mathbb{E}\left[ \frac{X^2 + 2X}{12} \right] \\ &= \frac{1}{12} \left( \mathbb{E}[X^2] + 2\mathbb{E}[X] \right) \\ &= \frac{1}{12} \Big( (N-1)p(1-p) + (N-1)^2p^2 + 2(N-1)p \Big) && \text{($\mathbb{E}[X^2] = \text{Var}(X) + (\mathbb{E}[X])^2$)}. \end{align*}

Adding them together and simplifying, we get

Var(S)=12(N−1)p−13(N−1)p2+112(N−1)2p2=N−12M+(N−1)(N−4)12M2.\text{Var}(S) = \frac{1}{2}(N-1)p - \frac{1}{3}(N-1)p^2 + \frac{1}{12}(N-1)^2 p^2= \frac{N-1}{2M} + \frac{(N-1)(N-4)}{12M^2}.

This gives the standard deviation of the number of comparisons required for a successful search in hashing with separate chaining

σS=N−12M−N−13M2+(N−1)212M2≈α2+α212(with a load factor α=N/M).\sigma_S = \sqrt{ \frac{N-1}{2M} - \frac{N-1}{3M^2} + \frac{(N-1)^2}{12M^2} } \approx \sqrt{ \frac{\alpha}{2} + \frac{\alpha^2}{12} } \qquad \text{(with a load factor $\alpha = N/M$)}.

Exercise 9.35 🌟

This exercise is a case study how to analyze optimization techniques, like in this case, keeping the chains sorted. Without developing a mathematical model, we may never be sure do we have a good or bad idea.

Sorting the lists does absolutely nothing to improve the average cost of a successful search! If a key is actually in the table, we still have to traverse the list until we find it. Because its rank among the keys in that list (chain) is perfectly uniform, we’ll search exactly as far on average as we would in an unsorted list. Therefore, keeping the chains sorted is a mechanism specifically designed to optimize unsuccessful searches.

Let XX be the number of keys that hashed into the exact same list as our search key. Let PP be the number of comparisons (probes) we make. The conditional average is

E[P∣X]=1X+1((∑i=1Xi)+X)=X2+1−1X+1.\mathbb{E}[P \mid X] = \frac{1}{X+1} \left( \left(\sum_{i=1}^X i\right) + \bold{X} \right) = \frac{X}{2} + 1 - \frac{1}{X+1}.

The bolded XX in the above formula represents the case of hitting the end of the list.

To find the unconditional average E[P]\mathbb{E}[P], we use the fact that the number of keys in any list perfectly follows a Poisson distribution in the asymptotic limit N,M→∞N, M \to \infty with α=Np=N/M\alpha=Np=N/M:

lim⁡N,M→∞Binomial(N,p=1/M)=Poisson(α).\lim_{N, M \to \infty} \text{Binomial}(N, p=1/M) = \text{Poisson}(\alpha).

Shifting to a Poisson distribution drastically simplifies the calculus without impacting the asymptotic conclusions. For example, E[1X+1]=∑k1k+1αke−αk!=∑kαke−α(k+1)!=e−αα∑kαk+1(k+1)!=e−αα(eα−1)=1−e−ααE\left[\frac{1}{X+1}\right] = \sum_{k} \frac{1}{k+1} \frac{\alpha^k e^{-\alpha}}{k!} = \sum_{k} \frac{\alpha^k e^{-\alpha}}{(k+1)!}= \frac{e^{-\alpha}}{\alpha} \sum_{k} \frac{\alpha^{k+1}}{(k+1)!}= \frac{e^{-\alpha}}{\alpha} (e^\alpha - 1) = \mathbf{\frac{1 - e^{-\alpha}}{\alpha}}. Computing this expectation whilst sticking to the exact binomial distribution would be a nightmare.

According to the law of total expectation, we have

E[P]=E[E[P∣X]]=E[X]2+1−E[1X+1]=α2+1−1−e−αα≈α2.\mathbb{E}[P] =\mathbb{E}[\mathbb{E}[P \mid X]]= \frac{\mathbb{E}[X]}{2} + 1 - \mathbb{E}\left[\frac{1}{X+1}\right]= \frac{\alpha}{2} + 1 - \frac{1 - e^{-\alpha}}{\alpha} \approx \frac{\alpha}{2}.

Obviously, sorting cuts, on the average, the search time by half. Of course, this must be balanced with the cost of maintaining the chain sorted. In practice, this almost never worths the effort.

We also need

E[P2∣X]=1X+1((∑i=1Xi2)+X2)=1X+1(X(X+1)(2X+1)6+X2)=X23+7X6−1+1X+1.\mathbb{E}[P^2 \mid X] = \frac{1}{X+1} \left( \left(\sum_{i=1}^X i^2\right) + X^2 \right) = \frac{1}{X+1} \left( \frac{X(X+1)(2X+1)}{6} + X^2 \right) = \frac{X^2}{3} + \frac{7X}{6} - 1 + \frac{1}{X+1}.

This gives (we know that E[X]=Var(X)=α\mathbb{E}[X]=\text{Var}(X)=\alpha)

E[P2]=E[E[P2∣X]]=α2+α3+7α6−1+1−e−αα=α23+3α2−1+1−e−αα.\mathbb{E}[P^2] =\mathbb{E}[\mathbb{E}[P^2 \mid X]]= \frac{\alpha^2 + \alpha}{3} + \frac{7\alpha}{6} - 1 + \frac{1 - e^{-\alpha}}{\alpha} = \frac{\alpha^2}{3} + \frac{3\alpha}{2} - 1 + \frac{1 - e^{-\alpha}}{\alpha}.

Now, we can compute the standard deviation as Var(P)=E[P2]−(E[P])2\sqrt {\text{Var}(P) }= \sqrt{\mathbb{E}[P^2] - (\mathbb{E}[P])^2}

σP=α212+α2−2+(α+3)(1−e−αα)−(1−e−αα)2≈α212+α2.\sigma_P = \sqrt{\frac{\alpha^2}{12} + \frac{\alpha}{2} - 2 + (\alpha + 3)\left(\frac{1 - e^{-\alpha}}{\alpha}\right) - \left(\frac{1 - e^{-\alpha}}{\alpha}\right)^2} \approx \sqrt{\frac{\alpha^2}{12} + \frac{\alpha}{2}}.

Exercise 9.36

In the section about the expected maximum occupancy of urns, the book claims that the length of the longest list when Program 9.1 is used will be ∼ln⁡N/ln⁡ln⁡N\sim \ln N/\ln \ln N, on the average. If we compute two hash functions and put the key on the shorter of the two lists, then the longest list drops to O(ln⁡ln⁡N)\mathcal{O}(\ln \ln N), on the average, with high probability. The details are given in the paper Balanced Allocations.

Exercise 9.37

The Cayley function is defined as C(z)=zeC(z)C(z) = z e^{C(z)} (see Theorem 6.14 in the book). We’ve to extract a coefficient from a function composed with an implicitly defined generating function. Therefore, we need to use the 3rd case of the Lagrange inversion theorem with g(u)=eαug(u)=e^{\alpha u} and f(u)=u/euf(u)=u/e^u. This gives

[zn]eαC(z)=1n[un−1]αeαuenu=αn[un−1]e(α+n)u=α(α+n)n−1n!.\begin{align*} [z^n] e^{\alpha C(z)} &= \frac{1}{n} [u^{n-1}] \alpha e^{\alpha u} e^{nu} \\[0.3cm] &= \frac{\alpha}{n} [u^{n-1}] e^{(\alpha + n)u} \\[0.3cm] &= \frac{\alpha (\alpha + n)^{n-1}}{n!}. \end{align*}

Exercise 9.38 🌟

This exercise introduces Abel’s binomial theorem and shows how GFs help in proving seemingly daunting identities.

The LHS follows from the previous exercise

[zn]e(α+β)C(z)=(α+β)(n+α+β)n−1n!.[z^n]e^{(\alpha + \beta)C(z)} = \frac{(\alpha + \beta)(n + \alpha + \beta)^{n-1}}{n!}.

The RHS is a classical convolution of GFs, where we also reuse the result from the previous exercise. We’ve

[zn](eαC(z)eβC(z))=∑k=0n([zk]eαC(z))([zn−k]eβC(z))=∑k=0nα(k+α)k−1k!β(n−k+β)n−k−1(n−k)!.[z^n]\left(e^{\alpha C(z)} e^{\beta C(z)}\right) = \sum_{k=0}^n \left( [z^k]e^{\alpha C(z)} \right) \left( [z^{n-k}]e^{\beta C(z)} \right)= \sum_{k=0}^n \frac{\alpha (k + \alpha)^{k-1}}{k!} \frac{\beta (n - k + \beta)^{n-k-1}}{(n-k)!}.

Now, we just need to equate and simplify the LHS and RHS to get

(α+β)(n+α+β)n−1n!=∑k=0nα(k+α)k−1k!β(n−k+β)n−k−1(n−k)!(α+β)(n+α+β)n−1=∑k=0nn!k!(n−k)!α(k+α)k−1β(n−k+β)n−k−1=αβ∑k=0n(nk)(k+α)k−1(n−k+β)n−k−1.\begin{align*} \frac{(\alpha + \beta)(n + \alpha + \beta)^{n-1}}{n!} &= \sum_{k=0}^n \frac{\alpha (k + \alpha)^{k-1}}{k!} \frac{\beta (n - k + \beta)^{n-k-1}}{(n-k)!} \\ (\alpha + \beta)(n + \alpha + \beta)^{n-1} &= \sum_{k=0}^n \frac{n!}{k!(n-k)!} \alpha (k + \alpha)^{k-1} \beta (n - k + \beta)^{n-k-1} \\ &= \alpha \beta \sum_{k=0}^n \binom{n}{k} (k + \alpha)^{k-1} (n - k + \beta)^{n-k-1}. \end{align*}

Exercise 9.39

Since "average search cost" can refer to either finding a key that is in the table (successful) or verifying a key is not in the table (unsuccessful), we cover both scenarios based on Table 9.9 from the book. The objective is to find the point where the cost equals ln⁡N\ln N.

The threshold for a successful search is

12(1+11−α)=ln⁡N  ⟹  α=1−12ln⁡N−1.\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right) = \ln N \implies \alpha = 1 - \frac{1}{2 \ln N - 1}.

Substituting α≡N/M\alpha ≡ N/M and solving for NN, we get the implicit equation

N=M(1−12ln⁡N−1).N = M \left( 1 - \frac{1}{2 \ln N - 1} \right).

The threshold for an unsuccessful search is handled in virtually the same manner. Thus,

N=M(1−12ln⁡N−1).N = M \left( 1 - \frac{1}{\sqrt{2 \ln N - 1}} \right).

Exercise 9.40

Program 9.2 will enter an infinite loop, which means the cost is infinite.

Evaluating the exact formula from Table 9.9 for this edge case gives back a finite value. The reason is that the precondition N<MN<M is violated, hence the output is meaningless.

Exercise 9.41

We want to construct the EGF with respect to NN, treating the table size MM as a fixed parameter. The method is virtually the same as in the case of a successful search demonstrated in the book. This gives

UM(z)=∑N≥0UM,NzNN!=12∑N≥0zNN!+12∑N≥0∑k=0NN!k!(N−k)!(k+1)!MkzNN!(see Table 9.9 and reported errata)=12ez+12∑k≥0k+1Mk∑N=k∞zN(N−k)!=12ez+12∑k≥0k+1Mkzk∑j≥0zjj!=12ez+12ez∑k≥0(k+1)(zM)k=12ez(1+1(1−z/M)2)(∑k≥0(k+1)xk=1(1−x)2).\begin{align*} U_M(z) &= \sum_{N \ge 0} U_{M,N} \frac{z^N}{N!} \\[0.4cm] &= \frac{1}{2} \sum_{N \ge 0} \frac{z^N}{N!} + \frac{1}{2} \sum_{N \ge 0} \sum_{k=0}^N \frac{N!}{k!(N-k)!} \frac{(k+1)!}{M^k} \frac{z^N}{N!} && \text{(see Table 9.9 and reported errata)} \\[0.4cm] &= \frac{1}{2} e^z + \frac{1}{2} \sum_{k \ge 0} \frac{k+1}{M^k} \sum_{N=k}^\infty \frac{z^N}{(N-k)!} \\[0.4cm] &= \frac{1}{2} e^z + \frac{1}{2} \sum_{k \ge 0} \frac{k+1}{M^k} z^k \sum_{j \ge 0} \frac{z^j}{j!} \\[0.4cm] &= \frac{1}{2} e^z + \frac{1}{2} e^z \sum_{k \ge 0} (k+1) \left(\frac{z}{M}\right)^k \\[0.4cm] &= \frac{1}{2} e^z \left( 1 + \frac{1}{(1 - z/M)^2} \right) && \text{$\left(\sum_{k \ge 0} (k+1)x^k = \frac{1}{(1-x)^2}\right)$}. \end{align*}

Exercise 9.42

The "solution" is given in the matching footnote in the book.

When you build an EGF using the symbolic method, the structures must physically make sense. It must natively encode the hard stop at N=MN=M while simultaneously yielding a clean, infinite-series function. Here is the pertinent citation from the book regarding the explicit EGF for a successful search:

This is not directly meaningful for linear probing because the quantities are defined only for N ≤ M but it would seem a fine candidate for a combinatorial interpretation.

We had encountered a similar situation with CFGs (see Exercise 8.35). Employing BGFs may solve the spatial constraints.

Nonetheless, there is another fundamental issue. An inability of the symbolic method's grammar to directly specify the historical averaging process. Deriving the successful search cost requires performing a discrete integration over the timeline of the table's construction; it was computed in the book by averaging all unsuccessful searches that happened while building the table. But this is evidently a step outside the symbolic framework to finish the math.

Some attempts have already been made with the combinatorial structure called an increasing tree to track history. The problem with linear probing is that disjoint clusters can merge over time and this introduces global dependencies that are difficult to handle.

I think, that aggressively forcing some method beyond its capabilities could jeopardize the core principles that were in place originally. Even if new operators and extensions may encompass the above features, it could be at the expense of comprehensibility and succinctness of the current grammar. This is reminiscent to an old battle in computer science with every domain specific language: "Should it be more powerful?" Once a DSL becomes Turing complete, abuses of the grammar happen, and things start to fall apart. One notable example is the C++'s templating engine, that inadvertently became overly capable. Now, a simple syntax error in a template can generate hundreds of lines of incomprehensible compiler errors.

Exercise 9.43

Let’s use the symbolic method applied to the occupancy model (see Theorem 9.5). The EBGF for a single integer (urn) is ϵ+u×SET>0(Z)=1+u(ez−1)\epsilon + u\times \text{SET}_{>0}(\mathcal{Z})=1 + u(e^z - 1). Because the mapping consists of NN independent urns (the elements of the image), the EBGF for the entire mapping is simply the single-urn EBGF raised to the power of NN. This gives

CN(z,u)=(1+u(ez−1))N.C_N(z, u) = (1 + u(e^z - 1))^N.

It’s easy to verify the correctness of this EBGF by extracting the coefficient of ukzNN!u^k \frac{z^N}{N!}. Expanding the binomial and applying the identity from Table 3.6 for Stirling numbers of the second kind gives

CN(z,u)=∑k=0N(Nk)uk(ez−1)k=∑k=0N(Nk)uk(k!∑j≥k{jk}zjj!)∴[ukzNN!]CN(z,u)=k!(Nk){Nk}.C_N(z, u) = \sum_{k=0}^N \binom{N}{k} u^k (e^z - 1)^k= \sum_{k=0}^N \binom{N}{k} u^k \left( k! \sum_{j \ge k} \genfrac{\{}{\}}{0pt}{}{j}{k} \frac{z^j}{j!} \right) \\[0.4cm] \therefore \left[u^k \frac{z^N}{N!}\right] C_N(z, u) = k! \binom{N}{k} \genfrac{\{}{\}}{0pt}{}{N}{k}.

Now, performing the previous transformations in an opposite direction, starting from the formula for CNkC_{Nk}, we can arrive at the EBGF CN(z,u)C_N(z,u).

Exercise 9.44

See the previous exercise, which actually combines two approaches inside a single solution.

Exercise 9.45

CNk=k!(Nk){Nk}=k!(Nk)[k{N−1k}+{N−1k−1}](by Exercise 3.72)=k⋅NN−k⋅[k!(N−1k){N−1k}]+Nk⋅k[(k−1)!(N−1k−1){N−1k−1}]=N⋅kN−kC(N−1)k+NC(N−1)(k−1).\begin{align*} C_{Nk} &= k! \binom{N}{k} \genfrac{\{}{\}}{0pt}{}{N}{k} \\[0.4cm] &= k! \binom{N}{k} \left[ k \genfrac{\{}{\}}{0pt}{}{N-1}{k} + \genfrac{\{}{\}}{0pt}{}{N-1}{k-1} \right] && \text{(by Exercise 3.72)} \\[0.4cm] &= k \cdot \frac{N}{N-k} \cdot \left[ k! \binom{N-1}{k} \genfrac{\{}{\}}{0pt}{}{N-1}{k} \right] + \frac{N}{k} \cdot k \left[ (k-1)! \binom{N-1}{k-1} \genfrac{\{}{\}}{0pt}{}{N-1}{k-1} \right] \\[0.4cm] &= \frac{N \cdot k}{N-k} C_{(N-1)k} + N C_{(N-1)(k-1)}. \end{align*}

While the above equation is the exact direct recurrence, it introduces a division by N−kN-k. When programming this to generate a table, floating-point division can lead to precision errors for large combinatorial integers. Let’s use the substitution DNk=CNk/(Nk).D_{Nk}=C_{Nk}/ \binom{N}{k}. We can leverage again the following two identities:

  • (Nk)=NN−k(N−1k)\binom{N}{k} = \frac{N}{N-k} \binom{N-1}{k}

  • (Nk)=Nk(N−1k−1)\binom{N}{k} = \frac{N}{k} \binom{N-1}{k-1}

This gives DNk=kD(N−1)k+kD(N−1)(k−1)D_{Nk}=k D_{(N-1)k} + k D_{(N-1)(k-1)}. The following Python script produces the table of mappings for N<20N<20.

Exercise 9.46

The explicit expression is

(Mk)k!{Nk}=Mk‾{Nk}.\binom{M}{k} k! \genfrac{\{}{\}}{0pt}{}{N}{k}=M^{\underline{k}} \genfrac{\{}{\}}{0pt}{}{N}{k}.

The combinatorial reasoning is analogous to the number of mappings, as explained in the book.

Exercise 9.47

A random NN-mapping is any function ff with the integers 1 to NN as both domain and range. Run the following procedure:

  1. Initialize an empty set SS and a current value u=u0u = u_0 (seed).

  2. While u∉Su \notin S:

    1. Insert uu into SS

    2. Set u=f(u)u = f(u)

Because SS can hold a maximum of NN distinct integers, the while loop can run a maximum of NN times. Upon the (N+1)(N+1)th iteration (at the absolute latest), uu must evaluate to a number already in SS by the Pigeonhole principle. The loop terminates, and the cycle is found.

Exercise 9.48

The following Python script reports some properties about the specified random mappings for various input sizes.

It produces the following output:

A truly uniform random mapping has an image ratio 1−1/e≈0.6321 - 1/e \approx 0.632, on the average. This follows from the corollary of Theorem 9.5 with α=1\alpha=1 pertaining to the expected number of empty urns. Thus, a random mapping will leave about 36.8% of the range completely empty.

Exercise 9.49 🌟

This exercise introduces the principle of deferred decisions, a powerful technique in analyzing randomized algorithms.

Imagine we’re constructing our random mapping f:1,2,…,N→1,2,…,Nf: {1, 2, \dots, N} \to {1, 2, \dots, N} dynamically, rather than generating the whole thing up front. Starting from an arbitrary seed x0x_0, we generate subsequent values on the fly, essentially simulating each time an independent roll of an NN-sided die.

The isomorphism to the birthday problem is based on the following observations:

  • In the mapping, the table size is NN. In the birthday problem, it’s the NN days of the year.

  • In the mapping, we’re taking a step to a new node xkx_k. In the birthday problem, it’s a new person walking in.

  • In the mapping, we hit a cycle the moment ff outputs a node xjx_j we’ve already visited. In the birthday problem, we stop the moment a person announces a birthday that someone else in the room already has.

Let TT be the number of distinct nodes visited (the rho length) before closing the cycle. Let BB be the number of people in the room before the first shared birthday is found. Their probability distributions are identical

Pr⁡{T>k}≡Pr⁡{B>k}.\Pr\{T > k\} \equiv \Pr\{B > k\}.

The book contains, at the time of this writing, an unreported errata. Namely, the fomula in Theorem 9.9 should read as Pr⁡{rho length>k}=(N−1N)(N−2N)…(N−kN)\Pr\{\text{rho length} > k\} = \left(\frac{N-1}{N}\right) \left(\frac{N-2}{N}\right) \dots \left(\frac{N-k}{N}\right).

Using the tail sum formula for expectation, we can also conclude that

E[T]=E[B]=∑k=0NPr{B>k}∼πN2.\mathbb{E}[T] = \mathbb{E}[B] = \sum_{k=0}^N Pr\{B > k\} \sim \sqrt{\frac{\pi N}{2}}.

Exercise 9.50

The minimal rho length is achieved for identity mapping, resulting in the rho length of NN. The maximal length is attained for a random mapping being a permutation with one cycle. The length in this case is N2N^2.

The minimal tree length is achieved for a random mapping being a permutation; all tails are empty, so the length is zero. The maximal length is attained for a random mapping being a single linear chain tree that terminates in a fixed point. The length is N(N−1)/2N(N-1)/2.

Exercise 9.51

The next Python script computes the relevant statistics. The theoretical asymptotic estimates are based on Theorem 9.10 and Table 9.12 from the book. The averages are reported as seen from a random point.

The program generates the following output:

Exercise 9.52

Wikipedia covers the topic of cycle detection in some detail. It presents several algorithms that may answer the query of this exercise using only O(1) extra space for a random point. Iterating over all points and summing the results provides the required answer.

Exercise 9.53

The linear time algorithm using linear extra space is depicted below. For clarity the two stages are kept separate, although they could be bundled to avoid traversing the array twice.

1

Find the root

Iterate through the mapping array f once to count how many nodes satisfy f[i] == i. If the count is different than 1, then announce that the mapping isn’t a tree and stop.

2

Check if all nodes connect to the root

Iterate through the mapping array f once again and associate (i, f[i]) to belong to the same group. For this purpose, use the union-find data structure (see Section 6.13 in the book). If the mapping is a tree, there should be only one group formed.

Exercise 9.54

The next Python script uses the union-find data structure to track groups and their sizes (see also the previous exercise). The find method employs path compression to improve performance.

The program generates the following output:

The computed averages nicely align with the prediction from Table 9.12 even for small NN.

Exercise 9.55 🌟

This exercise formally introduces the pointing operator Θ\Theta of the symbolic method. It was used many times before, but here it has a special combinatorial role.

There are several derivation stages that build upon the idea of looking at random mappings as sets of cycles of Cayley trees.

The Structural Decomposition (the "Rho" Shape)

To find the expected rho length of a random point, we first need to isolate a single, random node in the mapping. This is called a pointed mapping. When you point to a random node xx and trace its path, it forms a sequence of nodes (the tail) that eventually falls into a cycle. Let's break this pointed path down into Cayley trees:

  • The Tail: The path from xx to the cycle is effectively a branch of a tree. If this path has tt nodes, it is structurally equivalent to a sequence of exactly tt trees rooted along the path.

  • The Cycle: The cycle has some length cc. The node where the tail meets the cycle accounts for 1 tree. The remaining nodes in the cycle correspond to a sequence of c−1c-1 trees.

Notice that the total number of trees forming this entire backbone is t+c−1t + c - 1. Therefore, the rho length is exactly equal to the total number of trees in this specific pointed component.

Formulation of the BGF

The EGF that enumerates cycles of trees (unpointed components) is from the book

U(z)=∑k≥1C(z)kk=ln⁡11−C(z)=∑N≥1UNzNN!.U(z) = \sum_{k \ge 1} \frac{C(z)^k}{k}=\ln \frac{1}{1 - C(z)}=\sum_{N \ge 1} U_N\frac{z^N}{N!}.

UNU_N is the number of valid cycles of trees you can build using NN nodes. Let’s apply the pointing operator Θ\Theta on U(z)U(z) to enumerate pointed components. This gives

P(z)=zddz(ln⁡11−C(z))=zC′(z)1−C(z)=C(z)(1−C(z))2(zC′(z)=C(z)1−C(z))=∑N≥1PNzNN!.\begin{align*} P(z) &= z \frac{d}{dz} \left( \ln \frac{1}{1 - C(z)} \right) \\[0.4cm] &= \frac{z C'(z)}{1 - C(z)} \\[0.4cm] &= \frac{C(z)}{(1 - C(z))^2} && \text{$\left(z C'(z) = \frac{C(z)}{1 - C(z)}\right)$} \\[0.4cm] &= \sum_{N \ge 1} P_N \frac{z^N}{N!}. \end{align*}

Combinatorially, PN=NUNP_N=NU_N counts the total number of pointed connected components of size NN. For every single one of those unpointed components, there are exactly NN different nodes you could choose to point to.

If we expand P(z)P(z) as a geometric series, we get ∑kkC(z)k\sum_k k C(z)^k. The power kk represents the number of trees in the component. Since we just proved that the number of trees equals the rho length, we can mark trees by substituting C(z)C(z) with uC(z)uC(z). We’ve

P(z,u)=uC(z)(1−uC(z))2=∑N≥1∑k≥1PNkukzNN!.P(z, u) = \frac{u C(z)}{(1 - u C(z))^2}= \sum_{N \ge 1} \sum_{k \ge 1} P_{Nk} u^k \frac{z^N}{N!}.

Combinatorially, PNkP_{Nk} counts the number of pointed connected components of size NN where the pointed node has a rho length of exactly kk.

But why is the coefficient kk in P(z)=∑kkC(z)kP(z) = \sum_k k C(z)^k? There are exactly kk different ways to split a sequence of kk trees into "the tail" and "the cycle." This is why a component with a rho length of kk has exactly kk valid structural configurations! Observe that by pointing to a node we break the symmetry of a cycle (dividing by kk disappears in U(z))U(z)) and we allow a sequence of kk trees to form kk distinct rho shapes. Again, the unit of abstraction is a complete Cayley tree, thus all sub-branching is handled internally and tracked by zz.

A pointed mapping consists of exactly one pointed component and a set of unpointed components. The EGF for the set of unpointed components is given in the book

E(z)=exp⁡(ln⁡11−C(z))=11−C(z).E(z) = \exp\left( \ln \frac{1}{1 - C(z)} \right) = \frac{1}{1 - C(z)}.

Our final BGF is the product of these two GFs

M(z,u)=(11−C(z))uC(z)(1−uC(z))2=∑N≥1∑k≥1MNkukzNN!.M(z, u) = \left( \frac{1}{1 - C(z)} \right) \frac{u C(z)}{(1 - u C(z))^2}= \sum_{N \ge 1} \sum_{k \ge 1} M_{Nk} u^k \frac{z^N}{N!}.

Combinatorially, MNkM_{Nk} counts the number of random NN-mappings, containing a pointed node, where the rho length of that pointed node is exactly kk.

Asymptotic Estimation

The total sum of rho lengths across all possible mappings is

H(z)=∂∂uM(z,u)∣u=1=C(z)(1+C(z))(1−C(z))4.H(z) = \left. \frac{\partial}{\partial u} M(z, u) \right|_{u=1} = \frac{C(z) (1 + C(z))}{(1 - C(z))^4}.

We should use here the general singularity analysis method of analytic combinatorics. We know the Cayley tree function has a dominant singularity at z=1/ez = 1/e, where its Taylor expansion behaves as:

C(z)∼1−2(1−ez).C(z) \sim 1 - \sqrt{2(1 - ez)}.

Let's evaluate H(z)H(z) near this singularity. This gives

H(z)∼24(1−ez)2=12(1−ez)−2  ⟹  [zN]H(z)∼12eNN.H(z) \sim \frac{2}{4(1 - ez)^2} = \frac{1}{2} (1 - ez)^{-2} \implies [z^N] H(z) \sim \frac{1}{2} e^N N.

We’re now ready for the final assembly by leveraging Stirling’s approximation of N!N!

Average Total Rho Length=N!NN(12eNN)∼2πN(N/e)NNN(12eNN)=NπN2.\text{Average Total Rho Length} = \frac{N!}{N^N} \left( \frac{1}{2} e^N N \right) \sim \frac{\sqrt{2\pi N} (N/e)^N}{N^N} \left( \frac{1}{2} e^N N \right) = N \sqrt{\frac{\pi N}{2}}.

Dividing this total by NN, we get the average rho length of a random point.

Exercise 9.56

Based on the result of Exercise 9.48, we know that the image ratio for the first iteration is 1−1/e1-1/e, therefore the size of the input for the second iteration is k=N(1−1/e)k=N(1-1/e). Using the same logic, the new image ratio is 1−e−k/N1-e^{-k/N}. Thus, the average number of different integers in the image when a random mapping is iterated twice is N(1−e−1+1/e)≈0.47NN(1-e^{-1+1/e}) \approx 0.47N.

Exercise 9.57

This is documented as OEIS A001372.

Exercise 9.58 🌟

This exercise introduces a handy variant of the Lagrange inversion theorem that avoids the derivative form (3rd case).

In a standard mapping, every single node has an out-degree of exactly 1. Consequently, every path is guaranteed to eventually lead to a cycle. In a partial mapping, some nodes have an out-degree of 0. These nodes act as "sinks" where the path simply stops.

This splits the graph into two entirely distinct types of connected components, which is best illuminated by the following symbolic expression (a Cayley tree is denoted by TC\mathcal{T_C}):

P=SET(CYC>0(TC))×SET(TC)  ⟹  P(z)=eC(z)1−C(z).\mathcal{P}=\text{SET}(\text{CYC}_{>0}(\mathcal{T_C})) \times \text{SET}(\mathcal{T_C}) \implies P(z) = \frac{e^{C(z)}}{1 - C(z)}.

We can use the alternative variant of the Lagrange inversion theorem

[zN]g(C(z))1−C(z)ϕ′(C(z))ϕ(C(z))=[uN]g(u)ϕ(u)N,[z^N] \frac{g(C(z))}{1 - C(z) \frac{\phi'(C(z))}{\phi(C(z))}} = [u^N] g(u) \phi(u)^N,

where ϕ(u)=u/f(u)=eu\phi(u)=u/f(u)=e^u and g(u)=eug(u)=e^u. In our case, ϕ′(u)/ϕ(u)=1\phi'(u)/\phi(u)=1. This immediately gives

N![zN]P(z)=N![uN]e(N+1)u=(N+1)N.N![z^N] P(z) = N![u^N] e^{(N+1)u} = (N+1)^N.

Exercise 9.59

By defining a sequence of 2N2N integers strictly bounded between 1 and NN, the mapping ff forces a "layered" topological structure:

  • The Core 1≤x≤N1 \le x \le N: These NN nodes map exclusively to other nodes in the same range, so they form a standard random NN-mapping.

  • The Periphery N+1≤x≤2NN+1 \le x \le 2N: These NN nodes also map into the core range. Because no node can ever map to them, they are guaranteed to be absolute leaves (nodes with an in-degree of exactly 0).

Assume that "path length" means the total sum of the tree path lengths (the number of steps to reach a cycle) for all 2N2N nodes. Let TNT_N be the total tree path length of a standard random NN-mapping. We know from Table 9.12 that its expected value is

E[TN]∼NπN8.\mathbb{E}[T_N] \sim N \sqrt{\frac{\pi N}{8}}.

Every peripheral node jj takes exactly 1 step to enter the core (by landing on its target f(j)f(j)). Once it lands there, it simply inherits the remaining path length of that target node. Therefore,

Total Peripheral Path Length=∑j=N+12N(1+E[TN]N)=N(1+E[TN]N)=N+E[TN].\text{Total Peripheral Path Length} = \sum_{j=N+1}^{2N} \left(1 + \frac{E[T_N]}{N}\right) = N \left(1 + \frac{E[T_N]}{N}\right) = N + E[T_N].

Adding together the two pieces and simplifying gives

Total Path Length∼2(NπN8)+N=NπN2+N.\text{Total Path Length} \sim 2 \left( N \sqrt{\frac{\pi N}{8}} \right) + N = N \sqrt{\frac{\pi N}{2}} + N.

The average path length as seen from a random point is the total divided by 2N2N.

Exercise 9.60

The next Python script empirically verifies the statistics given in Table 9.12.

It produces the following output:

Exercise 9.61

Modern PRNGs, like Mersenne Twister, don’t have short cycles. Therefore, the Python script below use less capable generators to demonstrate the issue of short cycles, although it does showcase a linear congruential generator whose image spans the range (this was mentioned in the book). The cycle detection algorithm is the one from Exercise 9.52.

It produces the following output:

Exercise 9.62

See the previous exercise. The middle-square method is famous for collapsing into extremely short cycles or hitting zero.

Exercise 9.63

The next script demonstrates how "collapses" occur for non prime modulus. For a prime NN, all values of cc produce an expected result O(N)O(\sqrt N), on the average. The strangest behavior happens for a power of prime. At any rate, instead of averaging over many randomly selected values of cc, the program shows how various choices influence the simulated random mapping.

The program creates the following report:

Exercise 9.99*

The text of this exercise is available at the book’s website; it’s not in the book, but it should be. The EGF that defines random mappings with no singleton cycles, as a function of the Cayley function, is

F(z)=e−C(z)1−C(z).F(z)=\frac{e^{-C(z)}}{1-C(z)}.

The alternative variant of the Lagrange inversion theorem (see Exercise 9.58) immediately gives

Probability=N!NN[zN]F(z)=N!NN[uN]e(N−1)u=N!NN⋅(N−1)NN!=(1−1N)N∼1/e.\text{Probability}=\frac{N!}{N^N} [z^N]F(z)=\frac{N!}{N^N}[u^N] e^{(N-1)u}=\frac{N!}{N^N} \cdot \frac{(N-1)^N}{N!}= \left( 1 - \frac{1}{N} \right)^N \sim 1/e.

The last step follows by letting N→∞N \to \infty.

PreviousChapter 8: Strings and Tries

Last updated