Pre-Midterm Review Questions

Mark all correct answers in each of the following questions.

1. Consider the lazy secretary problem. Given an assignment of letters to envelopes, a set {i_{1}, i_{2}, …, i_{k}} is a k-cycle if the letter to person i_{1} is sent to person i_{2}, the letter to i_{2} is sent to i_{3}, ..., the letter to i_{k} is sent to i_{1}. Denote by p_{k} the probability that there exists at least one k-cycle. Thus, for example, we have

p_{1} = 1 − \frac{1}{2!} + \frac{1}{3!} − … + \frac{(−1)^{n−1}}{n!} .

(a) For sufficiently large n we have p_{2} < p_{1}.

(b) We have p_{2} ⟶_{n→∞} 1 − \frac{1}{\sqrt{e}}.

(c) We have p_{2} − p_{1} ⟶_{n→∞} 0.

(d) We have p_{k} = \frac{1}{k} for \frac{n}{2} < k ≤ n and p_{k} < \frac{1}{k} for k < \frac{n}{2}.

(e) The probability that there exists a k-cycle for some k > \frac{n}{2} is larger than \frac{1}{2} for sufficiently large n.

(f) The probability that there exists a k-cycle for some k > \frac{n}{2} converges to ln 2 as n → ∞. (Hint: The sum of the first n terms of the harmonic series behaves asymptotically as ln n + γ, where γ ≈ 0.577 is Euler’s constant.)

(g) None of the above.

2. Let A_{1}, A_{2}, … be events in a probability space (Ω, B, P).

(a) If P (⋃_{i=1}^{n} A_{i}) = ∑_{i=1}^{n} P (A_{i}) for a certain n, then A_{i} ⋂ A_{j} = ∅ for 1 ≤ i < j ≤ n.

(b) If A_{i} ⋂ A_{j} = ∅ for 1 ≤ i < j ≤ n, then P (⋃_{i=1}^{n} A_{i}) = ∑_{i=1}^{n} P (A_{i}).

(c) Denoting a_{r} = ∑_{1≤j_{1}<j_{2}<...<j_{r}<∞} P (⋂_{i=1}^{r} A_{j_{i}}) for each r, we have

P (⋃_{n=1}^{∞} A_{n}) = ∑_{r=1}^{∞}(−1)^{r−1}a_{r}.

(d) The formula in the preceding part is valid if P (A_{n}) ⟶_{n→∞} 0, but is false in general.

(e) If there exists a non-empty event A such that P (A) = 0, then P is not a probability function.

(f) Given a set A ⊆ N, put P (A) = lim sup_{n→∞} \frac{|A ⋂\{1,2,...,n\}|}{n} (where |F | denotes the cardinality of a finite set F). Then P defines a probability function on the collection of all subsets of N.

(g) None of the above.

3. Consider the following code fragment:

int counter1 = 0, counter2 = 0;
for (int i = 1; i <= n; i++)
  if (Math.random() < 0.5)
     counter1++;
for (int i = 1; i <= n + 1; i++)
  if (Math.random() < 0.5)
     counter2++;

Assume that n is a variable of type int, having some positive value when the above code is executed.

(a) The probability that after the code is executed counter1 is (strictly) smaller than counter2 is 1/2 for any value of n.

(b) The probability that after the code is executed counter1 is smaller than counter2 is 1/2 for infinitely many values of n and is smaller than 1/2 for infinitely many others.

(c) The probability that after the code is executed counter1 is smaller than counter2 is 1/2 for infinitely many values of n and is larger than 1/2 for infinitely many others.

(d) If the condition i <= n in the first loop is replaced by i <= m for some m larger than n, then the probability in question (strictly) increases.

(e) If the condition i <= n+1 in the second loop is replaced by i <= m for some m larger than n+1, then the probability in question increases.

(f) If the code fragment in question is embedded in a loop executed repeatedly until counter1 is smaller than counter2, then there is a positive probability the loop will never terminate.

(g) None of the above.

