Let N denote the number of cycles that result in the match problem.

(a) LetMn =E[N], and derive an equation forMn in terms ofM1, . . . ,Mn−1.

(b) Let Cj denote the size of the cycle that contains person j . Argue that

and use the preceding to determine E[N].

(c) Find the probability that persons 1, 2, . . . , k are all in the same cycle.

(d) Find the probability that 1, 2, . . . , k is a cycle.

Transcribed Image Text:

n N = 1/C; j=1