Midterm

Mark all correct answers in each of the following questions.

1. The Computer Science Department and the Electrical Engineering Department have n students each. When the secretariat of a department has to send a letter to all students, it prepares the letters and the envelopes separately, and then the letters are put in the envelopes randomly. When it comes to the stage of stamping the envelopes, however, the departments have different methods for cutting expenses. At the Electrical Engineering Department they toss a die; if the die shows a “6” – all letters are stamped, otherwise – none is stamped. At the Computer Science Department (which is well known of giving each student a personal service) they toss a die n times. If the result of the ith toss is “6” – the ith envelope is stamped, otherwise – it is sent unstamped. Denote by p_{n} the probability that at least one letter sent by the Computer Science Department is sent stamped to the correct address. Let q_{n} be the analogous probability for the Electrical Engineering Department.

(a) For all sufficiently large n we have p_{n} = q_{n}.

(b) For sufficiently large n the probabilities p_{n} and q_{n} are very close. More precisely, \frac{p_{n}}{q_{n}} ⟶_{n→∞} 1.

(c) For all sufficiently large n we have p_{n} > q_{n}.

(d) For all sufficiently large n we have p_{n} < q_{n}.

(e) We have 6q_{n} + (1 − p_{n})^{6} ⟶_{n→∞} 1.

(f) We have p_{n} + q_{n} ⟶_{n→∞} 1/6.

(g) None of the above.

2. Consider the problem, discussed in class, of 2n people standing in line to buy tickets for a show. Suppose that, unlike the model presented in class, each person tosses a coin before leaving his house, and takes a 50-shekel bill or a 100-shekel bill depending on the outcome of this experiment. (Thus, the number of people with 50 shekels may well be different from that of people having 100 shekels.) Let p_{n} be the probability that none of the 100-shekel holders has to wait for change at the cashier in this model, and q_{n} the analogous probability for the model presented in class. (Recall that q_{n} = \frac{1}{n+1}.)

(a) For all sufficiently large n we have p_{n} = q_{n}.

(b) For all n:

p_{n} = \frac{1}{2^{2n}} ∑_{j=0}^{n} \frac{2j + 1}{n + j + 1}\binom{2n}{n + j}.

(c) For all n:

p_{n} = \frac{\binom{2n}{n}}{2^{2n}}.

(d) For sufficiently large n the probabilities p_{n} and q_{n} are very close,

namely \frac{p_{n}}{q_{n}} ⟶_{n→∞} 1.

(e) For large n the first probability is much larger than the second,

namely \frac{p_{n}}{q_{n}} ⟶_{n→∞} ∞.

(f) For large n the first probability is much smaller than the second,

namely \frac{p_{n}}{q_{n}} ⟶_{n→∞} 0.

(g) None of the above.

3. Consider the following two loops.

    // first loop
    for (anyint n = 1, counter1 = 1, counter2 = 0;
         counter1 != counter2; n++)
    {
       counter1 = counter2 = 0;
       for (anyint i = 1; i <= 2 * n; i++)

      if (Math.random() < 0.5)
         counter1++;
      else
         counter2++;
}
// second loop
for (anyint n = 1, counter1 = 1, counter2 = 0;
     counter1 != counter2; n++)
{
   counter1 = counter2 = 0;
   for (anyint i = 1; i <= n; i++)
      if (Math.random() < 0.5)
         counter1++;
   for (anyint i = 1; i <= n; i++)
      if (Math.random() < 0.5)
         counter2++;
}

Here anyint is a (theoretical) data type designed for all integers, without any size restriction.

(a) Each of the loops terminates with probability 1. Moreover, there is no reason to expect one of them to be executed usually more times than the other.

(b) Each of the loops terminates with probability 1. However, the first loop may be expected to be executed usually more times than the second.

(c) Each of the loops terminates with probability 1. However, the second loop may be expected to be executed usually more times than the first.