4. Two cards are drawn randomly without replacement from a full deck of cards, and then returned to the deck. The experiment is carried out over and over until for the first time both cards drawn are kings. For m ≥ 0, denote by K_{m} the event that during the experiment a total of m kings are drawn (not including the two kings drawn at the last stage). Let Q_{m} be the event that a total of m queens have been drawn during the experiment, and T_{n}, n ≥ 1, the event that the number of pairs of cards drawn is n (including the last drawing).

(a) Since the probability of drawing two kings at any stage is the same, the probability of having an even number of drawings is the same as that of having an odd number of drawings, that is P (⋃_{n=1}^{∞} T_{2n}) = P (⋃_{n=1}^{∞} T_{2n−1}).

(b) Since at each drawing (except for the last) we may have two queens, but not two kings, we should expect to see more queens than kings. Consequently, P (Q_{m}) ≥ P (K_{m}) for each m ≥ 0, with a strict inequality for at least one value of m.

(c) P (Q_{0}) = 1/34.

(d) P (Q_{m}) > 0 for every m ≥ 0. In particular, P (Q_{m}|T_{n}) > 0 for every m ≥ 0, n ≥ 1.

(e) P (K_{m}) = (\frac{31}{32})^{m−1} · \frac{1}{32}, m ≥ 0.

(f) If the two cards drawn at each stage were drawn with replacement instead of without replacement, P (T_{1}) was bigger.

(g) None of the above.

5. Alice performs the following experiment. First she rolls 6 dice, then 12 dice, then 18 dice, etc. She stops the experiment at the first stage n at which exactly n out the dice showed “1”, exactly n showed “2”, etc. Bob performs the same experiment, but stops at the first stage n at which exactly 2n out the dice showed either “1” or “2”, 2n showed either “3” or “4”, and 2n showed either “5” or “6”. Caroline also performs the same experiment, but stops at the first stage n at which exactly 3n out the dice showed either one of the numbers “1”, “2” and “3”.

(a) Each of the three players will stop with probability 1 within a finite time.

(b) Alice has a positive probability of never stopping, but Bob and Caroline will stop with probability 1 within a finite time.

(c) Alice and Bob have a positive probability each of never stopping, but Caroline will stop with probability 1 within a finite time.

(d) Each of the three players has a positive probability of never stopping.

(e) The probability that Alice will stop exactly after the second stage is \frac{5^{2}·7·11^{2}·29}{2^{11}·3^{12}}.

(f) There exists a constant 0 < p < 1 such that, for each n ≥ 1, the probability that Alice will stop exactly after the nth stage is (1 − p)^{n−1}p.

(g) None of the above.

Solutions

1. For any 1 ≤ i < j ≤ n, let A_{ij} denote the event that {i, j} is a 2-cycle. Thus:

p_{2} = P ( ⋃_{1≤i<j≤n} A_{ij}) .

We would like to employ the formula for calculating the probability of a union. Obviously:

P (A_{ij}) = \frac{(n − 2)!}{n!}, 1 ≤ i < j ≤ n.

Moreover, a typical intersection P (⋂_{l=1}^{r} A_{i_{l}j_{l}}) is of probability \frac{(n−2r)!}{n!} if all the sets {i_{l}, j_{l}} are disjoint and is empty otherwise. Since the number of such non-empty intersections is \frac{1}{r!} · \binom{n}{2,2,...,2,n−2r}, we have:

p_{2} = \binom{n}{2} · \frac{(n − 2)!}{n!} − \frac{1}{2!}\binom{n}{2, 2, n − 4} · \frac{(n − 4)!}{n!}

+\frac{1}{3!}\binom{n}{2, 2, 2, n − 6} · \frac{(n − 6)!}{n!} − …

+(−1)^{r−1} \frac{1}{r!}\binom{n}{2, 2, …, 2, n − 2r} · \frac{(n − 2r)!}{n!} + …

