Final #2

Mark all correct answers in each of the following questions.

1. Let a_{1}, a_{2}, …, a_{n}, where n ≥ 3, be a finite sequence consisting of distinct numbers, ordered randomly (with all n! permutations equiprobable). Let M be the number of pairs (i, j) such that 1 ≤ i < j ≤ n and a_{i} > a_{j}. Let S be the number of indices 1 ≤ i ≤ n − 2 for which the three terms a_{i}, a_{i+1}, a_{i+2} do not form a monotonic subsequence (namely, they satisfy either a_{i} < a_{i+1} > a_{i+2} or a_{i} > a_{i+1} < a_{i+2}). For example, if n = 10 and the ordering is 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, then M = 4 and S = 2. For convenience denote m = \binom{n}{2}.

(a) M ∼ B (m, \frac{1}{2}).

(b) S ∼ B (n − 2, \frac{1}{2}).

(c) E(M) = \frac{n(n−1)}{4} .

(d) E(S) > \frac{n−2}{2} for all sufficiently large n.

(e) P (M = m) = P (S = n − 2).

(f) The more the terms of the sequence are shuffled, the more disorder we should expect to have. Hence, if in addition to ordering the elements randomly we pick randomly a pair of distinct terms and swap them, and denote by M′ and S′ the values corresponding to M and S, respectively, after this change, then E(M′) > E(M) and E(S′) > E(S).

(g) None of the above.

2. A player draws with replacement cards from a full deck of 52 cards, until he draws for the first time the king of spades. Let M be the number of distinct cards drawn (between 1 and 52), N – the total number of drawings (including the last one) and X the number of times a queen is drawn.

(a) E(M) = 26.

(b) E(N) = 104.

(c) V (X) = 20.

(d) The probability for equal numbers of drawings of the kings of hearts and the king of diamonds is strictly between \frac{1}{3} and \frac{3}{5}.

(e) Every two out of the three random variables M, N and X are dependent.

(f) The correlation coefficient of any two of the three random variables M, N and X is positive. (Hint: Use your intuition. Do not try to calculate the correlation coefficients.)

(g) None of the above.

3. In some programming languages, when a program is run the garbage collector is activated each time when the available memory gets below some threshold. More precisely, the system checks periodically, say every unit time, whether the available memory is below the threshold, in which case the garbage collector is activated. Suppose the time T it takes the available memory to get below the threshold, after the garbage collector has been last activated, is distributed Exp(θ). Thus the time between consecutive activations of the garbage collector is S = ⌈T ⌉ (where ⌈t⌉ denotes the least integer not smaller than the real number t). Let Y = S − T the amount of time between the moment the memory level reached the threshold and the moment the garbage collector started taking care of the problem.

(a) The distribution of S is geometric.

(b) Y ∼ U(0, 1).

(c) The random variables S, Y are independent.

(d) The random variables T, Y are dependent, yet uncorrelated.

(e) E(Y) = \frac{1}{1−e^{−θ}} − \frac{1}{θ} .

(f) S = T + Y, which in our case implies that E(S) = E(T) + E(Y) and V (S) = V (T) + V (Y).

(g) None of the above.

4. Let X_{1}, X_{2}, …, X_{m} ∼ U[1, n] be independent. Put Y = min_{1≤i≤m} X_{i} and Z = max_{1≤i≤m} X_{i}.

(a) Z is one of the variables X_{i}, and in particular it is uniformly distributed.

(b) The limiting distribution of Y as m = n ⟶ ∞ is geometric.

(c) The limiting distribution of Y as m = n ⟶ ∞ is Poissonian.

(d) P_{Y,Z}(k, l) = (\frac{l−k+1}{n})^{m} , 1 ≤ k ≤ l ≤ n.

(e) P_{Y,Z}(k, l) < (\frac{l−k+1}{n})^{m} , 1 ≤ k ≤ l ≤ n.

(f) The minimum of numbers tends to be small, while the maximum tends to be large. In our case, this means that Y and Z have opposite tendencies. In particular, for every fixed n ≥ 2, if m is sufficiently large then ρ(Y, Z) < 0. However, if either m = 1 or n = 1, then ρ(Y, Z) = 1.

(g) None of the above.

5. A point (X, Y) is selected uniformly in the annular region consisting of all points whose distance from the origin is between 1 and 2. Put R = \sqrt{X^{2} + Y^{2}}, S = X^{2}+Y^{2} and Q = Y/X. (Note that Q is undefined at the points where X = 0, but as this set is of probability 0 we may ignore it.)

(a) R ∼ U(1, 2).

(b) S ∼ U(1, 4).

(c) The distribution of Q is symmetric about the point 0, and in particular E(Q) = 0.

(d) F_{R}(r) = \frac{r^{2}−1}{3} for 1 ≤ r ≤ 2.

(e) V (R) = \frac{13}{162} .

