Pre-Final Review Questions

Mark all correct answers in each of the following questions.

1. Let V = {v_{1}, v_{2}, …, v_{n}}, where n ≥ 3. Construct a random graph G = (V, E) by taking E as a random subset of size n of the set of all \binom{n}{2} unordered pairs (v_{i}, v_{j}) with i ≠ j. Let i + j be the weight of the edge (v_{i}, v_{j}) ∈ E. Denote by X_{i} the number of neighbors of the vertex v_{i}, by W_{i} the sum of weights of all edges one of whose endpoints is v_{i}, and by W the total sum of weights of all edges of G. For example, if n = 4 and E = {(v_{1}, v_{2}), (v_{1}, v_{4}), (v_{2}, v_{3}), (v_{3}, v_{4})}, then X_{2} = 2, W_{2} = 8 and W = 20.

(a) V (X_{1}) = \frac{2(n−3)}{n+1} .

(b) E(W_{i}) = \frac{n(n+1)+2(n−2)i}{n−1} .

(c) Calculating the variance of ∑_{i=1}^{n} X_{i} in two ways, one can show that Cov(X_{1}, X_{2}) = −V (X_{1})/n.

(d) E(W) = n(n + 1).

(e) A random edge, one of whose is endpoints is v_{i}, weighs on the average 1 more than a random edge one of whose endpoints is v_{i+1}. Therefore, E(W_{i+1} − W_{i}) = E(X_{1}).

(f) For sufficiently large n we have ρ(X_{i}, W) ≠ 0 for every i = 1, 2, …, n. (Hint: Do not calculate the correlation coefficient. Use intuition.)

(g) None of the above.

2. One of the ideas raised in order to increase the number of visitors in DisneyRandomWorld, Beer Sheva, was to contribute to EMACS (Enhancing Mice And Cats Solidarity) organization a certain amount of money, related to the number of visitors, as follows. Each day, a random minute will be chosen. All visitors arriving to DisneyRandom-World during that minute will participate at an experiment, in which the success probability is p (where 0 < p < 1). If at least one of them succeeds, DisneyRandomWorld will contribute $M to EMACS. Suppose the number of visitors arriving per minute is distributed P (λ). Let X denote the number of people arriving during the selected minute and Y the amount (0 or M) of dollars contributed that day.

(a) E(Y) = M (1 − e^{−λp}).

(b) For every λ > 0 and 0 < p < 1 we have σ(Y) > M (1 − e^{−λp}).

(c) The number of people arriving during the selected minute and succeeding in the experiment is distributed P (λp).

(d) Suppose after some statistical data has been gathered it turned out that the number of visitors arriving per minute is distributed P (λ/2) (and not P (λ) as supposed earlier), where the numbers of visitors in distinct minutes are independent. The park administration decided to select 2 random minutes each day and let all visitors arriving during those minutes to participate at the experiment (where again, $M will be donated if at least one of all those visitors succeeds). The combination of these changes makes no difference whatsoever for EMACS.

(e) The changes in (d) do not change the expected contribution to EMACS, but they do change the distribution of this contribution.

(f) Suppose the park administration decides to make the following change (with respect to the initial situation). Denoting q = 1 − p, if k people arrive during the selected minute, the first participates at an experiment with failure probability of \frac{q}{2}, the second – at an experiment with failure probability of \frac{q}{3}, ..., the kth – at an experiment with failure probability of \frac{q}{k+1} . If λ = 2 ln 2, q = 1/2 and M = 10000, then the expected increase in the contribution is less than $2000 per day.

(g) None of the above.

3. The numbers 1, 2, …, n are ordered randomly. Let X_{i} be 1 if i is to the left of 1 and 0 otherwise, 2 ≤ i ≤ n. Denote by X the number of numbers to the left of 1, and by S the sum of these numbers. For example, if n = 4 and the ordering is 2, 4, 1, 3, then X_{2} = X_{4} = 1, X_{3} = 0, X = 2 and S = 6.

(a) X ∼ B(n − 1, 1/2).

(b) V (X) = \frac{n^{2}−1}{12} .

(c) E(S) = \frac{(n+2)(n−1)}{2} .

(d) X_{i}, X_{j} are independent for i ≠ j.

(e) ρ(X_{i}, S) < ρ(X_{j}, S) for 2 ≤ i < j ≤ n.

(f) ρ(X, S) = ∑_{i=2}^{n} ρ(X_{i}, S).