(d) The probability of the first loop to terminate is less than 1, while that of the second is 1.

(e) The probability of the second loop to terminate is less than 1, while that of the first is 1.

(f) Each of the loops terminates with probability less than 1.

(g) None of the above.

4. In Bill Gates’s mansion there are infinitely many rooms, denoted by the integers from 1 on. Due to software problems at the electricity system, when the electric switch at room n is turned, the situation of the light bulbs at all rooms whose number is divisible by n is changed; those that were on are turned off, while those which were off are turned on. Mr. Gates arrives home when all rooms are dark and turns the switch at some of them. (For example, if he turns only the switches at rooms 1, 5 and 8, then rooms 3 and 200, say, are lit, while rooms 24 and 25 are dark.) Now suppose that at each room he turns the switch with probability 1/3, different rooms being independent. Let A_{k}, k = 1, 2, …, be the event that at the end of the process room k is lit.

(a) P (A_{7}) = 4/9, P (A_{9}) > 4/9.

(b) P (A_{256}) = \frac{2^{8}}{3^{9}} ∑_{k=0}^{4} \binom{9}{2k+1}/2^{2k}.

(c) P (A_{5^{m+1}}) = \frac{2}{3}P (A_{5^{m}}) + \frac{1}{3}(1 − P (A_{5^{m}})), m ≥ 0.

(d) P (A_{2^{m}}) ⟶_{m→∞} \frac{1}{2}.

(e) The probabilities P (A_{2^{m}}) are in general smaller for even values of m than for odd values of m. Moreover, the subsequence formed by those at the even places converges to some α and the subsequence formed by those at the odd places converges to some β, where α < β.

(f) P (⋂_{k=1}^{∞} \overline{A}_{k}) = 0.

(g) None of the above.

5. S_{1} is a random subset of {1, 2, …, n}, chosen by including each element in it with probability 1/2, different elements being independent. S_{2} is chosen in the same way. The sets T_{1} and T_{2} are chosen similarly, but the probability of each element to belong to T_{1} is 2/3, while the probability of each element to belong to T_{2} is 1/3. For n ≥ 1 and 0 ≤ k ≤ n, put:

A_{nk} = {|S_{1} ⋃ S_{2}| = k}, B_{nk} = {|T_{1} ⋃ T_{2}| = k}, C_{nk} = {|S_{1} ⋂ S_{2}| = k}.

(a) P (A_{nk}) = P (B_{nk}) for all k and n.

(b) P (A_{nk}) ≥ P (B_{nk}) for all k and n.

(c) P (A_{nk}) = (\frac{6}{7})^{k} (\frac{9}{8})^{n} for all k and n.

(d) If the events A_{nk_{1}} and C_{nk_{2}} are disjoint for some n, k_{1} and k_{2}, then at least one of them is empty.

(e) For each n there exists a k such that P (C_{nk}|A_{nk}) = 0.

(f) For each n there exists a k such that P (C_{nk}|A_{nk}) = 1.

(g) None of the above.

Solutions

1. We start with calculating q_{n}. The event that at least one letter will be sent stamped to the correct address is given by the intersection B ⋂ C, where B is the event that at least one letter will be sent to the correct address and C is the event that the letters are stamped. Therefore

q_{n} = \frac{1}{6} [1 − \frac{1}{2!} + \frac{1}{3!} + … + \frac{(−1)^{n−1}}{n!} ] ,

and in particular

q_{n} ⟶_{n→∞} \frac{1}{6} (1 − \frac{1}{e}) .

To calculate p_{n}, denote by A_{i}, i = 1, 2 …, n, the event that the ith letter sent by the Computer Science Department is sent stamped to the right address. Obviously, P (A_{i}) = \frac{1}{6} · \frac{1}{n} = \frac{1}{6n} . Moreover, the intersection of any r distinct sets A_{i} is the same:

P (⋂_{j=1}^{r} A_{i_{j}}) = \frac{1}{6^{r}} · \frac{(n − r)!}{n!} .