(f) The random variables X, R are independent.

(g) None of the above.

Solutions

1. We have M = 0 if and only if the sequence is sorted, which occurs with probability \frac{1}{n!} . If we had M ∼ B (m, \frac{1}{2}), then we would have P (M = 0) = 1/2^{m}. Similarly, the event {M = m} consists of a single point, whereas the event {S = n − 2} occurs for numerous orderings of the sequence (for example, 1, n, 2, n − 1, …, as well as the inverse ordering).

The event {S = 0} occurs if and only if the sequence is either increasing or decreasing. Hence P (S = 0) = \frac{2}{n!} ≠ \frac{1}{2^{n−2}} , and in particular S is not B (n − 2, \frac{1}{2})-distributed.

If M assumes the value l for some ordering, then it assumes the value m−l for the inverse ordering. Hence the distribution of M is symmetric about the point \frac{m}{2} , and in particular E(M) = \frac{m}{2} = \frac{n(n−1)}{4} . (A more “conventional” way to obtain this result is by expressing M in the form ∑_{1≤i<j≤n} M_{ij}, where M_{ij} = 1 if a_{i} > a_{j} and M_{ij} = 0 otherwise.)

For 1 ≤ i ≤ n − 2, define the random variable S_{i} by S_{i} = 1 if the three terms a_{i}, a_{i+1}, a_{i+2} do not form a monotonic subsequence and S_{i} = 0 otherwise. Clearly, S = ∑_{i=1}^{n−2} S_{i}. By symmetry, all 3! = 6 orderings of a_{i}, a_{i+1}, a_{i+2} are equi-probable. Since for 4 of these orderings the terms form a monotonic subsequence, we have P (S_{i} = 1) = \frac{4}{6} = \frac{2}{3}, and therefore E(S) = \frac{2(n−2)}{3} > \frac{n−2}{2} .

Ordering the sequence randomly, and then letting an additional random transposition act on the sequence, amounts to still having a random permutation, with each of the n! a priori possible orderings equiprobable.

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

2. We may assume that the experiment is held indefinitely, even though we care only about the part until the first king of spades has been drawn. To understand the distribution of M, we may ignore all drawings of cards which were drawn already. Thus, we just look at the 52! possible orders of drawing the cards. By symmetry, all these orders are equiprobable, and in particular the king of spades has equal probability of being any of the 52. Hence M ∼ U[1, 52], and therefore E(M) = 53/2. Obviously, N ∼ G(1/52), so that E(N) = 52. To understand the distribution of X, we may ignore all drawings of cards other than the king of spades and the 4 queens. The number of cards drawn out of these five cards until the king of spades is drawn for the first time is distributed G(1/5). Since X does not take into account the last drawing, we have E(X) = 5 − 1 = 4. When calculating the variance, the last drawing is immaterial, so that

V (X) = \frac{4/5}{(1/5)^{2}} = 20.

Denote by A the event in (d). First note that this event strictly contains the event B whereby the king of hearts and the king of diamonds do not appear at all before the first time the king of spades does. Now the event B occurs exactly if the king of spades is the first to appear among the three kings in question. By symmetry we have P (B) = 1/3, and therefore P (A) > 1/3. On the other hand, A is strictly contained in the event C, whereby the king of hearts and the king of diamonds appear together an even number of times before the first time the king of spades does. In other words, C is the event that the G(1/3)-distributed variable, counting the number of drawings of these three kings until the first occurrence of the king of spades, assumes an odd value. This latter probability is

\frac{1}{3} + (\frac{2}{3})^{2} · \frac{1}{3} + (\frac{2}{3})^{4} · \frac{1}{3} + … = \frac{1}{1 − (2/3)^{2}} · \frac{1}{3} = \frac{3}{5} .

Hence P (A) < 3/5. (We mention in passing that it is actually possible to calculate the probability of A precisely. In fact, note that this event happens if, for some n, we have exactly n drawings of each of the king of hearts and the king of diamonds before the first drawing of the king of spades. In other words, denoting the latter event by A_{n}, we have A = ⋃_{n=0}^{∞} A_{n}, where the union is disjoint. When calculating P (A_{n}) we may ignore all drawings of cards other than the three kings in question. Hence

P (A_{n}) = \frac{\binom{2n}{n}}{3^{2n+1}} ,

so that

P (A) = ∑_{n=0}^{∞} P (A_{n}) = ∑_{n=0}^{∞} \frac{\binom{2n}{n}}{3^{2n+1}} = \frac{1}{3} ∑_{n=0}^{∞} \binom{2n}{n} (\frac{1}{9})^{n} .

Now recall that

∑_{n=0}^{∞} \binom{2n}{n}x^{n} = \frac{1}{\sqrt{1 − 4x}} , −\frac{1}{4} < x < \frac{1}{4} ,

and therefore

P (A) = \frac{1}{3} \frac{1}{\sqrt{1 − 4/9}} ,

so that P (A) = 1/\sqrt{5}.)

