Probability Theory

Exercises

1 Review Questions in Combinatorics

1. Car license plates consist of 5 digits and 5 letters. How many different license plates are possible

(a) if all digits precede the letters?

(b) if no two letters may be adjacent?

(c) if there is no restriction?

2. A certain lock has five buttons, numbered from 1 to 5. The combination of numbers that opens the lock is a sequence of seven numbers and is reset every week.

(a) How many combinations are possible if every button must be used at least once?

(b) Assume that the lock may also have combinations requiring to push first two buttons simultaneously and then the other five one at a time (still with the restriction that every button must be used). How many combinations does this add?

3. A computer with k processors receives n jobs.

(a) How many possibilities are there to assign the jobs?

(b) How many possibilities are there if each processor must be assigned at least one job?

(c) How many possibilities are there if exactly one processor has to remain idle?

4. A word over an alphabet Σ is a finite sequence of elements of Σ. Let |Σ| = r. How many words of length n are there over Σ

(a) if there are no restrictions?

(b) if adjacent letters must be distinct?

(c) if some specific σ ∈ Σ is not allowed to appear twice in a row?

(d) if each letter σ_{i} has to appear some prescribed number n_{i} of times (where ∑_{i=1}^{r} n_{i} = n)?

(e) if the word has to be a palindrome (i.e., the last letter is the same as the first, the second last the same as the second, etc)?

5. Solve the following recurrences by the method of generating functions: (a)

\begin{matrix}a_{n+2} − 3a_{n+1} + 2a_{n} = 0, n ≥ 0, \\ a_{0} = 1, a_{1} = 6. \end{matrix}

(b)

\begin{matrix}a_{n+2} − 2a_{n+1} + a_{n} = 2^{n}, n ≥ 0, \\ a_{0} = 1, a_{1} = 2. \end{matrix}

6. For fixed n, find the generating function of the sequence (\binom{n}{k})_{k=0}^{∞}.

7. Solve the following systems of recurrence relations by the method of generating functions: (a)

\begin{matrix}\begin{matrix}a_{n+1} = −2a_{n} − 4b_{n}, \\ b_{n+1} = 4a_{n} + 6b_{n}, \end{matrix} n ≥ 0 \\ a_{0} = 1, b_{0} = 0. \end{matrix}

(b)

\begin{matrix}\begin{matrix}a_{n+1} = 2a_{n} − b_{n} + 2, \\ b_{n+1} = −a_{n} + 2b_{n} − 1, \end{matrix} n ≥ 0 \\ a_{0} = 0, b_{0} = 0. \end{matrix}

8. Recall that Stirling’s formula provides the following approximation for n!:

n! ≈ \sqrt{2πn} (\frac{n}{e})^{n} .

Use the idea of the integral test (for testing the convergence of infinite series) to prove the following weak form of Stirling’s formula:

e (\frac{n}{e})^{n} ≤ n! ≤ e (\frac{n + 1}{e})^{n+1} .

9. Consider the middle binomial coefficients \binom{2n}{n}.

(a) What asymptotics does Stirling’s formula yield for them?

(b) Employing elementary means only, derive upper and lower bounds which are at most polynomially worse than the “precise” asymptotics found in the first part.

10. Show that the number C_{n} of binary trees on n vertices is

\frac{1}{n + 1}\binom{2n}{n}. Note that the C_{n}’s are the Catalan numbers. (Hint:

use the generating function f(x) = ∑_{n=0}^{∞} C_{n}x^{n}.)

11. Two queues Q_{1} and Q_{2} and a stack S are given. Initially, Q_{1} contains the integers 1, 2, …, n (with 1 at the head, 2 after it, and so forth). At each stage we either move the element at the head of Q_{1} to S, or the element at the top of S to Q_{2}. The process continues for 2n stages, at which time all integers are at Q_{2}. Let P_{n} be the number of possible permutations of 1, 2, …, n at the end.

(a) Find a recurrence relation satisfied by the sequence (P_{n}).

(b) Using generating functions, arrive at a closed-form formula for P_{n}.

12. A walk in the plane consists of a sequence of moves, each one from a point (l, m) to either (l + 1, m) or to (l, m + 1).

(a) Find the number of all walks going from (0, 0) to (l, m).

(b) Same, if a walk is not allowed to go above the main diagonal.

(c) Suppose we allow also to move directly from a point (l, m) to (l + 1, m + 1). Find the generating function

f(x, y) = ∑_{l=0}^{∞} ∑_{m=0}^{∞} W_{lm}x^{l}y^{m}

of the double sequence (W_{lm}), counting the number of such walks from (0, 0) to (l, m).

(d) Suppose P is a finite set of vectors (a_{i}, b_{i}), each having nonnegative coordinates, not both 0. Suppose a walk consists of moves from any point (l, m) to any of the points (l + a_{i}, m + b_{i}). Can you guess what the generating function will be in this general case? (Hint: Start by trying to find a connection between the possible moves in the preceding part and the form of the generating function there.)

13. Find the number of binary trees of n vertices, such that

(a) the left subtree is empty.

(b) the left subtree has only one vertex.

(c) the left subtree has two vertices.

(d) the left and right subtrees have the same number of vertices.

14. An r-ary tree is defined similarly to a binary tree, but each node has r subtrees instead of 2.

(a) Find a recurrence relation satisfied by the sequence (T_{r}(n))_{n=0}^{∞} counting the number of r-ary trees on n vertices.

(b) Use the recurrence to show that T_{r}(n) = \frac{1}{(r−1)n+1} \binom{rn}{n}.

(c) Find an equation satisfied by the generating function of the sequence.

15. The following method is used to sort a list:

    void BubbleSort(int [ ] array)
    {
       int temp;
       n = array.length;
       for (int i = 0; i < n - 1; i++)
          for (int j = 0; j < n - 1 - i; j++)
             if (array[j] > array[j+1])
             {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
             }
    }

Find the number of comparisons the method does when sorting a list of length n.

16. Consider the following two classes:

class Father
{
   public static int count= 0;
   public Father() {}
   public Father(int num)
   {
      for (int i = 0; i < num; i++)
      {
         new Father(i);
         count++;
      }
   }
}
class Son extends Father
{
   public Son(int num)
   {
      for (int i = 0; i < num; i++)
         new Father(i);
   }
}

The main method has:

Son x = new Son(n);
System.out.println(x.count);

(a) What is the value of x.count for any given n?

(b) Same if the class Father is changed to:

    class Father
    {
       public static int count = 0;
       public Father() {}
       public Father(int num)
       {
          for (int i = 0; i < num; i++)
             new Father(i);
          count++;
       }
    }

2 Elementary Probability Calculations

17. Consider an experiment having N possible outcomes, say {w_{1}, w_{2}, … w_{N}}, where it is known that each outcome w_{j+1} is twice as likely as outcome w_{j}, j = 1, 2, …, N−1. Find P (A_{k}), where A_{k} = {w_{1}, w_{2}, …, w_{k}}.

18. A fair coin is tossed n times. Find the probability that

(a) the sequence of results is palindromic.

(b) no two consecutive tosses produce the same result.

(c) no three consecutive tosses produce the same result.

(d) the total number of heads equal that of tails.

19. A full deck contains 52 cards. Find the probability that:

(a) the four aces are located consecutively in the deck.

(b) the locations of the aces in the deck form an arithmetic sequence of difference 7.

(c) the locations of the aces in the deck form an arithmetic sequence.

20. Forty books stand on a shelf, among them the three volumes of “the seventh column” by Alterman. Find the probability that the three volumes are arranged on the shelf according to the correct order (not necessarily adjacent to each other).