The required event is simply ⋃_{i=1}^{n} A_{i}, and consequently:

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

In particular:

p_{n} ⟶_{n→∞} 1 − \frac{1}{e^{1/6}} .

Since 1 − \frac{1}{e^{1/6}} > \frac{1}{6} (1 − \frac{1}{e}), we have p_{n} > q_{n} for all sufficiently large n.

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

2. Let A be the event discussed in the question, and B_{k}, k = 0, 1, 2, …, 2n, the event that exactly k people come with a 50-shekel bill. Then:

P (A) = ∑_{k=0}^{2n} P (B_{k})P (A|B_{k}).

Now P (B_{k}) is the probability of obtaining k successes out of 2n independent trials with success probability 1/2 each, so that

P (B_{k}) = \frac{\binom{2n}{k}}{2^{2n}} .

The conditional probability P (A|B_{k}) clearly vanishes for k < n. For k ≥ n, the problem of calculating this probability is equivalent to that of the ballot problem, discussed in class, with m and n there replaced by k and 2n − k, respectively, in our problem. Thus

P (A|B_{k}) = 1 − \frac{2n − k}{k + 1} = \frac{2k − 2n + 1}{k + 1} = \frac{\binom{2n}{k} − \binom{2n}{k+1}}{\binom{2n}{k}} .

Using the first expression for the probability, we obtain:

P (A) = ∑_{k=n}^{2n} \frac{\binom{2n}{k}}{2^{2n}} · \frac{2k − 2n + 1}{k + 1} = \frac{1}{2^{2n}} ∑_{j=0}^{n} \frac{2j + 1}{n + j + 1}\binom{2n}{n + j} .

Using the second expression for P (A|B_{k}), we obtain:

P (A) = ∑_{k=n}^{2n} \frac{\binom{2n}{k}}{2^{2n}} · \frac{\binom{2n}{k} − \binom{2n}{k+1}}{\binom{2n}{k}}
= \frac{1}{2^{2n}} ∑_{j=0}^{n} (\binom{2n}{n + j} − \binom{2n}{n + j + 1}) = \frac{\binom{2n}{n}}{2^{2n}} .

Now according to Stirling’s formula:

\binom{2n}{n} ≈ \frac{\sqrt{2π · 2n}(2n/e)^{2n}}{(\sqrt{2πn}(n/e)^{n})^{2}} = \frac{2^{2n}}{\sqrt{πn}} .

Thus, p_{n} converges to 0 as C/\sqrt{n}, whereas q_{n} does so as 1/n, and consequently \frac{p_{n}}{q_{n}} ⟶_{n→∞} ∞.

Thus, only (b), (c) and (e) are true.

3. The first loop terminates after the nth iteration, assuming it gets to this iteration, if out of the 2n random numbers selected at the nth iteration there are exactly n smaller than 0.5 and exactly n larger (or

equal). The probability for this is \frac{\binom{2n}{n}}{2^{2n}}.

The second loop terminates after the nth iteration (again, assuming it gets to this iteration) if in two independent sequences of random numbers, of length n each, the same number of numbers less than 0.5 is obtained. The probability for this is

\frac{1}{2^{2n}} ∑_{k=0}^{n} \binom{n}{k}^{2} = \frac{\binom{2n}{n}}{2^{2n}} .

Consequently, the probability for each loop to iterate at least n + 1 times is

∏_{j=1}^{n} (1 − \frac{\binom{2j}{j}}{2^{2j}}) .

Since \binom{2j}{j}/2^{2j} ≈ C/\sqrt{j}, and ∑_{j=1}^{∞} 1/\sqrt{j} = ∞, the probability above converges to 0 as n → ∞. Hence each loop terminates with probability 1 within a finite time.

Thus, only (a) is true.

4. Obviously, the light at room n will be on at the end if and only if the button is pressed at an odd number of rooms out of those enumerated by divisors of n. Hence