A relatively large value of any of the three variables M, N and X means that there have been many drawings until the king of spades was drawn, and hence hints that each of the other two is also relatively large. Therefore all correlation coefficients should be positive.

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

3. For any positive integer m we have

P (S = m) = P (m − 1 < T ≤ m) = (1 − e^{−θm}) − (1 − e^{−θ(m−1)}) .

Therefore

P (S = m) = (e^{−θ})^{m−1} (1 − e^{−θ}) , m = 1, 2, …,

so that S ∼ G (1 − e^{−θ}). For Y we have

F_{Y} (y) = P (Y ≤ y) = ∑_{m=1}^{∞} P (m − y ≤ T ≤ m)

= ∑_{m=1}^{∞} ((1 − e^{−θm}) − (1 − e^{−θ(m−y)}))

= \frac{e^{θy} − 1}{e^{θ} − 1} ,  0 ≤ y < 1.

Consequently

f_{Y} (y) = \frac{θ}{e^{θ} − 1}e^{θy}, 0 ≤ y < 1,

and a routine calculation yields

E(Y) = \frac{θ}{e^{θ} − 1} ∫_{0}^{1} ye^{θy} dy = \frac{1}{1 − e^{−θ}} − \frac{1}{θ} .

Since

P (S = m, Y ≤ y) = P (m − y ≤ T ≤ m) = (e^{θy} − 1) e^{−mθ}
= P (S = m)P (Y ≤ y),

the variables S and Y are independent. Now

Cov(T, Y) = Cov(S − Y, Y) = Cov(S, Y) − Cov(Y, Y) = −V (Y), so that T and Y are negatively correlated. Since S and Y are independent

V (T) = V (S − Y) = V (S) + V (−Y) = V (S) + V (Y). Thus, only (a), (c) and (e) are true.

4. We have Y = k if and only if all X_{i}’s are at least k, but not all of them

are at least k + 1. Hence:

P (Y = k) = (\frac{n − k + 1}{n})^{m} − (\frac{n − k}{n} )^{m}
= (1 − \frac{k − 1}{n})^{m} − (1 − \frac{k}{n})^{m} .

As m = n ⟶ ∞ we have: P (Y = k) ⟶ e^{−(k−1)} − e^{−k} = (e^{−1})^{k−1} (1 − e^{−1}) , k = 1, 2, …, n. The number on the right hand side is exactly the probability of a G (1 − e^{−1})-distributed random variable to assume the value k. Hence the limiting distribution of Y as m = n ⟶ ∞ is geometric.

Similarly:

P (Z = l) = (\frac{l}{n})^{m} − (\frac{l − 1}{n})^{m} , l = 1, 2, …, n.

Obviously

P_{Y,Z}(k, l) ≤ P (k ≤ X_{1}, X_{2}, …, X_{m} ≤ l) = (\frac{l − k + 1}{n})^{m} , k ≤ l.

The inequality is usually strict. However, if k = l, for example, it is actually an equality.

For n ≥ 2, a large value of Y means that all X_{i}’s are large, and hence Z should be expected to be relatively large. Hence ρ(Y, Z) should be expected to be positive. In fact, one can show, for example, that for n = 2 we have Cov(Y, Z) = 1/2^{2m} > 0, so that ρ(Y, Z) > 0.

Thus, only (b) is true.

5. The random variable R clearly assumes values in the interval [1, 2]. For r in this range, the value of F_{R}(r) is the ratio between the area of the annular region consisting of all points whose distance from the origin is between 1 and r and the area of the region consisting of all points whose distance is between 1 and 2. Therefore

F_{R}(r) = \frac{π (r^{2} − 1^{2})}{π (2^{2} − 1^{2})} = \frac{r^{2} − 1}{3} , 1 ≤ r ≤ 2,

and hence:

f_{R}(r) = \frac{2r}{3} , 1 ≤ r ≤ 2.

Thus

E(R) = ∫_{1}^{2} r · \frac{2r}{3} dr = \frac{14}{9} ,

and

E (R^{2}) = ∫_{1}^{2} r^{2} · \frac{2r}{3} dr = \frac{5}{2} ,

so that:

V (R) = E (R^{2}) − E(R)^{2} = \frac{13}{162} .

The variable S assumes values in [1, 4], and for s in this interval we have

F_{S}(s) = P (S ≤ s) = P (R ≤ \sqrt{s}) = \frac{s − 1}{3} ,

which implies that S ∼ U(1, 4).

The angle between the positive x-axis and the line leading from a randomly chosen (X, Y) is clearly distributed U(0, 2π). Hence Q is Cauchy distributed. Its distribution is symmetric with respect to the point 0, but E(Q) does not exist.

The variables X, R are dependent as, for example, if X is close to 2, then R must be close to 2 as well.

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