21. A number a is chosen randomly from the set {1, 2, … n}. Find the probability p_{n} that a^{2} mod 10 = 1. Find lim_{n⟶∞} p_{n}.

22. A number a is chosen randomly from {0, 1, 2, … 10^{n} − 1}. Find the probability p that a is a k-digit number, i.e., a = c_{k}10^{k−1} + c_{k−1}10^{k−2} + … + c_{1}, where 0 ≤ c_{i} ≤ 9 for i = 1, 2, … k − 1 and 0 < c_{k} ≤ 9.

23. Two numbers X and Y are chosen randomly with replacement from the set {1, 2, … n}, where n ≥ 4. Let

p_{2} = P (X^{2} − Y^{2} mod 2 = 0)

and

p_{3} = P (X^{2} − Y^{2} mod 3 = 0) .

Which of the probabilities p_{2} and p_{3} is bigger?

24. Two numbers X and Y are chosen randomly with replacement from the set {1, 2, … n}.

(a) Find the probability

Q_{n}(p) = P ((X^{p−1} − Y^{p−1}) mod p = 0) .

(Hint: Employ Fermat’s little theorem, which states that, for a prime p and b relatively prime to p we have b^{p−1} mod p = 1.)

(b) Find Q(p) = lim_{n⟶∞} Q_{n}(p).

(c) Find Q = lim_{p⟶∞} Q(p).

25. Let M = 2^{{1,2,...,n}}. Two elements A_{1} and A_{2} of M are chosen randomly (with replacement). Find the probability that A_{1} ⋂ A_{2} is empty.

26. An urn contains B blue and R red balls. A random sample of size n is drawn from the urn. Find the probability that the sample contains exactly b blue balls, if the sample is drawn:

(a) with replacement.

(b) without replacement.

27. An urn contains M_{i} balls of color i for i = 1, 2 …, N. A random sample of size n is drawn from the urn without replacement. Find the probability that

(a) the sample contains exactly n_{i} balls with number i for i = 1, 2 …, N.

(b) each of the colors is represented.

28. Itzik and Shmulik take a course with 3 possible grades: 0, 56 and 100. The probability to get 56 is 0.3 for Itzik and 0.4 for Shmulik. The probability that neither gets 0 but at least one gets 56 is 0.1. Find the probability that at least one gets 56 but neither gets 100.

29. Two numbers X_{1} and X_{2} are drawn randomly from the set {1, 2, …, n} without replacement. Find P (X_{2} > X_{1}).

30. Three numbers X_{1}, X_{2} and X_{3} are drawn randomly from the set {1, 2, …, n} without replacement. Find the probability that X_{1} < X_{2} < X_{3}.

31. X_{i}, i = 1, 2, …, n, are drawn randomly from the set {1, 2, …, N} without replacement. Denote by Y_{i} their order statistics:

min_{1≤i≤n} X_{i} = Y_{1} < Y_{2} < Y_{3} < … < Y_{n} = max_{1≤i≤n} X_{i}.

(a) Find P (Y_{m} ≤ M < Y_{m+1}).

(b) Find the limit of the probability in part (a) if N, M ⟶ ∞ with M/N ⟶ θ ∈ [0, 1] (for constant m and n).

32. Thirteen cards are drawn randomly from a full deck of 52 cards. Find the probability of getting:

(a) a full hand.

(b) no aces.

(c) no aces and exactly one king and one queen.

(d) one ace, one king, one queen, etc.

33. Find the probability that, out of a set of n people, at least two have their birthdays in the same month. (Assume the months are equally likely.)

34. A sequence of length n over {0, 1, 2} is chosen randomly. Find the probability that the sequence:

(a) starts with a 0.

(b) starts and ends with a 0, and contains exactly m additional 0’s.

(c) contains digit i exactly n_{i} times, i = 0, 1, 2.

35. A coin is tossed until the first time a head turns up. Find the probability that the coin is tossed

(a) an even number of times.

(b) exactly k times.

(c) at least k times.

36. A coin is tossed until the same result appears twice in a row. Find the probability that the coin is tossed

(a) less than 6 times.

(b) an even number of times.

37. A drug is assumed to be effective with unknown probability p. To estimate p, the drug is tried on n different partients. It is found to be effective on m of them. The method of maximum likelihood for estimating p suggests that we choose the value of p yielding the highest probability to the result actually obtained at the experiment. Show that the maximum likehood estimate for p is \frac{m}{n}.

38. Prove the following claims:

(a) For sufficiently small x ≥ 0 we have e^{−x−x^{2}} ≤ 1 − x ≤ e^{−x}.

(b) If (α_{n})_{n=1}^{∞} is a sequence of numbers in the open interval (0, 1), then ∏_{n=1}^{∞}(1 − α_{n}) = 0 if and only if ∑_{n=1}^{∞} α_{n} = ∞.

39. Numbers X_{1}, X_{2}, …, X_{k} are chosen randomly from the set {1, 2, … n} with replacement.

(a) Find the probability that all chosen numbers are distinct.

(b) Find the limit of the probability calculated in part (a) if n ⟶ ∞ and \frac{k}{\sqrt{n}} ⟶ θ for some 0 < θ < ∞. (Hint: Employ Exercise 38.a.)

40. Numbers X_{1}, X_{2}, …, X_{k} are chosen randomly without replacement from the set {1, 2, … 2n}.

(a) Find the probability that |X_{i} − X_{j}| ≠ n for i ≠ j.

(b) Find the limit of the expression you found if n ⟶ ∞ and \frac{k}{\sqrt{n}} ⟶ θ for some 0 < θ < ∞. (Hint: Employ Exercise 38.a.)

41. Let Ω = [0, 1] and suppose the probability of each sub-interval of Ω is equal to its length. Find

(a) P (⋃_{i=1}^{∞}[\frac{1}{2i+1}, \frac{1}{2i}]).

(b) the probabilty of the set of points whose infinite decimal expansion does not contain the digit 7.

(c) the probabilty of the set of points whose infinite hexadecimal expansion does not contain the digit D.

(d) the probabilty of the set of points whose infinite decimal expansion contains infinitely many occurrences of the digit 7. (Hint: Let (a_{n})_{n=1}^{∞} be a sequence of positive integers increasing arbitrarily fast. Our set contains the set of points whose expansion contains at least one 7 in the first a_{1} places, at least one 7 in the next a_{2} places, etc. Employ the idea of the proof of Exercise 38.a to show that the probabilty of the latter set may be made arbitrarily close to 1.)

42. Prove that for any events A_{1}, A_{2}, …, A_{n} we have P (⋃_{i=1}^{n} A_{i}) ≤ ∑_{i=1}^{n} P (A_{i}).

43. Given any sequence (A_{n})_{n=1}^{∞} of events, denote by lim sup_{n→∞} A_{n} the set of points in the sample space belonging to infinitely many of the sets A_{n}, and by lim inf_{n→∞} A_{n} the set of points belonging to all sets A_{n} from some place on.

(a) Let