P (A_{n}) = ∑_{k=0}^{[(d−1)/2]} \binom{d}{2k + 1} (\frac{1}{3})^{2k+1} (\frac{2}{3})^{d−2k−1} ,

where d is the number of divisors of n.

In particular, since 7 has two divisors we have

P (A_{7}) = \binom{2}{1} · \frac{1}{3} · \frac{2}{3} = \frac{4}{9} ,

and since 9 has three divisors:

P (A_{9}) = \binom{3}{1} · \frac{1}{3} (\frac{2}{3})^{2} + \binom{3}{3} · (\frac{1}{3})^{3} = \frac{10}{27} > \frac{4}{9} .

Since 256 has nine divisors:

P (A_{256}) = ∑_{k=0}^{4} \binom{d}{2k + 1} (\frac{1}{3})^{2k+1} (\frac{2}{3})^{9−2k−1} = \frac{2^{8}}{3^{9}} ∑_{k=0}^{4} \binom{9}{2k + 1}/ 2^{2k} .

To get a recursive formula for P (A_{5^{m}}) we proceed as follows:

P (A_{5^{m+1}}) = P (A_{5^{m}})P (A_{5^{m+1}}|A_{5^{m}}) + P (\overline{A}_{5^{m}})P (A_{5^{m+1}}|\overline{A}_{5^{m}})
= \frac{2}{3}P (A_{5^{m}}) + \frac{1}{3}(1 − P (A_{5^{m}})).

Similarly:

P (A_{2^{m+1}}) = \frac{2}{3}P (A_{2^{m}}) + \frac{1}{3}(1 − P (A_{2^{m}})).

Therefore:

P (A_{2^{m+1}}) − \frac{1}{2} = \frac{1}{3} (P (A_{2^{m}}) − \frac{1}{2}) .

By induction:

P (A_{2^{m}}) − \frac{1}{2} = \frac{1}{3^{m}} (P (A_{1}) − \frac{1}{2}) = \frac{1}{2 · 3^{m+1}} ,

which yields

P (A_{2^{m}}) ⟶_{m→∞} \frac{1}{2} .

Finally

P (⋂_{k=1}^{∞} \overline{A}_{k}) ≤ P (⋂_{k=1}^{n} \overline{A}_{k}) = (\frac{2}{3})^{n}

for every n ≥ 1, which proves that P (⋂_{k=1}^{∞} \overline{A}_{k}) = 0.

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

5. The probability of any element of {1, 2, …, n} not to belong to S_{1} ⋃ S_{2} is 1/4. Thus the size of S_{1} ⋃ S_{2} may be thought of as the number of successes in a sequence of length n of trials, each having success probability 3/4. Hence:

P (A_{nk}) = \binom{n}{k} (\frac{3}{4})^{k} (\frac{1}{4})^{n−k} .

Similarly:

P (B_{nk}) = \binom{n}{k} (\frac{7}{9})^{k} (\frac{2}{9})^{n−k} .

The events A_{nk_{1}} and C_{nk_{2}} may be disjoint even if none of them is empty. In fact, since the union of sets is at least as large as their intersection, A_{nk_{1}} and C_{nk_{2}} are necessarily disjoint if k_{1} < k_{2}. However, for 0 ≤ k_{1}, k_{2} ≤ n we have A_{nk_{1}} ≠ ∅ and C_{nk_{2}} ≠ ∅.

For each n, the event A_{n0} occurs if and only if both of the sets S_{1} and S_{2} are empty, in which case C_{n0} occurs as well. Thus P (C_{n0}|A_{n0}) = 1. On the other hand, if any A_{nk} is known to have occurred, it may be the case that the sets S_{1} and S_{2} coincide, in which case C_{nk} occurs as well. In particular, P (C_{nk}|A_{nk}) > 0 for every n and k. (Actually, this conditional probability is exactly (1/3)^{k}.)

Thus, only (f) is true.