(Feller^{[Notes 1]}) A large number, [math]N[/math], of people are subjected to a blood test. This can be administered in two ways: (1) Each person can be tested separately, in this case [math]N[/math] test are required, (2) the blood samples of [math]k[/math] persons can be pooled and analyzed together. If this test is negative, this one test suffices for the [math]k[/math] people. If the test is positive, each of the [math]k[/math] persons must be tested separately, and in all, [math]k + 1[/math] tests are required for the [math]k[/math] people. Assume that the probability [math]p[/math] that a test is positive is the same for all people and that these events are independent.

• Find the probability that the test for a pooled sample of [math]k[/math] people will be positive.
• What is the expected value of the number [math]X[/math] of tests necessary under plan (2)? (Assume that [math]N[/math] is divisible by [math]k[/math].)
• For small [math]p[/math], show that the value of [math]k[/math] which will minimize the expected number of tests under the second plan is approximately [math]1/\sqrt p[/math].

Notes

Write a program to add random numbers chosen from [math][0,1][/math] until the first time the sum is greater than one. Have your program repeat this experiment a number of times to estimate the expected number of selections necessary in order that the sum of the chosen numbers first exceeds 1. On the basis of your experiments, what is your estimate for this number?

The following related discrete problem also gives a good clue for the answer to Exercise Exercise. Randomly select with replacement [math]t_1[/math], [math]t_2[/math],..., [math]t_r[/math] from the set [math](1/n, 2/n, \dots, n/n)[/math]. Let [math]X[/math] be the smallest value of [math]r[/math] satisfying

Then [math]E(X) = (1 + 1/n)^n[/math]. To prove this, we can just as well choose [math]t_1[/math], [math]t_2[/math], ..., [math]t_r[/math] randomly with replacement from the set [math](1, 2, \dots, n)[/math] and let [math]X[/math] be the smallest value of [math]r[/math] for which

• Use Exercise to show that
  [[math]] P(X \geq j + 1) = {n \choose j}{\Bigl(\frac {1}{n}\Bigr)^j}\ . [[/math]]
• Show that
  [[math]] E(X) = \sum_{j = 0}^n P(X \geq j + 1)\ . [[/math]]
• From these two facts, find an expression for [math]E(X)[/math]. This proof is due to Harris Schultz.^{[Notes 1]}

Notes

(Banach's Matchbox^{[Notes 1]}) A man carries in each of his two front pockets a box of matches originally containing [math]N[/math] matches. Whenever he needs a match, he chooses a pocket at random and removes one from that box. One day he reaches into a pocket and finds the box empty.

• Let [math]p_r[/math] denote the probability that the other pocket contains [math]r[/math] matches. Define a sequence of counter random variables as follows: Let [math]X_i = 1[/math] if the [math]i[/math]th draw is from the left pocket, and 0 if it is from the right pocket. Interpret [math]p_r[/math] in terms of [math]S_n = X_1 + X_2 +\cdots+ X_n[/math]. Find a binomial expression for [math]p_r[/math].
• Write a computer program to compute the [math]p_r[/math], as well as the probability that the other pocket contains at least [math]r[/math] matches, for [math]N = 100[/math] and [math]r[/math] from 0 to 50.
• Show that [math](N - r)p_r = (1/2)(2N + 1)p_{r + 1} - (1/2)(r + 1)p_{r + 1}[/math]\ .
• Evaluate [math]\sum_r p_r[/math].
• Use (c) and (d) to determine the expectation [math]E[/math] of the distribution [math]\{p_r\}[/math].
• Use Stirling's formula to obtain an approximation for [math]E[/math]. How many matches must each box contain to ensure a value of about 13 for the expectation [math]E[/math]? (Take [math]\pi = 22/7[/math].)

Notes

A coin is tossed until the first time a head turns up. If this occurs on the [math]n[/math]th toss and [math]n[/math] is odd you win [math]2^n/n[/math], but if [math]n[/math] is even then you lose [math]2^n/n[/math]. Then if your expected winnings exist they are given by the convergent series

called the alternating harmonic series. It is tempting to say that this should be the expected value of the experiment. Show that if we were to do this, the expected value of an experiment would depend upon the order in which the outcomes are listed.

Suppose we have an urn containing [math]c[/math] yellow balls and [math]d[/math] green balls. We draw [math]k[/math] balls, without replacement, from the urn. Find the expected number of yellow balls drawn. Hint: Write the number of yellow balls drawn as the sum of [math]c[/math] random variables.

The reader is referred to Example for an explanation of the various options available in Monte Carlo roulette.

• Compute the expected winnings of a 1 franc bet on red under option (a).
• Repeat part (a) for option (b).
• Compare the expected winnings for all three options.

(from Pittel^{[Notes 1]}) Telephone books, [math]n[/math] in number, are kept in a stack. The probability that the book numbered [math]i[/math] (where [math]1 \le i \le n[/math]) is consulted for a given phone call is [math]p_i \gt 0[/math], where the [math]p_i[/math]'s sum to 1. After a book is used, it is placed at the top of the stack. Assume that the calls are independent and evenly spaced, and that the system has been employed indefinitely far into the past. Let [math]d_i[/math] be the average depth of book [math]i[/math] in the stack. Show that [math]d_i \le d_j[/math] whenever [math]p_i \ge p_j[/math]. Thus, on the average, the more popular books have a tendency to be closer to the top of the stack. Hint: Let [math]p_{ij}[/math] denote the probability that book [math]i[/math] is above book [math]j[/math]. Show that [math]p_{ij} = p_{ij}(1 - p_j) + p_{ji}p_i[/math].

Notes

(from Propp^{[Notes 1]}) In the previous problem, let [math]P[/math] be the probability that at the present time, each book is in its proper place, i.e., book [math]i[/math] is [math]i[/math]th from the top. Find a formula for [math]P[/math] in terms of the [math]p_i[/math]'s. In addition, find the least upper bound on [math]P[/math], if the [math]p_i[/math]'s are allowed to vary. Hint: First find the probability that book 1 is in the right place. Then find the probability that book 2 is in the right place, given that book 1 is in the right place. Continue.

Notes

(from H. Shultz and B. Leonard^{[Notes 1]}) A sequence of random numbers in [math][0, 1)[/math] is generated until the sequence is no longer monotone increasing. The numbers are chosen according to the uniform distribution. What is the expected length of the sequence? (In calculating the length, the term that destroys monotonicity is included.) Hint: Let [math]a_1,\ a_2,\ \ldots[/math] be the sequence and let [math]X[/math] denote the length of the sequence. Then

and the probability on the right-hand side is easy to calculate. Furthermore, one can show that

Notes