+(−1)^{[n/2]−1} \frac{1}{[n/2]!}\binom{n}{2, 2, …, 2, n − 2[n/2]} · \frac{(n − 2[n/2])!}{n!}

= \frac{1}{2} − \frac{1}{2!} · \frac{1}{2^{2}} + \frac{1}{3!} · \frac{1}{2^{3}} − … + (−1)^{[n/2]−1} \frac{1}{[n/2]!} · \frac{1}{2^{[n/2]}} .

Similarly to the lazy secretary problem we obtain:

p_{2} ⟶_{n→∞} 1 − \frac{1}{\sqrt{e}} .

As p_{1} ⟶_{n→∞} 1 − \frac{1}{e} > 1 − \frac{1}{\sqrt{e}}, we have p_{2} < p_{1} for sufficiently large n.

Now notice that any two cycles either coincide or are disjoint. Consequently, for k > n/2 there may exist at most one k-cycle. In other words, denoting by A_{i_{1}i_{2}...i_{k}} the event that {i_{1}, i_{2}, …, i_{k}} is a cycle, all distinct events of this form are disjoint. Now {i_{1}, i_{2}, …, i_{k}} is a cycle if and only if any cyclic permutation thereof {i_{j}, i_{j+1}, …, i_{k}, i_{1}, …, i_{j−1}} is such. Therefore the number of distinct k-cycles is n(n − 1) … (n − k + 1)/k, which implies:

p_{k} = \frac{n(n − 1) … (n − k + 1)}{k} · \frac{(n − k)!}{n!} = \frac{1}{k} .

For k < n/2 (and also k = n/2 for even n) there may be more than one k-cycle. Thus, the events of the form A_{i_{1}i_{2}...i_{k}} are not disjoint. The above calculation still gives that the sum of probabilities of these sets is 1/k. However, as they intersect the required probability is strictly smaller than the sum of probabilities, namely p_{k} < 1/k.

Obviously, we cannot have more than one cycle of length exceeding n/2, so that the probability of the event in part (e) is

∑_{n/2<k≤n} \frac{1}{k} = ∑_{k=1}^{n} \frac{1}{k} − ∑_{k=1}^{[n/2]} \frac{1}{k} = (ln n + γ + o(1)) − (ln[n/2] + γ + o(1))
= ln 2 + o(1) ⟶_{n→∞} ln 2.

In particular, this probability is larger than \frac{1}{2} for sufficiently large n.

Thus, (a), (b), (d), (e) and (f) are true.

2. There may exist non-empty events with 0 probability. For example, take Ω = {1, 2} and define P on all subsets of Ω by:

P (A) = \{ \begin{matrix}1, & 1 ∈ A, \\ 0, & 1 ∉ A. \end{matrix}

P is clearly a probability function, yet P ({2}) = 0.

The union of (finitely or countably many) sets of 0 probability is also such, even if the sets intersect. Thus the equality P (⋃_{i=1}^{n} A_{i}) = ∑_{i=1}^{n} P (A_{i}) is possible for intersecting sets. (More generally, the equality holds if all intersections A_{i} ⋂ A_{j} are of 0 probability.) Of course, as we showed in class, it follows easily from the definition of a probability function that the probability of a finite union of disjoint sets is the sum of probabilities of the sets in the union.

The value of ∑_{1≤j_{1}<j_{2}<...<j_{r}<∞} P (⋂_{i=1}^{r} A_{j_{i}}) may well be infinite for an infinite collection A_{1}, A_{2}, … of events. For example, taking A_{n} = Ω for each n, all intersections in the expression are of probability 1, so that the sum diverges. Even the additional condition P (A_{n}) ⟶_{n→∞} 0 does not guarantee that the sum does not diverge. For example, let (A_{n}) be a descending sequence of events with P (A_{n}) = 1/n for each n.

(A possibility for that is to take Ω = [0, 1], the probability of each subinterval of [0, 1] being its length, and putting A_{n} = [0, 1/n].) Then:

∑_{1≤j_{1}<j_{2}<...<j_{r}<∞} P (⋂_{i=1}^{r} A_{j_{i}}) ≥ ∑_{n=r}^{∞} \frac{1}{n} = ∞.

Taking P (A) = lim sup_{n→∞} \frac{|A ⋂\{1,2,...,n\}|}{n} clearly gives P (A) = 0 for every finite set A and P (N) = 1. Thus

P (⋃_{n=1}^{∞}{n}) = P (N) = 1,

whereas

∑_{n=1}^{∞} P ({n}) = ∑_{n=1}^{∞} 0 = 0.

It follows that P is not σ-additive. (Actually, with slightly more work one can show that P is not even finitely additive. Take a set constructed by taking large consecutive blocks of integers, followed by much larger holes, followed by much larger blocks, etc. For example, take

A = ⋃_{n=1}^{∞}{(2n)!, (2n)! + 1, …, (2n + 1)! − 1}.

Then both P (A) = 1 and P (\overline{A}) = 1. The point is that the sets A and \overline{A} “seem” large when measured at certain times, and small at others. Taking the lim sup gives both of them the measure they tend to assume when they are large, and ignores times when they are small. Since these sets are alternately small and large, with one being small exactly when the other is large, the lim sup “misses” when measuring their sizes.)

Thus, only (b) is true.

3. The first loop puts in counter1 the number of heads obtained out of n tosses of a coin. The second loop does the same for counter2, but for n + 1 tosses instead of n. Thus the probability that counter1 is smaller than counter2 is the same as that of a player tossing a coin n times to obtain less heads than a player tossing it n + 1 times. This probability has been computed in class to be 1/2 for any value of n.

Replacing n in the first loop by a larger integer is tantamount to letting the first player toss his coin more times, so that his probability of having less heads than his opponent decreases. If n + 1 in the second loop is increased, then the opposite happens.

Since the probability for counter1 to be smaller than counter2 is 1/2, if the experiment is held repeatedly, the probability for this event to happen m consecutive times is 1/2^{m}. It follows that the probability for the loop to never terminate is 0.

Thus, only (a) and (e) are true.

4. The probability of obtaining two kings at a single drawing of two cards is \frac{4·3}{52·51} = \frac{1}{221}. Hence:

P (T_{n}) = (\frac{220}{221})^{n−1} · \frac{1}{221} , n ≥ 1.

Consequently:

P (⋃_{n=1}^{∞} T_{2n−1}) = \frac{1}{221} · (1 + (\frac{220}{221})^{2} + (\frac{220}{221})^{4} + …)
= \frac{1}{221} · \frac{1}{1 − (220/221)^{2}} = \frac{221}{441} ,

and therefore

P (⋃_{n=1}^{∞} T_{2n}) = 1 − \frac{221}{441} = \frac{220}{441} .

Expecting to see more queens than kings does not mean that P (Q_{m}) ≥ P (K_{m}) for each m. It means rather (roughly speaking) that this inequality holds for large values of m, whereas for small values of m the converse inequality holds. Indeed, since ∑_{m=0}^{∞} P (Q_{m}) = ∑_{m=0}^{∞} P (K_{m}) = 1, the inequalities suggested in (b) are impossible.

To calculate P (Q_{0}) we use conditioning on the stage at which the two drawn cards are kings:

P (Q_{0}) = ∑_{n=1}^{∞} P (T_{n})P (Q_{0}|T_{n})
= ∑_{n=1}^{∞} (\frac{220}{221})^{n−1} · \frac{1}{221} · (\frac{48 · 47 − 4 · 3}{52 · 51 − 4 · 3})^{n−1}
= \frac{1}{221} · ∑_{n=0}^{∞} (\frac{187}{221})^{n−1} = \frac{1}{34} .

(A simpler way of finding P (Q_{0}) is as follows. Suppose we stop the experiment at the first stage when either one of the cards is a queen or both are kings. Our question is equivalent to asking for the probability that this new experiment will be stopped due to drawing two kings. Now in the new experiment we may ignore all outcomes except for either drawing at least one queen or drawing two kings. Drawing two queens arises in 52 · 51 − 48 · 47 possibilities, whereas drawing two kings arises in 4 · 3 possibilities. Hence P (Q_{0}) = \frac{4·3}{52·51−48·47} = \frac{1}{34}.)

It is true that P (Q_{m}) > 0 for every m ≥ 0. However, under T_{n} we draw only 2n − 2 cards before the final two kings, so that P (Q_{m}|T_{n}) = 0 for m ≥ 2n − 1.

We calculate P (K_{m}) similarly to the calculation of P (Q_{0}) above:

P (K_{m}) = ∑_{n=1}^{∞} P (T_{n})P (K_{m}|T_{n})

= ∑_{n=1}^{∞}(\frac{220}{221})^{n−1} · \frac{1}{221}_{·\binom{n−1}{m}(\frac{52·51−48·47−4·3}{52·51−4·3})m(\frac{48·47}{52·51−4·3})n−1−m}

= \frac{1}{221} · (\frac{8}{47})^{m} ∑_{n=0}^{∞} \binom{n}{m} (\frac{188}{221})^{n}
= \frac{1}{221} · (\frac{8}{47})^{m} \frac{(188/221)^{m}}{(33/221)^{m+1}} = (\frac{32}{33})^{m} · \frac{1}{33} .

If the two cards at each stage are drawn with replacement, then P (T_{1}) = (4/52)^{2} = 1/169 > 1/221, so that we would obtain a larger value for P (T_{1}) than is the case for our experiment.

Thus, only (c) and (f) are true.

5. Let α_{n} be the probability of Alice to stop the experiment at stage n, assuming she indeed got to this stage, and let β_{n} and γ_{n} be the corresponding probabilities for Bob and Caroline, respectively. Clearly:

α_{n} = \frac{\binom{6n}{n,n,n,n,n,n}}{6^{6n}},  β_{n} = \frac{\binom{6n}{2n,2n,2n}}{3^{6n}},  γ_{n} = \frac{\binom{6n}{3n,3n}}{2^{6n}} .

The probability for Alice to continue the experiment beyond the first n stages is ∏_{k=1}^{n}(1 − α_{k}). Thus her probability to continue forever is 0 if and only if ∏_{k=1}^{∞}(1 − α_{k}) = 0. According to Exercise 38(b), since all α_{k}’s are strictly between 0 and 1, we only have to find whether the series ∑_{k=1}^{∞} α_{k} diverges or converges. Now, according to Stirling’s formula

\binom{6n}{n, n, n, n, n, n} = \frac{(6n)!}{(n!)^{6}} ≈ \begin{matrix}\sqrt{2π · 6n} & (\frac{6n}{e}) & 6n \\ (\sqrt{2πn} (\frac{n}{e})^{n}) & 6 \end{matrix} = \frac{C_{1} · 6^{6n}}{n^{5/2}}

for some positive constant C_{1}, which yields

α_{n} ≈ \frac{C_{1}}{n^{5/2}} .

Since the series ∑_{n=1}^{∞} \frac{1}{n^{5/2}} converges, Alice will continue the experiment indefinitely with positive probability. Similarly

β_{n} ≈ \frac{C_{2}}{n} ,

and

γ_{n} ≈ \frac{C_{3}}{n^{1/2}} .

As the series ∑_{n=1}^{∞} \frac{1}{n} and ∑_{n=1}^{∞} \frac{1}{n^{1/2}} both diverge, Bob and Caroline will stop with probability 1 after a finite time.

Alice will stop after the nth stage with probability (∏_{k=1}^{n−1}(1 − α_{k})) α_{n}. For n = 2 we obtain

(1 − \frac{6!}{6^{6}} ) · \frac{\binom{12}{2,2,2,2,2,2}}{6^{12}} = \frac{5^{2} · 7 · 11^{2} · 29}{2^{10} · 3^{11}}.

Thus, only (b) is true.