A_{n} = \{ \begin{matrix}[0, 1 + 1/n],  n even, \\ [1/2, 2 + 1/n],  n odd. \end{matrix}

Find the sets lim sup_{n→∞} A_{n} and lim inf_{n→∞} A_{n}.

(b) Prove that, for any sequence (A_{n})_{n=1}^{∞} of events, lim sup_{n→∞} A_{n} and lim inf_{n→∞} A_{n} are also events.

44. For each of the following collections B of subsets of Ω, determine whether B is a σ-field:

(a) Ω = N, B is the collection of sets containing the number 1.

(b) Ω = N, B is the collection of all finite sets of even size and complements of such sets.

(c) Ω = N, B is the collection of all infinite sets and ∅.

(d) Ω = [0, 1], B is the collection of all finite sets and their complements.

(e) Ω = [0, 1], B is the collection of all sets which are at most countable and their complements.

45. A sequence (A_{n})_{n=1}^{∞} of events is increasing if A_{n} ⊆ A_{n+1} for each n and decreasing if A_{n} ⊇ A_{n+1} for each n. Prove that

(a) if (A_{n}) is increasing, then P (⋃_{i=1}^{∞} A_{i}) = lim_{n→∞} P (A_{n}).

(b) if (A_{n}) is decreasing, then P (⋂_{i=1}^{∞} A_{i}) = lim_{n→∞} P (A_{n}).

46. Let A be a finite set of size n. A subset R of A is chosen randomly. Find the probability that:

(a) |R| (the size of R) is even.

(b) |R| is divisible by 3; is 1 modulo 3. (Hint: Let ω = e^{2πi/3} be a root of unity of order 3. What is the value of 1 + ω^{k} + ω^{2k} as a function of k?)

(c) |R| is divisible by 4; is 1,2,3 modulo 4.

47. (Requires Algebra II) Let F be a finite field with q elements. A polynomial P (x) of degree d over F is chosen randomly, with the same probability to each such polynomial. Find the probability that:

(a) Some fixed a ∈ F is a root of P (x).

(b) Some fixed a_{1}, a_{2}, …, a_{k} ∈ F are roots of P (x).

48. (Requires Algebra II) Let F be a finite field with q elements. An n × n matrix A over F is chosen randomly, each entry being chosen with equal probabilities to all field elements, independently of all other entries. Find the probability that:

(a) A = A_{0} for some arbitrary fixed A_{0} ∈ M_{n}(F).

(b) A is invertible.

(c) det(A) = a for some arbitrary fixed a ∈ F.

(d) A is of rank 1.

(e) A is of rank n − 1.

(f) all eigenvalues of A belong to F and are distinct from each other.

(g) Av = 0 for some arbitrary fixed non-zero vector v ∈ F^{n}.

(h) Av = v for some arbitrary fixed non-zero vector v ∈ F^{n}.

(i) the sum of all eigenvalues of A (counting multiplicities) is a, where a ∈ F is arbitrary and fixed.

49. A finite sequence of length n consisting of distinct numbers is permuted randomly (all n! orderings being equi-probable). The numbers are read one by one, and put into a binary search tree T. Find the probability that:

(a) T is of height n − 1.

(b) the left subtree and the right subtree of T contain \frac{n−1}{2} nodes each (assuming n is odd).

(c) T is perfectly balanced (namely, contains all 2^{k} possible nodes at level k for each k ≤ h, where h is the height of the tree; we assume here that n = 2^{h+1} − 1).

50. We choose a random graph G = (V, E) on n vertices as follows. V is any set of size n (say, V = {1, 2, …, n}). For any two distinct v_{1}, v_{2} ∈ G, the edge (v_{1}, v_{2}) belongs to E with probability p and does not belong to it with probability q = 1 − p, where 0 < p < 1 is arbitrary fixed. Show that the probability of G being connected converges to 1 as n ⟶ ∞.

51. An (abstract) urn contains n left brackets “(” and n right brackets “)”.

(a) The brackets are drawn randomly from the urn without replacement. Let w denote the “word” consisting of the brackets, according to the order in which they were drawn. Find the probability that w is a legal expression in brackets. (An expression in brackets is legal if each prefix contains at least as many left brackets as right brackets, and altogether the same number of both types.)

(b) The same if the brackets are drawn with replacement. (Assume that altogether 2n are drawn, so the sequence is again of length 2n.)

52. Consider the problem of 2n people waiting to buy movie tickets. Find the probability that:

(a) all of the people with 100-shekel bills will have to wait for their change.

(b) exactly one person will have to wait for change.

53. The following algorithm has been proposed for selecting a random tree on n labeled vertices 1, 2, …, n out of the n^{n−2} such trees. First we choose a random vertex v_{1} (with equal probabilities 1/n to each vertex). Next we choose a random vertex v_{2} out of the remaining vertices and connect it to v_{1}. In general, for each 1 ≤ k ≤ n, we choose a random vertex v_{k+1} out of the remaining vertices and connect it to a random vertex out of those chosen already.

(a) Explain why each tree has a positive probability of being selected when using this algorithm.

(b) Show that for n ≤ 3 the algorithm assigns equal probabilities 1/n^{n−2} to all trees.

(c) Show in two ways that for sufficiently large n the algorithm does not assign equal probabilities to all trees:

(i) by finding a specific tree whose probability is too large. (ii) by finding a specific tree whose probability is too small.

(d) Prove the result of the preceding part without calculating the probability of any specific tree. (Hint: Show that, even after cancellation, the rational numbers you obtain cannot possibly have n^{n−2} in the denominator.)

54. A drunkard moves randomly along the x-axis. At time 0 he is at the point 0, and then at each time unit he moves either 1 distance unit to the right or 1 distance unit to the left. The probability for him to move right (independently of his current location and past movements) is p and to move left is q = 1 − p.

(a) Show that, if p > 1/2, then there is positive probability for him to stay from time 1 on in the positive x-axis.

(b) Show that, if p < 1/2, then the probability for him to stay from time 1 on in the positive x-axis is 0.

(c) The same as (b) for p = 1/2.

3 Conditional Probability

55. Let the probability p_{n} that a family has exactly n children be αp^{n} for n ≥ 1 . Suppose that all sex distributions of n children have the same probability. Find the probabily that a family contains exactly k boys.

56. Given N +1 urns, each containing N blue and white balls. The kth urn contains k blue and N −k white balls, k = 0, 1, 2, … N. An urn is chosen at random and a random ball is drawn from it n + 1 times with replacement. Let A = {the first n balls turn out to be blue} and B = {the (n + 1)’st ball is blue}.

(a) Find P (B | A).

(b) Show that for large N the probability in part (a) is approximatly \frac{n+1}{n+2}. (Hint: Use ∫_{0}^{1} x^{n}dx.)

57. Two players are playing a game until one of them is ruined. At each round one of them wins 1 dollar from the other. At the beginning of the game the first player has x dollars and the second has y dollars. The probabilities for the first and second players to win each round are p and q, respectively (where p + q = 1).

(a) Find the probabilities P_{1} and P_{2} for the first and the second player, respectively, to win the whole match. (Hint: Distinguish between the cases p = q = 1/2 and p ≠ q.)

(b) What happens to the probabilities you calculated in part (a) as y ⟶ ∞ (assuming x remains constant)?

58. An urn contains initially w white and b black balls. A ball is drawn at random. It is replaced and, moreover, another ball of the same color is put into the urn. The procedure is repeated indefinitely. Let P_{k}(n) be the probability of drawing k white (and n − k black) balls in the first n trials.

(a) Given that the second ball was black, what is the probability that the first was black?

(b) Prove the recurrence relation

P_{k}(n + 1) = P_{k}(n)\frac{b + n − k}{w + b + n} + P_{k−1}(n)\frac{w + k − 1}{w + b + n},

where we set P_{−1}(k) = 0.

(c) Using the preceding part (or directly) prove that:

P_{k}(n) = \binom{n}{k} · \frac{w + b − 1}{w + b + n − 1} · \begin{matrix}( & {w+b−2 \atop w−1} & ) \\ ( & {w+b+n−2 \atop w+k−1} & ) \end{matrix}.

59. Programming languages usually have random number generators. Such a generator provides numbers U ∈ [0, 1] with the property that P (U ≤ x) = x for every 0 ≤ x ≤ 1. In Java such a generator is implemented by the method Math.random().

(a) Show that the instruction

int k = (int) (n+1) * Math.random();

generates an integer between 0 and n, each such integer having the same probability \frac{1}{n+1} to be selected.

(b) The method choose(n,k) calculates the binomial coefficient \binom{n}{k}. Consider the method:

public static double Gen(int n)
{
   int k;
   do
      k = (int) ((n+1) * Math.random());
   while (Math.random() > choose(n,k) / choose(n,n/2));
   return k;
}

Prove that it generates an integer between 0 and n, such that the probability for any k in this range to be selected is \binom{n}{k}/2^{n}.

60. Let anyint be a (theoretical) type of integers, which includes all integers. Consider the following code fragment:

double x,y;
anyint k=1;
do
{
   x = Math.random();
   y = Math.random();
   k++;
}
while (Math.abs(x-y) > 1/k);

(a) Find the probability of entering an infinite loop with this code. Ignore rounding errors of the computer. (Hint: Consider a sample space Ω which is a unit square.)

(b) Same if the last line is changed to:

while (Math.abs(x-y) > 1/(k*k));

(c) Same if the last line is changed to:

while (Math.abs(x-y) > 1/Math.sqrt(k));

(d) Same if the last line is changed to:

while (Math.abs(x-y) > 1/(4*k*k));

(Hint: In the last part you may use Wallis’s formula

\frac{2 · 2 · 4 · 4 · . . . · 2n · 2n}{1 · 3 · 3 · 5 · . . . · (2n − 1) · (2n + 1)} ⟶_{n→∞} \frac{π}{2}

in your calculations.)

61. Let anyint be as in Problem 60. Suppose the method add(anyint k) adds the element k to a set and deleteRandom() deletes a randomly chosen element from it. Consider the following code fragment:

set mySet;
for (anyint k = 1; ; k++)
{
   mySet.add(2*k-1);
   mySet.add(2*k);
   mySet.deleteRandom();
}

Find the probability that after the execution of this (infinite) loop, starting with an empty set mySet,

(a) the number 1 belongs to mySet.

(b) mySet is empty.

62. Three people toss a die repeatedly until all three obtain the same result. Then they continue tossing their dice as many times as before.

(a) What is the probability that, in the course of the second stage of the experiment, they received three different results exactly k times?

(b) Assuming that at the second stage they received three different results k times, what is the probability that the first stage took n steps?

63. A coin of radius r ≤ a is dropped at random on an infinite grid (a system of straight lines parallel to the x-axis and the y-axis) with distance 2a between the parallel lines. Find the probability that the coin crosses

(a) none of the lines.

(b) at most one line.

64. A point P is selected at random in the circle S = {(x, y) : x^{2} + y^{2} ≤ R^{2}}. Find the probability that the interval of length R centered at P and parallel to the x-axis is contained in S.

65. A right angle with sides of length b and c is dropped at random on a plane divided by a system of parallel lines of distance 2a apart. Suppose b^{2} + c^{2} ≤ 4a^{2}. Find the probability that the angle crosses a line.

66. Solve Buffon’s needle problem if the length 2l of the needle is larger than the distance 2a between the lines.

67. Consider the version of Buffon’s needle problem (known as Laplace’s problem) where we have a grid with distance 2a between the parallel lines. Find the probability that the needle crosses none of the lines.

68. A semicirle of radius r ≤ a is dropped at random on a plane divided by a system of parallel lines of distance 2a apart. Find the probability that the semicirle meets

a. none of the lines.

b. exactly one of the lines.

c. two of the lines.

69. A parent particle splits at the end of its life into 0, 1 or 2 particles, with probabilities 1/4, 1/2 and 1/4, respectively. Starting with a single particle and denoting by X_{i} the number of partices in the i-th generation, find

a. P (X_{2} > 0).

b. P (X_{1} = 2|X_{2} = 1).

c. P (X_{1} = 1|X_{3} > 0).

70. An urn contains 5 balls, r of them red and the others green, the value of r being unknown. (The possible values of r between 0 and 5 are apriori equally reasonable.) Mr. X is to draw a ball at random from the balls in the urn, and you are required to guess the color of the ball he will draw. You are allowed to hold one of the following three experiments prior to making your guess:

(1.) Draw a single ball from the urn.

(2.) Draw three balls with replacement from the urn.

(3.) Draw three balls without replacement from the urn.

(The balls are returned to the urn after the experiment.) What is the probability of making the right guess if you

a. use option 1 and guess that Mr. X will draw a ball of the same color as you did?

b. use option 2 and guess that Mr. X will draw a ball of the same color as the majority among the three balls you have drawn?

c. use option 3 and guess that Mr. X will draw a ball of the same color as the majority among the three balls you have drawn?

71. A and B throw alternately a pair of dice. A wins if he scores a total of 6 before B scores a total of 7; otherwise B wins. If A starts the game, what is his probability of winning?

72. N players A_{1}, A_{2}, …, A_{N} toss a biased coin whose probability of a head is p. A_{1} starts the game, A_{2} plays next, etc. The first player to get a head wins. Find the probability of each of the players to be the winner.

73. An urn contains initially W white and B black balls. A random sample of size n is drawn. Find the probability that the jth ball in the sample is black, given that the sample contains b black balls. Consider sampling

(a) with replacement.

(b) without replacement.

74. The game of craps is played as follows. The player tosses repeatedly a pair of dice. If he scores a total of 7 or 11 at his first toss he wins, whereas if his total is 2, 3 or 12 he loses. In any other case the game continues until for the first time he scores a total equal to either his first total or to 7. In the first of these cases he wins, and in the second – loses.

(a) Find the player’s total probability of winning.

(b) Write a computer program estimating the same probability.

75. Construct examples of three events A, B and C

(a) which are pairwise independent but not independent.

(b) satisfying P (A ∩ B ∩ C) = P (A)P (B)P (C), without any two of them being independent.

76. For events A, B and C, prove or disprove:

(a) If A and B are independent, then P (A∩B|C) = P (A|C)P (B|C).

(b) If P (A) > P (B), then P (A|C) > P (B|C).

(c) If P (A) = 0, then P (A ∩ B) = 0.

(d) If P (A|B) ≥ P (A), then P (B|A) ≥ P (B).

(e) If P (B|\overline{A}) = P (B|A), then A and B are independent.

(f) If P (A) = a and P (B) = b, then P (A|B) ≥ \frac{a+b−1}{b}.

(g) If P (A) = P (B) > 0, then P (A|B) = P (B|A).

(h) If P (A|B) = P (B|A), then P (A) = P (B) .

(i) If P (A|B) = P (B|A), with P (A ∪ B) = 1 and P (A ∩ B) > 0, then P (A) > \frac{1}{2}.

(j) If P (A) = a and P (B) = b, then P (\overline{A} ∩ \overline{B}) ≥ 1 − a − b.

77. A coin with probability p for a head is tossed n times. Suppose A = {a head is obtained in the first toss} and B_{k} = {exactly k heads are obtained}. For which n and k are A and B_{k} independent?

78. It is known that each of four given people A, B, C and D tells the truth in any given instance with probability \frac{1}{3}. Suppose that A makes a statement, and then D says that C says that B says that A is telling the truth. What is the probability that A is actually telling the truth?

79. A coin is tossed twice. Consider the following events:

A : Head on the first toss.
B : Head on the second toss.
C : Same outcomes in the two tosses.

(a) Are A, B, C pairwise independent?

(b) Are A, B, C independent?

(b) Show that C is independent of A and B but not of A ∩ B.

80. Same as Problem 46 if the set R is selected by including each element of A in it with probability p and excluding it with probability 1 − p (distinct elements being independent).

4 Discrete Distributions

81. An urn contains 10 white balls, marked by the numbers 1, 2, …, 10, and 3 blue balls, marked by 11, 12, 13. Five balls are drawn randomly

(i) with replacement; (ii) without replacement. For each of the cases (i) and (ii) find the distribution of the

(a) number of white balls in the sample.

(b) minimum of the numbers marked on the balls.

(c) maximum of the numbers marked on the balls.

(d) number of stage at which the first white ball is drawn (6 if all balls in the sample are blue).

(e) number of balls marked by even numbers.

(f) number of balls marked by 2.

82. Same as the preceding problem, with the blue balls marked by 1, 2, 3.

83. The traffic flow at a certain street is such that the probability of a car passing during any given second is p. Moreover, different seconds are independent. Suppose that a pedestrian can cross the street only if no car is to pass during the next three seconds. Find the probability that pedestrian has to wait for exactly k = 0, 1, 2, 3, 4 seconds. (Regard seconds as indivisible time units.)

84. Two people toss a coin n times each. Let P_{n} be the probability that they score the same number of heads. Show that for large n we have P_{n} ≈ \frac{1}{\sqrt{πn}} .

85. A list of even length n is sorted using mergesort. The last step in the algorithm – merging the two sublists – may consume up to n − 1 comparisons. Find the distribution of the number of comparisons we actually save (namely, of the number k such that we need only n − 1 − k comparisons).

86. For Banach’s matchbox problem, considered in class:

(a) Find the probability that, at the moment when the first box is emptied (but not yet observed as being empty), the other contains exactly s matches, s = 1, 2, …, N.

(b) Find the probability that the first box emptied is not the one first found to be empty.

(c) Show that the probability in part (b) is approximately \frac{1}{2\sqrt{πn}} .

87. The following functions are probability functions of certain random variables. In each case find the parameter c and calculate the distribution function F:

(a)

p(x) = \{ \begin{matrix}c(N − x), & x = 0, 1, …, N − 1, (N ≥ 1), \\ 0, & otherwise. \end{matrix}

(b)

p(x) = \{ \begin{matrix}\frac{c}{x(x+1)}, & x = 1, 2, …, \\ 0, & otherwise. \end{matrix}

(c)

p(x) = \{ \begin{matrix}\frac{c}{x(x+1)(x+2)}, & x = 1, 2, …, \\ 0, & otherwise. \end{matrix}

(d)

p(x) = \{ \begin{matrix}\frac{c}{x(x+1)(x+3)}, & x = 1, 2, …, \\ 0, & otherwise. \end{matrix}

(e)

p(x) = \{ \begin{matrix}\frac{c}{x}, & x = 2^{k}3^{l}, k, l = 0, 1, …, \\ 0, & otherwise. \end{matrix}

(f)

p(x) = \{ \begin{matrix}\frac{c}{x^{2}} , & x = 2^{k}3^{l}, k, l = 0, 1, …, \\ 0, & otherwise. \end{matrix}

88. Suppose all rational numbers are ordered in some way, r_{1} being the first, r_{2} – the second, etc. Let X be a random variable assuming each rational value r_{k} with probability P (X = r_{k}) = 1/2^{k}. At which points is the distribution function F_{X} continuous and at which not?

89. M people are chosen at random out of n couples. Find the distribution of the number of couples within the M.

90. Recall that the probability function of the binomial distribution converges, as n → ∞ and p → 0 with np = λ constant, to the probability function of the Poissonian distribution with parameter λ. Show that the convergence is uniform over the set of non-negative integers.

91. Suppose a family of hypergeometric distributions H(n, a, b) is given, with a, b → ∞ such that a/b → C for some 0 < C < ∞ and n constant. Show that the distributions converge to a certain binomial distribution and specify its parameters.

92. Consider the distribution of the number of failures, obtained in a sequence of independent experiments with success probability p until r successes are obtained. Let r → ∞, p → 1 and r(1 − p) = λ. Show that the distributions converge to the P (λ) distribution.

93. Find the limiting distribution of the number of letters sent to their right destination in the lazy secretary problem.

94. Let G be a random graph as in Problem 50.

(a) How is the number of neighbors of any fixed vertex distributed?

(b) How is the size of E distributed?

(c) Show that the probability of G being a tree becomes very small as n becomes large.

5 Expectation

95. Find E(X^{2}) and E(X^{3}) if X is a random variable distributed according to the following distribution:

(a) X ∼ U[a, b].

(b) X ∼ B(n, p).

(c) X ∼ H(n, a, b).

(d) X ∼ G(p).

(e) X ∼ P (λ).

(f) X ∼ \overline{B}(p, r).

96. Find E(X) if:

(a) X = 2^{Y}, where Y ∼ U[a, b].

(b) X = 2^{Y}, where Y ∼ B(n, p).

(c) X = sin Y, where Y ∼ B(n, p). (Hint: Recall that sin θ = \frac{e^{iθ}−e^{−iθ}}{2i} .)

(d) X = 2^{Y}, where Y ∼ G(p).

(e) X = 2^{Y}, where Y ∼ P (λ).

(f) X = sin Y, where Y ∼ P (λ). (Hint: See (c).)

97. Consider a system consisting of n independent components, each of which either functions or fails, with functioning probabilities p_{i}, i = 1, 2, …, n. A system is serial if it works only if all its components function and parallel if it works if at least one of its components functions. Let

Y = \{ \begin{matrix}1, & the system works, \\ −1, & the system fails. \end{matrix}

Find E(Y) for a serial system and for a parallel system.

98. A random subset S of {1, 2, …, m} is chosen by selecting n consecutive times a random element of {1, 2, …, m} and letting S consist of all elements chosen at least once in the process. Let X = |S|. Find E(X) if:

(a) at each step, all the numbers have equal probabilities of being selected.

(b) the probabilities of 1, 2, …, m to be selected are p_{1}, p_{2}, …, p_{m}, respectively.

99. An urn contains N balls enumerated from 1 to N. Let X be the largest number drawn in n drawings, when random sampling with replacement is used.

(a) Find E(X) as a function of N and n.

(b) Approximate E(X) for large N and constant n.

(c) Approximate E(X) for large n and constant N.

100. A royal family has children until it has a boy or until it has three childen, whichever comes first. Find the expected number of boys and the expected number of girls in the family.

101. A multiple-choice exam is given. A problem has four possible answers, of which exactly one is correct. A student is allowed to mark any subset of the possible answers. The student receives 3 points if the correct answer is marked, and is penalized by 1 point for each wrong answer. Suppose the student marks his answers randomly, where each possible answer is marked with some probability. (Distinct answers are not necessarily marked with the same probability.) Show that the expected score of the student is 0.

102. A coin is tossed until the first time a head turns up. If this occurs at the nth, then the player wins 2^{n}/n dollars if n is odd, and loses 2^{n}/n dollars if n is even. Let X be the amount the player wins. Find E(X) if it exists.

103. A number of people are to pass a blood test each. The test may be held in one of two ways:

(1) Each person is tested separately.

(2) The group is divided into groups of size k each. (Assume the whole group to be large, so that we may neglect the inaccuracy due to the fact that the total size is not exactly divisible by k.) The blood samples of the people in each of these groups are pooled and analyzed togeter. If the test is negative, this one test shows that the result is negative for each of the k people, and the test suffices. If it is positive, each of the k people must be tested separetely, in which case k + 1 tests are required in all for the k people.

Assume that the probability p that the test yields a positive result for a person is the same for all people and that distinct people are independent.

(a) What is the expected value of the number X of tests carried out per person under plan (2)?

(b) For small p, show that the value of k which will minimize E(X) is approximately \frac{1}{\sqrt{p}} .

104. There are two envelopes. In one of them we place an amount X of money. The distribution of X is discrete and is known. In the second envelope we put twice the amount actually put in the first envelope. You are given one of these envelopes randomly and, after opening it and seeing the amount x in it, may decide to switch to the other envelope. Your prize is the amount in the envelope you have chosen.

(a) If your envelope containts an amount x, what is your expected prize if you switch to the other envelope.

(b) For which values of x should you switch if

(i)

p(x) = \{ \begin{matrix}\frac{1}{3} (\frac{2}{3})^{k−1} , & x = 2^{k}, k = 1, 2, …, \\ 0, & otherwise. \end{matrix}

(ii)

p(x) = \{ \begin{matrix}\frac{2}{3} (\frac{1}{3})^{k−1} , & x = 2^{k}, k = 1, 2, …, \\ 0, & otherwise. \end{matrix}

105. Consider random variables as in Problem 87.

(a) Which of these variables have finite expectation? Find their expectation.

(b) Same for the squares of these variables.

106. Let G be a random graph as in Problem 50. Let v_{1}, v_{2} be arbitrary fixed vertices. Show that the expected value of the distance between v_{1} and v_{2} converges to 2 − p as n ⟶ ∞ (where we take the distance as n if there exists no path between the two vertices).

107. We select n people randomly.

(a) Find the expected number of people whose birth date is distinct from that of all others.

(b) For which value(s) of n is this expected number maximal?

(c) Estimate the expected number for the value of N found in (b) without using a calculator.

108. In Problem 89, find the expected number of couples within the M.

109. Show that, in the problem of 2n people waiting to buy movie tickets, the expected number of people who will have to wait for change is n/2.

110. Two algorithms, randomPerm1 and randomPerm2, have been proposed for generating random permutations of 1, 2, …, n. The first of these consists of choosing n random integers between 1 and n until the chosen n-tuple forms a permutation. The second algorithm consists of n steps; at each step we repeatedly choose a random integer between 1 and n until the chosen integer is distinct from all those chosen earlier. Find the expected number of selections of random integers for each of these algorithms.

111. Find the expected number of letters sent to their right destination in the lazy secretary problem.

112. Recall that the diameter of a graph is the maximum of all distances between two vertices of the graph. Let T be a random tree, constructed according to the algorithm in Problem 53. Prove that for n ≥ 2 the expected value of the diameter of T is at least 2(1 + 1/2 + 1/3 + … + 1/(n − 1)) − 1.

6 Continuous Distributions

113. Let U ∼ U(0, 1). Find the density function and the distribution function of the following random variables:

(a) X = 3U + 2.

(b) X = U^{3}.

(c) X = − ln U.

(d) X = \frac{1}{U+1}.

(e) X = ln U + 1.

(f) X = |U − \frac{1}{2}|.

(g) X = (U − \frac{1}{2})^{2}.

114. Let f_{1}(x) and f_{2}(x) be density functions and θ_{1}, θ_{2} constants.

(a) Find a sufficient condition on θ_{1} and θ_{2} for the function θ_{1}f_{1}(x)+ θ_{2}f_{2}(x) to be a density function.

(b) Is the condition found in (a) always necessary?

(c) Prove that, for every θ_{1} and θ_{2} not satisfying the condition, there exist densities f_{1}(x) and f_{2}(x) such that the function θ_{1}f_{1}(x) + θ_{2}f_{2}(x) is not a density function.

115. For what values of the parameters a, b is the function

f(x) = \{ \begin{matrix}ax + b, & −1 ≤ x ≤ 1, \\ 0, & otherwise, \end{matrix}

a density function?

116. The following functions are density functions of certain random variables. In each case find all possible values of the parameter c and calculate the distribution function F:

(a)

f(x) = \{ \begin{matrix}cx^{3}, & 3 ≤ x ≤ 5, \\ 0, & otherwise. \end{matrix}

(b)

f(x) = \{ \begin{matrix}c(e^{−2x} + e^{−3x}), & x ≥ 0, \\ 0, & otherwise. \end{matrix}

(c)

f(x) = c(e^{−2|x|} + e^{−3|x|}), −∞ < x < ∞.

(d)

f(x) = \{ \begin{matrix}0, & x < −1, \\ −2cx, & −1 ≤ x ≤ 0, \\ 3ce^{−x}, & x > 0. \end{matrix}

(e)

f(x) = \{ \begin{matrix}\frac{c−1}{(1+x)^{c}} , & x > 0, \\ 0, & otherwise. \end{matrix}

117. Suppose that the distribution function F_{X}(x) of a certain random variable X is strictly increasing on the whole real line. Let U ∼ U(0, 1).

(a) Show that the random variable W = F_{X}(X) is distributed U(0, 1).

(b) Show that the random variable Y = F_{X}^{−1}(U) is distributed according to the distribution function F_{X}(x).

(c) The function Math.random() provides values distributed U(0, 1). Use part (b) to write a function providing values distributed Exp(λ).

118. Let X be the amount of bread (measured in hundreds of kilograms) a certain bakery sells a day. It is known that X has the density function:

f(x) = \{ \begin{matrix}cx, & 0 ≤ x < 3, \\ c(6 − x), & 3 ≤ x < 6, \\ 0, & otherwise. \end{matrix}

(a) Find the value of c.

(b) Find the probability of the events A = {X > 3} and B = {1.5 ≤ X ≤ 4.5}. Are A and B independent?

119. A mirror is mounted on a vertical axis, and is free to revolve about that axis. The axis of the mirror is at a distance of 1 meter from a straight wall of infinite length. A pulse of light is sent to the mirror, and the reflected ray hits the wall. Suppose that the angle between the reflected ray and the line perpendicular to the wall and running through the axis of the mirror is distributed U (−\frac{π}{2}, \frac{π}{2}). Let X be the distance between the point on the wall hit by the reflected ray and the point on the wall closest to the axis of the mirror. Find the density function and the distribution function of X.

120. Find the expectation of random variables distributed on [−1, 1] with the following density functions:

(a) f(x) = |x|.

(b) f(x) = 1 − |x|.

(c) f(x) = \frac{3}{2}x^{2}.

(d) f(x) = \frac{4}{3}(1 − x^{2}).

(e) f(x) = \frac{π}{4} cos(πx/2).

(f) f(x) = \frac{x+1}{2}.

(g) f(x) = \frac{3(x+1)^{2}}{8} .

121. The lifetime of the super light bulb, measured in hours, is a random variable T with density function

f(t) = 0.01te^{−0.1t} .

Find the expected lifetime of the bulb.

122. A point (U_{1}, U_{2}) is selected uniformly in the square [0, 1] × [0, 1]. Find:

(a) E(U_{1}^{2} + U_{2}^{2}).

(b) E((U_{1} + U_{2})^{2}).

(c) E(− ln U_{1} − ln U_{2}).

(d) E(max(U_{1}, U_{2})).

(e) E(min(U_{1}, U_{2})).

123. Find E(X^{n}) for any positive integer n if:

(a) X ∼ U(a, b).

(b) X ∼ Exp(λ).

(c) X ∼ Γ(λ, α).

124. Find E(X) (in case it exists) if X is distributed according to any of the distributions defined in question 116.

125. Let U ∼ U(0, 1) and Z_{λ} = \frac{U^{λ}−(1−U)^{λ}}{λ} , λ > 0. Find:

(a) E(Z_{λ}^{k}), k = 1, 2, 3, 4.

(b) Two parameter values λ_{1} ≠ λ_{2}, for which all four expectations calculated in (a) are equal.

7 Variance and Covariance

126. Find V (X) (if it exists) if X is distributed according to any of the distributions defined in question 96.

127. Find the variance of a \overline{B}(p, r) random variable.

128. An urn contains n balls of l distinct weights – n_{1} of weight x_{1} each, n_{2} balls of weight x_{2}, and so forth. Let m = ^{\frac{∑_{j=1}^{l} n_{j}x_{j}}{n}} be the mean ball weight. We select r balls randomly without replacement. (Assume that balls of different weights still have the same probability of being selected.) Let W be the total weight of the selected balls. Find E(W) and V (W).

129. Find E(X) and V (X) if X is distributed according to the following probability functions:

(a)

p(x) = \{ \begin{matrix}\frac{e^{−λ}λ^{x}}{x!(1 − e^{−λ})}, & x = 1, 2, …, (λ > 0), \\ 0, & otherwise. \end{matrix}

(b)

p(x) = \{ \begin{matrix}\frac{(1 − p)^{x}}{−x ln p} , & x = 1, 2, …, (0 < p < 1), \\ 0, & otherwise. \end{matrix}

(c)

p(x) = \{ \begin{matrix}\binom{n}{x}\frac{Γ(α + β)Γ(x + α)Γ(n + β − x)}{Γ(α)Γ(β)Γ(n + β + α)}, & x = 0, …, n, \\ 0, & otherwise, \end{matrix}

(α and β positive parameters).

130. Let X be a random variable with E(X) = μ and V (X) < ∞. Show that the function v(s) = E ((X − s)^{2}) assumes its minimum at the point s = μ.

131. Let X and Y be two random variables having finite variances. Assume that all four variables X, Y, X + Y and X − Y have the same distribution. Show that P (X = Y = 0) = 1.

132. Find V (X) (if it exists) if X is distributed according to any of the distributions defined in questions 116 and 120.

133. Find V (e^{U} + e^{1−U}), where U ∼ U(0, 1).

134. Find the covariance of the number of ones and the number of sixes in n tosses of a die.

135. An urn contains a white balls and b black balls. Suppose m random balls are taken out of the urn without replacement, and then n more are taken out, where m + n ≤ min(a, b). Let X and Y denote the number of white balls in the first batch and in the second batch, respectively.

(a) Calculate V (X) and V (Y).

(b) Calculate Cov(X, Y).

(c) Is Cov(X, Y) positive or negative? Why should you have expected it without performing any calculations?

136. Find the variance of the number of letters sent to the right destination in the lazy secretary problem.

137. Let X = e^{U} + c (U − \frac{1}{2}), where U ∼ U(0, 1) and c is a constant.

(a) Find E(X).

(b) Find V (X).

(c) For which value of c is V (X) minimal?

(d) Same for Y = e^{1−U} + c (U − \frac{1}{2}).

138. An coin is tossed n times. A change is said to occur when two consecutive results are different. Let S_{n} denote the total number of changes in the sequence. For example, if a coin is tossed for 5 times and the result is HTTHH, then S_{5} = 2. Find E(S_{n}) and V (S_{n}) if the coin

(a) is fair.

(b) has probability p for a head.

139. Same as the preceding question for

(a) a fair die.

(b) a die with probabilities p_{1}, p_{2}, …, p_{6} for the outcomes 1, 2, …, 6, respectively.

8 Multi-Dimensional Distributions

140. The probability function of (X, Y) is given by the following table:

\begin{matrix}[figure: y; x] & 1 & 2 & 3 \\ 1 & 1/12 & 1/6 & 1/12 \\ 2 & 1/6 & 1/4 & 1/12 \\ 3 & 1/12 & 1/12 & 0 \end{matrix}

Find:

(a) the probability for X to be odd.

(b) the probability for XY to be odd.

(c) P (X + Y ≥ 4).

(d) E(X + Y).

(e) V (X + Y).

141. Two cards are drawn without replacement from a full deck. Let X be the number of aces and Y the number of kings. Find:

(a) the probability function of (X, Y).

(b) P (X ≥ Y).

(c) Cov(X, Y).

142. A company manufactures items, each of which may have 0, 1, or 2 defects with probabilities 0.7, 0.2 and 0.1, respectively. If the item has 2 defects, the inspectors notice it and the item is replaced by one without defects before delivery. Let X be the original number of defects in an item produced and Y the number of defects in the corresponding delivered item. Find:

(a) the probability function of (X, Y).

(b) E(X − Y).

(c) V (X − Y).

143. Consider a sample of size 2 drawn without replacement from an urn containing three balls, numbered 1, 2 and 3. Let X be the smaller of the drawn numbers and Y the larger. Find:

(a) the probability function of (X, Y).

(b) E(X + Y).

(c) V (X + Y).

144. A die is tossed n times. Let X_{1} and X_{2} be the number of 1’s and of 2’s, respectively. Find:

(a) the probability function of (X_{1}, X_{2}).

(b) Cov(X_{1}, X_{2}).

145. A point (U_{1}, U_{2}) is selected uniformly in [0, 1] × [0, 2]. Find the distribution function and the density function of the following random variables:

(a) U_{1}.

(b) U_{2}.

(c) X = \sqrt{U_{2}/2}.

(d) V = max(U_{1}, U_{2}).

(e) Y = min(U_{1}, U_{2}).

(f) W = U_{1} · U_{2}.

9 Independence

146. Let g and h be non-decreasing functions. Prove that for any random variable X we have

Cov(g(X), h(X)) ≥ 0.

(Hint: Let X and Y be independent identically distributed random variables. Consider the non-negative random variable (g(X) − g(Y))(h(X) − h(Y)).)

147. Let U ∼ U(0, 1) and let h be a monotonic function. Prove that

Cov(h(U), h(1 − U)) ≤ 0.

(Hint: Use the result of question 146.)

148. Consider the following three methods:

     public static double X()
     {
        double res = 0;
        double v1, v2;
        for (int i = 0; i < 100; i++)
        {
          v1 = 2*Math.random() - 1;
          v2 = 2*Math.random() - 1;
          if (v1*v1 + v2*v2 <= 1)
              res++;
         }
         return res/100;
     }

public static double Y()
{
double res = 0;
double v;
for (int i = 0; i < 100; i++)
{
   v = Math.random();
   res += Math.sqrt(1-v*v);
 }
 return res/100;
}

public static double Z()
{
double res = 0;
double v1, v2;
for (int i = 0; i < 50; i++)
{
   v1 = Math.random();
   v2 = 1 - v1;
   res += Math.sqrt(1 - v1*v1) + Math.sqrt(1 - v2*v2);
}
return res/100;
}

The main method has:

double X=X(), Y=Y(), Z=Z();

Find:

(a) E(X), E(Y) and E(Z).

(b) V (X), V (Y) and V (Z).

149. Let X_{i}, i = 1, 2, …, m, be independent random variables distributed according to one of the following possibilities:

(a) X_{i} ∼ P (λ_{i}).

(b) X_{i} ∼ B(n_{i}, p).

(c) X_{i} ∼ G(p).

Let Y = ∑_{i=1}^{m} X_{i}. Prove that, correspondingly:

(a) Y ∼ P (∑_{i=1}^{m} λ_{i}).

(b) Y ∼ B (∑_{i=1}^{m} n_{i}, p).

(c) Y ∼ \overline{B}(n, p).

150. Let X_{i}, i = 1, 2 be independent random variables. Find the distribution of X_{1} + X_{2} if:

(a) X_{i} ∼ U[a_{i}, b_{i}], i = 1, 2.

(b) X_{i} ∼ U(a_{i}, b_{i}), i = 1, 2.

151. Show that for any k there exist k dependent random variables, any k − 1 of which are independent.

152. A die is rolled twice. Let X_{i} denote the outcome of the ith roll, and put S = X_{1} + X_{2} and D = |X_{1} − X_{2}|.

(a) Show that E(SD) = E(S)E(D).

(b) Are S and D independent?

153. Show that, if X and Y are random variables assuming only two values each, and E(XY) = E(X)E(Y), then X and Y are independent.

154. Let X and Y be discrete random variables, each assuming only finitely many possible values. Let P_{ij} = P_{X,Y} (x_{i}, y_{j}). Show that X and Y are independent if and only if the matrix of probabilities P = (P_{ij}) is of rank 1.

155. A tetrahedron, with the numbers 1, 2, 3 and 4 marked on its faces, is tossed twice. Let X be the smaller of the two outcomes and Y the larger. Find ρ(X, Y).

156. Let X ∼ U[−k, k] and Y = X^{2}.

(a) Find ρ(X, Y).

(b) Explain intuitively the result of part (a) .

157. Let X and Y be independent identically distributed random variables, and put S = X + Y and D = X − Y. Find:

(a) ρ(X, S).

(b) ρ(Y, D).

(c) ρ(S, D).

158. Suppose that the probability function of (X_{1}, X_{2}, X_{3}) is trinomial with parameters n and (p_{1}, p_{2}, p_{3}). Find

(a) E(X_{1}).

(b) V (X_{1}).

(c) ρ(X_{1}, X_{2}).

159. Let X ∼ P (λ). After a value for X is selected randomly, a fair coin is tossed X times. Let Y be the number of heads in these tosses. Find:

(a) the probability function of (X, Y).

(b) E(Y) and V (Y).

(c) ρ(X, Y).

160. A fair die is tossed twice. Let X be the number of sixes in the two tosses and Y the number of even outcomes.

(a) Find the probability function of (X, Y).

(b) Are X and Y independent?

(c) Find ρ(X, Y).

161. Let X, Y_{1}, …, Y_{k}, Z_{1}, …, Z_{k} be independent random variables, each with mean 0 and finite variance σ^{2}. The random variable N is independent of all these variables, and its probability function is given by

p_{N}(j) = \{ \begin{matrix}p_{j}, & x = 1, 2, …, k, \\ 0, & otherwise, \end{matrix}

(where p_{j} ≥ 0, ∑_{j=1}^{k} p_{j} = 1). Define random variables U, V by:

U = X + ∑_{j=1}^{N} Y_{j}, V = X + ∑_{j=1}^{N} Z_{j} .

(a) Show that N, UV are not independent, yet they are uncorrelated.

(b) Find ρ(U, V).

162. Let X ∼ U(0, 1). Find:

(a) ρ(X^{2}, X^{3}).

(b) ρ (X, e^{X}).

(c) ρ(sin 2πX, cos 2πX).

(d) ρ(− ln X, ln^{2} X).

163. Let X and Y be independent random variables with E(X) = E(Y) = 0 and V (X) = V (Y) = 1. Let −1 ≤ c ≤ 1 and Z = cX + \sqrt{1 − c^{2}} · Y. Find:

(a) ρ(X, Z).

(b) ρ(Y, Z).

164. Let X be uniformly distributed in the triangle with vertices (0, 0), (0, 2) and (1, 0). Find:

(a) the density functions of X and Y.

(b) ρ(X, Y).

165. Let (X, Y) be uniformly distributed in the square with vertices (1, 0), (0, 1), (−1, 0) and (0, −1).

(a) Find ρ(X, Y).

(b) Are X and Y independent? uncorrelated?

(c) Calculate P (XY > 0).

(d) Calculate P (X^{2} + Y^{2} < \frac{1}{4}).

10 Normal Distribution

166. Calculate ∫_{0}^{∞} e^{−x^{2}}dx by the following steps:

(a) Prove that:

(1 + x)e^{−x} ≤ 1, −∞ < x < ∞.

(b) Using part (a) show that

(1 − x^{2}) ≤ e^{−x^{2}}, 0 < x < 1,

and

e^{−x^{2}} ≤ \frac{1}{(1 + x^{2})}, x > 0.

(c) Show that for any positive integer n

∫_{0}^{1}(1 − x^{2})^{n}dx\frac{2n!!}{(2n + 1)!!} ,

and

∫_{0}^{∞} \frac{1}{(1 + x^{2})^{n}} dx = \frac{(2n − 3)!!}{(2n − 2)!!} · \frac{π}{2} .

(d) Using parts (b) and (c) prove that

\sqrt{n}\frac{2n!!}{(2n + 1)!!} ≤ ∫_{0}^{∞} e^{−x^{2}}dx ≤ \sqrt{n}\frac{(2n − 3)!!}{(2n − 2)!!} \frac{π}{2} .

(e) Using part (d) and Wallis’s formula \frac{2·2·4·4·...·2n·2n}{1·3·3·5·...·(2n−1)·(2n+1)} ⟶_{n→∞} \frac{π}{2} ,

show that

∫_{0}^{∞} e^{−x^{2}}dx = \frac{\sqrt{π}}{2} .

167. Let X be a random variable with density function f_{X}(x) = c(2e^{−x^{2}} + 3e^{−2x^{2}}), −∞ < x < ∞.

Find:

(a) the value of c.

(b) E(X) and V (X).

168. Show that the even-order moments of the standard normal distribution can be expressed in terms of the gamma function as follows:

E (Z^{2k}) = \frac{2^{k−1}}{\sqrt{π}} · Γ (k + \frac{1}{2}) .

169. Find E(X^{3}) if X ∼ N(μ, σ^{2}).

11 Limit Theorems

170. Consider the following three methods:

public static double X()
{
double res = 0;
double v;
for (int i = 0; i < 100; i++)
{
   v = 20 * Math.random();
   res += v;
 }
 return res/100;
}

public static double Y()
{
double res = 0;
double v;
for (int i = 0; i < 100; i++)
{
   v = 20 * Math.random();
   if (v < 5)
         res++;
 }
 return res/100;
}

public static double Z()
{
double res = 0;
double v = 10;
for (int i = 1; v > 5; i++)
{
   v = 20 * Math.random();
   res += i;
}
return res;
}

The main method has:

double X=X(), Y=Y(), Z=Z();

(a) Using Markov’s Inequality find an upper bound for the probabilities P (X > 10), P (Y > 0.8) and P (Z > 20).

(b) Using Chebyshev’s Inequality find an upper bound for the probabilities P (|X − E(X)| > 0.2), P (|Y − E(Y)| > 0.2) and P (|Z − E(Z)| > 0.2).

171. Let g be a positive increasing function. Prove that for any random variable X:

P (|X| ≥ t) ≤ \frac{E(g(|X|))}{g(t)} .

172. Let X be a non-negative random variable. What is the best upper bound you can give for P (X ≥ a) if it is known that:

(a) E(X) = 20.

(b) E(X) = 20 and V (X) = 25.

(c) E(X) = 20, V (X) = 25, and X is symmetric with respect to its mean.

173. Let (X_{n})_{n=1}^{∞} be a sequence of identically distributed random variables with mean μ and variance σ^{2}. Let (Y_{n})_{n=1}^{∞} be a sequence of random variables, each taking the values ±1 with probabilities \frac{1}{2}. Assume that all variables are independent. Form the sequence:

S_{n} = Y_{1}X_{1} + Y_{2}X_{2} + … + Y_{n}X_{n}, n = 1, 2, ….

Show that S_{n}/\sqrt{n} is asymptotically normal, and find its asymptotic mean and variance.

174. A random sample of size 54 is drawn from a population distributed according to the probability function

P (x) = \{ \begin{matrix}1/3, & x = 3, 5, 8, \\ 0, & otherwise. \end{matrix}

Estimate the probability for the sample mean to be between 5 and 5.2.

175. A random sample of size 200 is drawn from an Exp(2) population. Find a number d for which the probability for the sample mean to deviate from the population mean by more than d is approximately 0.05.