Some interesting problems in Probability Here are mostly probability problems which I find interesting and worth thinking about. (Some of them might appear on our problem sheets.) I’m happy to discuss about them on my office hours (unless we are too many on those). They connect to our Probability 1 material across the whole unit, come back to them later if you feel they require material not yet covered. Some of them might assume a bit more knowledge than what is given in Probability 1, we can discuss that too. These problems are not required for any unit, they are not to be handed in. 1. Combinations with repetitions. We will solve the following problem: How many ways are there to pick k objects without order out of an infinite supply of n different types of objects? Example: out of the n = 9 types of cakes in your favourite patisserie you wish to bring home a pack of k = 12 cakes. How many different choices can you make? • First notice that the problem is equivalent with placing k indistinguishable balls (your choices) into n different urns (types of objects). The number of balls in urn i will represent the number of objects of type i selected. • Place these n urns in a row, and think about a configuration as an ordered sequence of k identical balls, and n − 1 identical walls that separate the n urns. Convince yourself that every ball-urn configuration corresponds to exactly one order of these k + n − 1 objects. • The number of orders of the above is now easy, a simple permutation with repetition problem: k+n−1 . This is therefore our answer for the original problem. k many possible packs of cakes. To answer the cake example, we have 12+9−1 12 2. How many solutions does the equation e1 + e2 + · · · + en = k have with ei ’s non-negative integers? (Recall Problem 1.) And if we require each of them to be strictly positive? 3. A closet contains n pairs of shoes. If 2r shoes are randomly selected (2r ≤ n), what is the probability that there will be (a) no complete pair, (b) exactly one complete pair, (c) exactly two complete pairs? 4. We roll a die ten times. What is the probability that each of the results 1, 2, . . . , 6 shows up at least once? Hint: Define the events Ai : = {number i doesn’t show up at all during the ten rolls}, i = 1 . . . 6. Note that these events are not mutually exclusive. 5. In a small town n TV repairmen are available, and one day k households call for TV repairmen. What is the probability that precisely i of the n repairmen will be called, i = 1, 2, . . . , min(n, k)? 6. • Fermi-Dirac distribution. k balls are randomly distributed into n ≥ k urns in such a way that each urn contains at most one ball. (This will be the distribution after a long time if in every second a random ball is chosen, and that ball is moved to the clockwise neighboring urn, provided that that urn is empty. If the neighboring urn is occupied then nothing happens.) Find the probability that the first urn is occupied. • Maxwell-Boltzmann distribution. k distinguishable balls are randomly distributed into n urns. (This will be the distribution after a long time if in every second a random ball is chosen, and that ball is moved into the clockwise neighboring urn.) Find the probability that the first urn contains i balls, i = 1 . . . k. • Bose-Einstein distribution. k indistinguishable balls are randomly distributed into n urns. (This will be the distribution after a long time if in every second a random urn is chosen, and a ball, if any, from that urn is moved into the clockwise neighboring urn.) Find the probability that the first urn contains i balls, i = 1 . . . k. • Now in each of these cases consider the limit n, k → ∞ such that k/n → λ. Show that the answers for the above questions converge: – for Fermi-Dirac: P{the first urn contains a ball} → λ, this is the Bernoulli distribution; – for Maxwell-Boltzmann: P{the first urn contains i balls} → son distribution; 1 λi i! · e−λ , this is called the Pois- – for Bose-Einstein: P{the first urn contains i balls} → metric distribution. λ λ+1 i · 1 λ+1 , this is called the Geo- 7. You are playing a coin tossing game with a friend. You each must choose a (different) sequence of 3 outcomes, (e.g. HT H). A coin will be tossed repeatedly, until one of your sequences is observed in the (possibly long) list of outcomes. You friend has chosen HHH. What sequence should you choose to maximise the probability your sequence comes up first? 8. (Ross.) The king comes from a family of 2 children. What is the probability that the other child is his sister? 9. (Ross.) A laboratory blood test is 95 percent effective in detecting a certain disease when it is, in fact, present. However, the test also yields a “false positive” result for 1 percent of the healthy persons tested. (That is, if a healthy person is tested, then, with probability 0.01, the test result will imply he or she has the disease.) If 0.5 percent of the population actually has the disease, what is the probability a person has the disease given that the test result is positive? 10. (Ross.) Three prisoners are informed by their jailer that one of them has been chosen at random to be executed, and the other two are to be freed. Prisoner A asks the jailer to tell him privately which of his fellow prisoners will be set free, claiming that there would be no harm in divulging this information because he already knows that at least one of the two will go free. The jailer refuses to answer this question, pointing out that if A knew which of his fellow prisoners were to be set free, then his own probability of being executed would rise from 31 to 21 because he would then be one of two prisoners. What do you think of the jailer’s reasoning? 11. We repeatedly roll two dice at the same time, and only stop when at least one of them shows a six. What is the probability that the other also shows a six? 12. Efron’s dice. We are given four fair dice with sides: • A: 4, 4, 4, 4, 0, 0 • B: 3, 3, 3, 3, 3, 3 • C: 6, 6, 2, 2, 2, 2 • D: 5, 5, 5, 1, 1, 1 Compute the probabilities P{A > B}, P{B > C}, P{C > D}, P{D > A} for the respective numbers shown on them. Isn’t it strange? 13. Envelope paradox. You will win one of 2 envelopes which contain an unknown amount of money. One of these amounts is double the other. Suppose you pick envelope A, see the amount, and are offered the option to swap to B – should you? (Why not just pick envelope B in the first place?!) 14. Pólya urn. Initially an urn contains 1 red and 1 blue balls. In every step we choose a random ball which we replace plus we also insert another ball of the same color. (For example, if the first choice was red, then in the second step we choose from 2 red balls and one blue ball.) Show by induction that, after the 1 for each i = 1, 2, . . . , n + 1. nth step, the urn will contain i red balls with probability n+1 15. Urn 1 contains n blue balls, and Urn 2 contains n red balls. At each step we randomly choose a ball from Urn 1, throw it away, and move a red ball from Urn 2 into Urn 1. After the nth step, Urn 2 is empty. What is the proportion of the blue balls in Urn 1 at this time? (Assume that n is large.) 16. (Ross.) Let S = {1, 2, . . . , n} and suppose that A and B are, independently, equally likely to be any of the 2n subsets (including the null set and S itself) of S. n a) Show without computations that P{A ⊂ B} = 34 . n b) Show, using the above, that P{AB = ∅} = 43 . 17. What is the probability that in a class of 50 students there are no coinciding birthdays? 18. Cities A, B, C, D are located (in this order) on the four corners of a square. Between them, we have the following roads: A ↔ B, B ↔ C, C ↔ D, D ↔ A, B ↔ D. One night each of these roads gets blocked by the snow independently with probability 1/2. Show that the next morning city C is accessible from city A with probability 1/2. Do this without computations, using a dual map and probabilistic coupling: instead of snow blocks, use, in a clever way, crossroads with crossings open in one direction but closed in 2 the traverser direction. Now imagine four new cities where these crossroads meet, in a way that the map of the new cities and the crossroads be similar to the original road map. Then think about the question in terms of cities A, C and the corresponding two new cities. 19. A hunter discovers a fox in 30 yards distance, and shoots it. If the fox survives the first shot, then it tries to escape at a velocity of 10 yards/second. The hunter loads the gun and shoots again in every 3 seconds until he either kills the fox, or it disappears in the horizon. The probability that the hunter hits the fox is proportional to the inverse square of the distance: P{The hunter hits the fox from a distance x} = 675x−2 (x ≥ 30). Even when the fox is hit, it is not necessary fatal: the fox survives each hit, independently of previous hits, with probability 1/4. Is the probability that the fox survives this unpleasant adventure positive or zero? 20. Given are an urn of infinite volume and infinitely many balls numbered 1, 2, 3, . . .. Initially the urn is empty. One minute before midnight we place balls no. 1, 2, . . . , 10 into the urn, shake the urn well, choose a random ball which we throw away. Half a minute before midnight we place balls no. 11, 12, . . . , 20 into the urn, shake the urn well, choose a random ball which we throw away. . . . 2−n before midnight we place balls no. 10n + 1, 10n + 2, . . . , 10n + 10 into the urn, shake the urn well, choose a random ball which we throw away. We keep on this until midnight. Prove that the urn is empty at midnight with probability one. 21. As a result of a big survey it turned out that there are, on average, 2.4 children in a family, however, children have, on average, 1.55 siblings. What is the standard deviation of the number of children in a family? 22. A hundred passengers are in queue for boarding a hundred-seat plane. The first passenger lost his boarding pass, so he sits on a randomly chosen seat. Other passengers board one by one, and sit on their seats if they can, and sit to randomly chosen empty seats if their own is already occupied. What is the probability that the last passenger will occupy the seat that was assigned to him? 23. An R 7→ R function is convex, if for every y ∈ dom f there is a real v such that for every x ∈ dom f f (x) ≥ f (y) + v · (x − y). Suppose that f is a convex function, X is a random variable with values in dom f , and both X and f (X) have expectations. Show Jensen’s inequality: E(f (X)) ≥ f (EX). 24. Let x1 , x2 , . . . , xn be nonnegative reals, and X a uniform choice of these numbers: P{X = xi } = 1/n, i = 1 . . . n. Apply Jensen’s inequality for X and • the rth power function, r > 1; • the reciprocal function: connection of the arithmetic and the harmonic mean; • the logarithm: connection of the arithmetic and the geometric mean (how does Jensen’s inequality work for concave functions?). • The value at time t of a deposit with continuously compounded interest is Rt a(t) = a(0) · e0 r(s) ds , where r(s) is the interest rate at time s. Alex always plans in advance, so he deposits an amount in the bank for exactly 10 years. Bob on the other hand only knows that he will withdraw his money from the bank at a random time T which has mean E(T ) = 10 years. Which of the two fellows can expect more money at the time of withdrawal, if – r(s) is constant 0.1, or – r(s) is of the form 0.5/(s + 1)? 25. (Ross.) Suppose we want to generate the outcome of the flip of a fair coin, but that all we have at our disposal is a biased coin which lands on heads with some unknown probability p that need not to be equal to 12 . Consider the following procedure for accomplishing our task: (a) Flip the coin. (b) Flip the coin again. 3 (c) If both flips land on heads or both land on tails, return to step 1. (d) Let the result of the last flip be the result of the experiment. a) Show that the result is equally likely to be either heads or tails. b) Could we use a simpler procedure that continues to flip the coin until the last two flips are different and then lets the result be the outcome of the final flip? 26. (Ross.) a) Let X be a random variable having finite expectation µ and variance σ 2 , and let g(·) be a twice differentiable function. Show that E[g(X)] ≃ g(µ) + g ′′ (µ) 2 σ . 2 Hint: Expand g(·) in a Taylor series about µ. Use the first three terms and ignore the remainder. √ b) Let X be a Poisson random variable with mean λ. Show that if λ is not too small, then Var( X) ≃ 0.25 (!). 27. The rules of ditch-running competition are the following: the track is straight and contains infinitely many identical ditches. Two contestant of equal strength compete and run shoulder to shoulder. Each of the contestants can spring over each ditch independently with probability 2−L , where L is the length of the ditches. If one of them falls in a ditch then the competition ends. a) Show that probability that the game ends in a draw is smaller than ε if and only if 1 + ε . L < log2 1−ε b) Whenever a game ends in a draw they start a new game until a winner is found. For which value of L will the expected number of jumps of contestants be minimal? 28. Find expectation of (1 + X)−1 when a) X ∼ Binom(n, p), b) X ∼ Poi(λ). 29. After a foot-race, 300 of the participants found one tick and 75 found two ticks in their bodies. Estimate the total number of participants. 30. The average density of a forest is 16 trees on every 100 square yards. The tree trunks can be considered as cylinders of a diameter of 0.2 yards. We are standing inside the forest, 120 yards from its edge. If we shoot a gun bullet out of the forest without aiming, what is the probability that it will hit a tree trunk? (Ignore the marginal fact that centers of the tree trunks cannot be closer than 0.2 yards to each other.) 31. In a country families bear children until the first boy is born. What is the distribution of sexes in this country? Are the sexes of children within a family independent? 32. Surveys. In a population of size N , m people smoke. A survey is made by randomly selecting and asking n different people whether they smoke or not. Let X be the smokers among those asked. Show that the distribution of X converges to Binom(n, p) if N → ∞, m → ∞ such that m/N → p while n is kept fixed. 33. Geometric is memoryless. Show that, if X ∼ Geom(p), then P{X ≥ n + k | X > n} = P{X ≥ k}, and the Geometric is the only positive integer variable with this property. The above display interprets as the memoryless property: given that more than n trials are needed for the first success, the probability that an additional k or more trials are needed is the same as if we just started the experiments. 34. (Ross.) Let X be a continuous random variable having cumulative distribution function F . Define the random variable Y by Y = F (X). Show that Y is uniformly distributed over (0, 1). 35. (Ross.) We say that X is stochastically larger than Y , written X ≥st Y , if for all t, P{X > t} ≥ P{Y > t}. Show that if X ≥st Y , then E[X] ≥ E[Y ] when 4 a) X and Y are nonnegative random variables; b) X and Y are arbitrary random variables. Hint: Write X as X = X + − X − where ( X, if X ≥ 0 + , X = 0, if X < 0 X − = ( 0, − X, if X ≥ 0 . if X < 0 Similarly, represent Y as Y + − Y − . Then make use of part a). 36. (Ross.) Show that X ≥st Y if and only if E[f (X)] ≥ E[f (Y )] for all increasing functions f . Hint: If X ≥st Y , show that E[f (X)] ≥ E[f (Y )] by showing that f (X) ≥st f (Y ) and then using the previous exercise. To show the reverse, define an appropriate increasing function f . 37. (Ross.) A bus travels between the two cities A and B, which are 100 miles apart. If the bus has a breakdown, the distance from the breakdown to city A has a uniform distribution over (0, 100). There is a bus service station in city A, in B, and in the center of the route between A and B. It is suggested that it would be more efficient to have the three stations located 25, 50 and 75 miles, respectively, from A. Do you agree? Why? What is the optimal configuration and in what sense? 38. Let F be a continuous distribution function with F (0) = 0. Show that ( 0, if x ≤ 1, G(x) : = −1 F (x) − F (x ), if x > 1 is also a distribution function. Give a probabilistic interpretation to this formula. 39. Is there a continuous [0, 1] → [0, ∞) function for which R1 0 g(x) dx = 1, R1 x·g(x) dx = a, 0 R1 0 x2 ·g(x) dx = a2 ? 40. Let X be normally distributed with mean zero, variance σ 2 . Prove that for any x > 0 we have 2 2 σ 1 1 −(x2 /2σ2 ) σ σ 3 √ e < P{X > x} < √ e−(x /2σ ) . − 3 x x x 2π 2π Hint: differentiate all three terms of the inequality and compare the derivatives. 41. There are two identical insurance companies, both having ten thousand customers. At the beginning of the year every customer pays $500 to his/her insurance company. During the year each customer, independently, establishes a claim to $1500 for damages. Both companies also have $50 000 in reserve from the previous year. A company goes bankrupt, if it cannot settle the claims. Does it make sense for the two companies to join? Let p1 be the probability that at least one of the two companies goes bankrupt, and let p2 be the probability that the joint companies would go bankrupt. Compute p1 and p2 (approximately) and draw the conclusion. 42. A random variable is said to have a symmetric distribution, if there is a µ ∈ R for which X − µ and µ − X have the same distribution. Denote by F the distribution function of X. a) Compute F (µ). (Careful, tricky question.) b) Compute µ+a R F (x) dx. µ−a 43. For which c > 0 value will F (x) = ex ex +c be the distribution function of a symmetric random variable? 44. Let X be a random variable such that P{X = 0} = 0, and Y : = X −1 . Under what conditions will X and Y have the same distribution? 1 2 45. Prove that if ξ is a Cauchy random variable with density f (x) = π1 1+x 2 , then X : = 1/ξ, Y : = 2ξ/(1 − ξ ), 3 2 and Z : = (3ξ − ξ )/(1 − 3ξ ) are also Cauchy distributed. Hint: use the trigonometric identity: if ξ = tan(α), then 1/ξ = tan( π2 − α), 2ξ/(1 − ξ 2 ) = tan(2α), and (3ξ − ξ 3 )/(1 − 3ξ 2 ) = tan(3α). 1 46. Let X be a Cauchy random variable with density f (x) = π1 1+x We know that E|X| = ∞, but 2. 1−ε 1−ε E(|X| ) < ∞ for any ε > 0. Determine the limit lim εE(|X| ). εց0 5 47. Let X be uniformly distributed on the interval [−3, 4], and Ψ(x) = |x − 1| + |x + 1|. Determine the distribution function G(y) of the random variable Y = Ψ(X). Is Y a continuous random variable? Give the decomposition of G to the sum of a discrete, an absolutely continuous, and a continuous but singular, nondecreasing function. 48. Benford’s distribution describes the fact that many real-world quantity (e.g., physical constants, salaries, stocks) behave in a scale-invariant way within some boundaries. Let 0 < a < b be real numbers, then the precise definition is that X has Benford distribution, if it is continuous, almost surely a ≤ X < b, and for all a < z < b we have P{z ≤ X < αz} does not depend on z whenever 1 < α < b/z. (As an example, consider the case when a ≤ 1 and b ≥ 4. Then X has the same probability of falling between 1 and 2 as falling between 2 and 4.) a) Formulate the above statement in terms of the distribution function of X. b) Differentiate the equation of part a) with respect to z, and draw the conclusion: the density of X is of the form C/x (a ≤ x < b). Find the value of C. c) Find the distribution function of X. d) From now on we fix the value a = 1. Let b = 10n (n > 1 integer), and show that the distribution of the first digit of X does not depend on n. e) Therefore, we also fix the value of b now: let a = 1 and b = 10. Compute the probabilities P{the first digit of X is i}, i = 1, 2, . . . , 9. 49. (Ross.) Suppose that X and Y are independent geometric random variables with the same parameter p. a) Without any computations, what do you think is the value of P{X = i | X + Y = n}? Hint: Imagine that you continually flip a coin having probability p of coming up heads. If the second head occurs on the nth flip, what is the probability mass function of the time of the first head? b) Verify your conjecture in part a). 50. Let X and Y be i.i.d. geometric random variables, both with parameter p. Define U : = min{X, Y } and V : = X − Y . Show that U and V are independent. 51. (Ross.) Let X be a normal random variable with parameters µ = 0 and σ 2 = 1 and let I, independent of X, be such that P{I = 1} = 21 = P{I = 0}. Now define Y by ( X, if I = 1 Y = − X, if I = 0. In words, Y is equally likely to equal either X or −X. a) Are X and Y independent? b) Are I and Y independent? c) Show that Y is normal with mean 0 and variance 1. d) Show that Cov(X, Y ) = 0. 52. We break a stick at two random, uniformly and independently chosen points. a) What is the probability that, considering the three parts obtained as edges, a triangle can be assembled? b) What is the probability that each of the three parts is shorter than a (a is a fixed number, more than the third of the length of the stick)? 53. Ants are dropped on a metre stick uniformly at random, (and in a uniformly random direction: left or right). If they meet another ant they will turn around and start travelling in the opposite direction. What is the average distance travelled by an ant before it reaches an end of the stick? 54. Let X1 , X2 , X3 be iid. N (0, 1) random variables. Define q ̺ : = X12 + X22 + X32 , ξi : = Xi /̺, 6 i = 1, 2, 3. a) Compute the density of ̺. b) Show that ̺ and the vector ξ = (ξ1 , ξ2 , ξ3 ) are independent, and ξ is uniformly distributed on the surface of the unit sphere. 55. Let X and Y be iid. Exp(λ) random variables. Prove that U : = X + Y and V : = X/(X + Y ) are independent. 56. The Monte Carlo integration is basically the following. Suppose that f is a [0, 1] → [0, 1] continuous function, and we want to approximate the integral I= Z1 f (x) dx. 0 We generate a uniform random point on the unit square [0, 1]2 n times independently (for example by taking independent Uniform(0, 1) variables Ui and Vi , i = 1, . . . , n), and we denote by Xn the number of such points that fall below the graph of the function f (that is, the number of indices i with f (Ui ) < Vi ). Our estimate for I is then Xn /n. How large should we choose n for the case of the function f (x) = x2 , if we want 0.1 accuracy with at least 98% probability? 57. a) We take three uniform independent points in [0, 1]. Find the distribution function of the middle one. b) We take n uniform independent points in [0, 1]. Find the distribution function of the k th one. 58. (Ross.) Let X1 , X2 , . . . be a sequence of independent and identically distributed continuous random variables. Let N ≥ 2 be such that X1 ≥ X2 ≥ · · · ≥ XN −1 < XN . That is, N is the point at which the sequence stops decreasing. Show that E[N ] = e. Hint: First find P{N ≥ n}. 59. With every step while hiking, independently, Johnny might fall on his face and hurt his knee, or he also might fall back and hurt his elbow. Every ten miles, on average, he hurts his knee three times and his elbow two times. What is the longest hike his mother can let him go if she wants no injuries with probability at least 2/3? 60. The number of accidents in a city is Poisson(10) distributed. After each accident, with probability 0.6 the parties can come to an agreement themselves, but with probability 0.4 the police is called. Yesterday the police was called 5 times. What is the probability that 10 accidents occurred? 61. Let X1 , X2 , . . . , Xn be • independent geometrically distributed with respective parameters p1 , p2 , . . . , pn , or • independent exponentially distributed with respective parameters λ1 , λ2 , . . . , λn . In both cases find the distribution of min{X1 , X2 , . . . , Xn }. For the exponential case also find the probability that the minimum is achieved by Xi (i = 1 . . . n). 62. What is the probability that the sum of n independent Geometric(p) random variables is odd? 63. A fair coin is flipped repeatedly. Find the expected number of flips needed to first see the sequence HHH. How about HT H? 64. A type of sand consists of sphere-shaped grains with lognormally distributed diameters of parameter µ = −0.5 and σ = 0.3. What percentage of the weight of the sand is in grains with diameter less than 0.5? X . 65. Let X and Y be independent and identically distributed, non negative random variables. Find E X+Y 66. Let X1 , . . . , Xn be iid. integer valued random variables, m ≤ n, and Sm = with P{Sn = k} > 0, E(Sm | Sn = k) = 7 m·k . n m P i=1 Xi . Show that for any k 67. Let X and Y be both random variables that can only take on two values: X = x1 , x2 and Y = y1 , y2 . Show that, as opposed to the general case, they are independent if and only if they are uncorrelated. 68. Let X and Y be the two coordinates of a point that is uniformly distributed within the circle of radius one, centered at (1, 1). Compute Cov(X, Y ). 69. Solve Buffon’s needle problem without integrating, by the following argument. • Let X be the number of times the needle intersects a line. By linearity of expectations, it is clear that EX is proportional to ℓ/d, where ℓ is the length of the needle and d is the distance between the parallel lines on the sheet. • Let us now consider a smooth curve. By “dividing it into infinitesimal pieces” conclude that the same proportionality holds. • The circle of diameter d is a nice curve where the constant of proportionality is easy to find out. Conclude that for any smooth curve we have EX = 2 ℓ · . π d In particular, for a needle of length ℓ < d we have X = 0 or 1, hence this also agrees with the probability that the curve intersects a line. 70. A closed loop of thread, shorter than 2rπ, is dropped on the surface of a sphere of radius r. Show that the loop is entirely contained in the surface of a half-sphere. Of course, this is a probability problem. 71. We are given a set v 1 , v 2 , . . . , v n of unit vectors in Rd . Show that there exist εi = ±1 numbers (i = 1 . . . n) such that n √ X εi · v i ≤ n. i=1 Of course, this is also a probability problem. 72. Let A1 . . . An be events. Their indicator variables will be denoted by 1{Ai } (i = 1 . . . n) for this problem. Which event does n Y 1 − 1{Ai } i=1 indicate? On one hand, taking expectation will give the probability of this event. On the other hand, expand the above product according to a 1, singletons of 1{Ai }’s, products of pairs 1{Ai }1{Aj }, products of triplets 1{Ai }1{Aj }1{Ak }, etc. Apply an expectation on each of these terms and conclude the inclusionexclusion formula. 73. Twelve people enter the elevator on the ground floor of a ten-storey building. Compute the expectation and variance of the number of times the elevator stops. 74. (Ross.) Let X1 , X2 , . . . , Xn be independent and identically distributed positive random variables. Find, for k ≤ n, # "P k X i . E Pni=1 i=1 Xi 75. The generating function of a non-negative integer random variable X is given by P (s) = EsX . It shares many nice features with the moment generating function. In particular, the generating function of convolutions equals the product of the generating functions. Use them to find a way to paint positive integers on two 6 sided fair dice whose sum has the same distribution as the sum of two standard 6 sided dice. (The lowest number on each die should be 1). Hint: s + s2 + s3 + s4 + s5 + s6 = (1 + s3 )(s + s2 + s3 ) = (1 + s)(s + s3 + s5 ). 76. A prison warden wants to make room in his prison and is considering liberating one hundred prisoners, thereby freeing one hundred cells. He therefore assembles one hundred prisoners and asks them to play the following game: he lines up one hundred urns in a row, each containing the name of one prisoner, where every prisoner’s name occurs exactly once. The game is played as follows: every prisoner is allowed to look inside fifty urns. If he or she does not find his or her name in one of the fifty urns, all prisoners 8 will immediately be executed, otherwise the game continues. The prisoners have a few moments to decide on a strategy, knowing that once the game has begun, they will not be able to communicate with each other, mark the urns in any way or move the urns or the names inside them. Choosing urns at random, their chances of survival are almost zero, but there is a strategy giving them a 30% chance of survival, assuming that the names are assigned to urns randomly – what is it? Remark: First of all, the survival probability using random choices is 1/2100 so this is definitely not a practical strategy. 30% seems ridiculously out of reach – but yes, you read the problem correctly. 77. Law of Large Numbers for renewal processes. Let τ1 , τ2 , . . . be nonnegative iid. random variables n P τi (the time of the nth (waiting times between renewals), and suppose that Eτi = µ < ∞. Let T (n) : = i=1 renewal ), and N (t) = max{n : T (n) ≤ t} (the number of renewals up to time t). The Weak Law of Large Numbers states that T (n)/n → µ in probability. Prove the following dual statement: for any δ > 0, 78. o n N (t) 1 − > δ = 0. lim P t→∞ t µ a) Let X1 , X2 , . . . , Xn be iid. random variables, EXi = 0. Let also Sn = fourth moments of Sn in terms of those of the Xi ’s. n P Xi . Express the third and i=1 b) Let f : [0, 1] → R be a four times continuously differentiable function. Compute lim n n→∞ Z 1Z1 Z1 n 1 o x1 + x2 + · · · + xn ... f −f dx1 dx2 . . . dxn . n 2 lim Z 1Z1 00 79. Prove that n→∞ 0 ... Z1 0 00 x21 + x22 + · · · + x2n 2 dx1 dx2 . . . dxn = . x1 + x2 + · · · + xn 3 80. Let f be a [0, 1] → R continuous function. Prove that lim Z 1Z1 Z1 1 x1 + x2 + · · · + xn dx1 dx2 . . . dxn = f , ... f n 2 lim Z 1Z1 n→∞ 00 n→∞ 0 00 ... Z1 0 1 . f (x1 x2 . . . xn )1/n dx1 dx2 . . . dxn = f e 81. Conjecturing the true order of magnitude of normal fluctuations. Let X1 , X2 , . . . be iid. random n P Xi . The WLLN states variables with mean EXi = 0 and variance VarXi = σ 2 < ∞. Let also Sn = i=1 that for any fixed δ > 0 n |S | o n lim P > δ = 0. n→∞ n Prove the following, much stronger, statement: for any sequence bn that converges to ∞ we have, for any δ > 0, o n |S | n √ > δ = 0. lim P n→∞ bn · n 9