(g) None of the above.

4. A coin is tossed consecutively until it falls on a head. If the number of tosses has been odd – the experiment is finished; otherwise – the coin is tossed again until the next head shows up. If the number of tosses at the second stage is odd – the experiment is finished; otherwise – we move on to the third stage. We continue similarly until, for the first time, the number of tosses at that stage is odd. Denote by X the total number of times the coin is tossed, by Y – the number of times it is tossed at the last stage, and by S – the number of stages. For example, if the sequence of results is T,T,T,H,T,H,T,T,H, then the experiment is finished after the ninth toss, with X = 9, Y = 3 and S = 3.

(a) The three random variables X, Y, S are dependent. Out of the three pairs of variables we can generate from them, exactly one pair consists of independent variables.

(b) V (S) = \frac{3}{4} .

(c) E(X) = 3.

(d) E(Y^{2}) = \frac{41}{9} .

(e) 0 < Cov(X, Y) < \frac{8\sqrt{2}}{3} .

(f) If the coin is not fair, but has a probability p (where 0 < p < 1) for a head, then the distribution of S remains the same.

(g) None of the above.

5. The 2-dimensional random variable (X, Y) is uniformly distributed in the intersection {(x, y) : x^{2} +y^{2} ≤ 1} ⋂{(x, y) : (1−x)^{2} +(1−y)^{2} ≤ 1}.

(a) The probability for (X, Y) to obtain a value within the circle of radius ε around the point (1/2, 1/2) is πε^{2} for sufficiently small ε > 0.

(b) E(X + Y) = 1.

(c) P (X < 1/2) = 1/2, yet X is not distributed U(0, 1).

(d) The distribution of Y − X is symmetric around 0.

(e) The random variables X and Y are dependent, yet uncorrelated.

(f) ρ(X, Y) < 0.

(g) None of the above.

Solutions

1. There are \binom{n}{2} potential edges, out of which n − 1 have v_{1} as one of their endpoints and \binom{n−1}{2} do not. As we choose n edges for E, we have X_{1} ∼ H (n, n − 1, \binom{n−1}{2}). In particular

E(X_{1}) = \frac{n(n − 1)}{\binom{n}{2}} = 2

and

V (X_{1}) = \frac{n(n − 1)\binom{n−1}{2}}{\binom{n}{2}2} (1 − \frac{n − 1}{\binom{n}{2} − 1}) = \frac{2(n − 3)}{n + 1} .

Put, for i ≠ j:

X_{ij} = \{ \begin{matrix}1, & (v_{i}, v_{j}) ∈ E, \\ 0, & otherwise. \end{matrix}

Then:

W_{i} = (1 + i)X_{i1} + … + (2i − 1)X_{i,i−1} + (2i + 1)X_{i,i+1} + … + (n + i)X_{in} .

Since E(X_{ij}) = P (X_{ij} = 1) = n/\binom{n}{2} = \frac{2}{n−1}, this implies:

\begin{aligned}E(W_{i}) & = \frac{2}{n−1} ((1 + i) + … + (2i − 1) + (2i + 1) + … + (n + i)) \\ & = \frac{n(n+1)+2(n−2)i}{n−1} . \end{aligned}

Hence:

E(W_{i+1} − W_{i}) = E(W_{i+1}) − E(W_{i}) = \frac{2(n − 2)}{n − 1} < 2 = E(X_{1}).

(The reason that the argument in (d) is false is that one of the possible contributions to both W_{i} and W_{i+1} is through the edge (v_{i}, v_{i+1}), which contributes an equal amount to both. Hence E(W_{i+1}) exceeds E(W_{i}) by slightly less than 2.)

As W = \frac{1}{2} ∑_{i=1}^{n} W_{i}, we have:

E(W) = \frac{1}{2} ∑_{i=1}^{n} E(W_{i}) = \frac{n^{2}(n + 1)}{2(n − 1)} + \frac{2(n − 2)}{2(n − 1)} ∑_{i=1}^{n} i

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

(Try to calculate E(W) without using E(W_{i})!)

Each edge contributes 2 to ∑_{i=1}^{n} X_{i}, so that

∑_{i=1}^{n} X_{i} = 2n, V (∑_{i=1}^{n} X_{i}) = 0.

On the other hand:

V (∑_{i=1}^{n} X_{i}) = ∑_{i=1}^{n} V (X_{i}) + ∑_{1≤i<j≤n} 2Cov(X_{i}, X_{j}).

By symmetry, all X_{i}’s have the same variance and all pairs X_{i}, X_{j} with i ≠ j have the same covariance. Hence

nV (X_{1}) + n(n − 1)Cov(X_{1}, X_{2}) = 0,

which yields

Cov(X_{1}, X_{2}) = \frac{−V (X_{1})}{n − 1} .

A large value of X_{i} means that a (relatively) large part of W is due to edges, one of whose endpoints is v_{i}. For small i, such edges tend to have a small weight, while for large i – a large weight. In other words, ρ(X_{i}, W) should be negative for small i and positive for large i. For i exactly in the middle of the range, namely i = \frac{n+1}{2} (which is possible only for odd n), we should have ρ(X_{i}, W) = 0.

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

2. Denote by S the number of people arriving during the selected minute and succeeding in the experiment. Clearly P_{X,S}(k, l) = \frac{λ^{k}}{k!} e^{−λ}·\binom{k}{l}p^{l}q^{k−l}, and therefore

P (S = l) = ∑_{k=l}^{∞} P_{X,S}(k, l) = (\frac{p}{q})^{l} e^{−λ} ∑_{k=l}^{∞} \frac{(λq)^{k}}{k!} \binom{k}{l}

= (\frac{p}{q})^{l} e^{−λ} · \frac{1}{l!} ∑_{k=l}^{∞} \frac{(λq)^{k}}{(k − l)!} = (\frac{p}{q})^{l} e^{−λ} · \frac{1}{l!}(λq)^{l} ∑_{j=0}^{∞} \frac{(λq)^{j}}{j!}

= \frac{(λp)^{l}}{l!} e^{−λ}e^{λq} = \frac{(λp)^{l}}{l!} e^{−λp} .

Consequently, S ∼ P (λp), and therefore

P (Y = M) = P (S > 0) = 1 − e^{−λp} .

Hence

E(Y) = M (1 − e^{−λp})

and

E(Y^{2}) = M^{2} (1 − e^{−λp}) .

Thus

V (Y) = M^{2}e^{−λp} (1 − e^{−λp}) ,

which implies that σ(Y) > M (1 − e^{−λp}) if and only if e^{−λp} > 1 − e^{−λp}, namely if and only if λp < ln 2.

Under the changes in (d) we have X = X_{1} + X_{2}, where X_{1}, X_{2} ∼ P (λ/2) are independent. Since the sum of independent Poisson distributed random variables is again a Poisson distributed random variable, whose parameter is the sum of the parameters of the addends, we have X ∼ P (λ), so nothing changes statistically with respect to the original assumptions.

Let Y′ be the contribution under the assumptions in (f). Then:

P (Y′ = 0 | X = k) = \frac{q}{2} · \frac{q}{3} · . . . · \frac{q}{k + 1} = \frac{q^{k}}{(k + 1)!} ,

and consequently

P (Y′ = M) = ∑_{k=0}^{∞} \frac{λ^{k}}{k!} e^{−λ} (1 − \frac{q^{k}}{(k + 1)!}) = 1 − e^{−λ} ∑_{k=0}^{∞} \frac{(λq)^{k}}{k!(k + 1)!} .

With the values λ = 2 ln 2, q = 1/2 and M = 10000, the expected original contribution is

E(Y) = M (1 − e^{−λp}) = 10000 (1 − e^{− ln 2}) = 5000,

while the expected contribution after the change is

E(Y′) = 10000 (1 − \frac{1}{4} ∑_{k=0}^{∞} \frac{(ln 2)^{k}}{k!(k + 1)!})

≤ 10000 (1 − \frac{1}{4} − \frac{1}{4} · \frac{ln 2}{2}) = 6634.

Hence the expected increase in the contribution is less than $1634.

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

3. The number has equal probabilities of being placed at each of the n possible places, whence X ∼ U[0, n − 1]. In particular, V (X) = \frac{n^{2}−1}{12} .

Each i ≥ 2 has the same probability of being placed before 1 as of being placed after it. Hence X_{i} ∼ B(1, 1/2). Since

S = ∑_{i=2}^{n} iX_{i},

we have

E(S) = ∑_{i=2}^{n} iE(X_{i}) = \frac{1}{2} ∑_{i=2}^{n} i = \frac{(n + 2)(n − 1)}{4} .

By symmetry, each of the 3! = 6 orderings of the numbers 1, i and j in the sequence is equi-probable, so that

P (X_{i} = X_{j} = 1) = \frac{2}{6} = \frac{1}{3} ≠ \frac{1}{4} = P (X_{i} = 1)P (X_{j} = 1),

and thus X_{i}, X_{j} are dependent.

Now:

Cov(X_{i}, S) = ∑_{j=2}^{n} jCov(X_{i}, X_{j}) = ∑_{j≠i} j · (\frac{1}{3} − \frac{1}{4}) + i · \frac{1}{4}

= \frac{(n + 2)(n − 1) + 4i}{24} .

Since the right hand side increases with i, while V (X_{i}) is the same for each i, this implies that ρ(X_{i}, S) increases with i. (Note that this is also intuitively clear.)

Since

Cov(X, S) = ∑_{i=2}^{n} Cov(X_{i}, S)

and

V (X) = \frac{n^{2} − 1}{12} > \frac{1}{4} = V (X_{i}), n ≥ 3,

we have

ρ(X, S) < ∑_{i=2}^{n} ρ(X_{i}, S), n ≥ 3.

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

4. When a coin is tossed until falling on a head for the first time, the probability for the number of tosses to be odd is

∑_{n=0}^{∞} \frac{1}{2^{2n+1}} = \frac{2}{3} .

Hence S ∼ G(2/3), and in particular E(S) = 3/2 and V (S) = 3/4. By the same considerations, if the coin has a probability of p for a head, then S ∼ G (\frac{1}{1+q}) .

The total number of tosses X is the number of tosses until the first time a head shows up at an odd-numbered toss. Hence, letting X′ denote the number of odd-numbered tosses, we have X = 2X′ − 1. Obviously, X′ ∼ G(1/2), so that

E(X′) = 2, V (X′) = 2

and therefore

E(X) = 2E(X′) − 1 = 3, V (X) = 2^{2} · V (X′) = 8.

To find the distribution of Y, we note that it is obtained from a G(1/2)- distributed variable, conditioned on the event that the number of tosses is odd. Consequently

P (Y = 2k − 1) = \frac{1/2^{2k−1}}{2/3} = \frac{3}{2^{2k}} ,

which implies that Y = 2Y′ − 1, with Y′ ∼ G(3/4). Thus

E(Y′) = \frac{4}{3} , V (Y′) = \frac{4}{9} ,

and

E(Y) = 2E(Y′) − 1 = \frac{5}{3} , V (Y) = 2^{2} · V (Y′) = \frac{16}{9} , E(Y^{2}) = \frac{41}{9} .

The number of stages in the experiment does not give any indication regarding the length of the last stage. (Note that it does give information regarding the length of any specific stage. For example, if it is known that S = 3, then the lengths of the first two stages must be even and that of the third must be odd. However, it does not give further information, and in particular gives nothing about the length of the last stage.) Hence Y, S are independent. On the other hand, the inequalities X ≥ S and X ≥ Y, for example, show that each of the two pairs X, S and X, Y consists of dependent variables.

The more tosses there are at the last stage, the more there are altogether. Hence, the larger Y is, the larger X should be, so that Cov(X, Y) > 0. On the other hand, they do not completely determine each other, and in particular they are not linear functions of each other, and thus

Cov(X, Y) < \sqrt{V (X)V (Y)} = \frac{8\sqrt{2}}{3} .

(It is actually pretty easy to calculate Cov(X, Y) directly using the observation that the two variables X − Y, Y are independent. Try it!)

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

5. Denote the intersection of the circles in the question by D. Since (X, Y) is uniformly distributed in D, its probability to obtain a value within some region is the area of that region divided by the area of D. This area is easily seen to be 1 − 2(1 − π/4) = π/2 − 1, and hence the probability of the event in (a) is \frac{πε^{2}}{π/2−1} .

The region D is symmetric with respect to the line x + y = 1 in the plane. Therefore, the distribution of the random variable X + Y is symmetric with respect to the point 1, and in particular (and since X + Y is bounded) E(X + Y) = 1. Similarly, since D is symmetric with respect to the line y = x, the distribution of Y − X is symmetric around 0.

The density function f_{X} of X at any point x is the height of the fiber of D lying above the point x. Hence f_{X} is symmetric with respect to the point 1/2, and in particular P (X < 1/2) = 1/2. Since f_{X} is not constant on [0, 1], X is not distributed U(0, 1).

Obviously, as X assumes a larger value, Y tends to become smaller. Hence ρ(X, Y) < 0.

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