18.600 Introduction to Probability Spring 2023 Final PDF

18.600 Introduction to Probability Spring 2023 Elchanan Mossel Final Wed, May 24, 13:35-16:10 EST Instructions: Answer all questions. Read them carefully first. Be prec...

18.600 Introduction to Probability Spring 2023 Elchanan Mossel Final Wed, May 24, 13:35-16:10 EST Instructions: Answer all questions. Read them carefully first. Be precise and concise. If you write more than one solution to a problem, only the first solution will be graded. Unless stated otherwise you should Justify your answers. Answers with no justification will receive partial credit. You may use any fact from class without proof. However, you should clearly state the facts you are using and why they can be applied. Write your name and ID on each page that you submit. Do not use any materials, notes, electronic devices or web resources during the exam. Do not com- municate with anyone during the exam. Please write your final answer for each question in the box immediately following the question. At the end of the exam (16:10) you will be asked to scan all pages (including the honor code below) of your solutions to Gradescope. Do not write anything on your exam after 16:10. After you’ve scanned your exam you are required to physically hand over your work. Your grade is min(100, sum of points). Good luck! 1. ([−100, 0] pts.) Honor Code Please read, accept and sign below with your name and student i.d: I pledge on my honor that I have not used unauthorized materials or given or received any unauthorized assistance on this exam. Name: Student ID: Signature: 18.600, Spring 2023, Final 1 2. (10 pts.) Which is bigger 2n
1. Which is bigger (a) 22n or (b) n ? Check one: (a)  (b)  Justification: n
n
i+ j 2. Which is bigger (a) ∑ni=0 i (−1) i or (b) ∑i, j,k:i+ j+k=n i, j,k 2 (−3)k ? Check one: (a)  (b)  Justification: 18.600, Spring 2023, Final 2 3. (10 pts.) Events and Axioms of Probability For each of the following statements determine if it is true or false and explain why: 1. If A, B and C are events then 2P(A ∪ B ∪C) = P(A ∪ B) + P(B ∪C) + P(C ∪ A). Check one: TRUE  FALSE  Justification: 2. If A and B are events and P(A|B) = P(B|A) then P(A) = P(B). Check one: TRUE  FALSE  Justification: 18.600, Spring 2023, Final 3 4. (10 pts.) Chat GPT SPAM In 10 years your email account will receive two types of email. 0.01 of the emails are sent by humans and 0.99 are sent by Large Language Models SPAM. The probability that you like an email sent by a human is 0.1. The probability that you like a SPAM email is 0.9. Given that you dislike an email, what is the chance that it was sent by a human? Justification: 18.600, Spring 2023, Final 4 5. (10 pts.) Roll It You roll a standard Die. 1. What is the expected number of rolls until (and including) the sixth time you get a 6? Justification: 2. What is the variance of the number of rolls until (and including) the sixth time you get a 6? Justification: 18.600, Spring 2023, Final 5 6. (10 pts.) At the airport The LongGone airport screens incoming passenger for carrying nuts. The probability that a passen- ger carries nuts is 10−5 and the probability that such a passenger will be caught by the screening is 0.1. There are no false positives, so passengers who do not carry nuts are not caught by the screen- ing. Recall that a Poisson random variable X with parameter λ satisfies: P[X = k] = e−λ λ k /k! for k = 0, 1, 2,.... Use the Poisson approximation to: 1. Compute the probability that in a certain month where 106 passenger passed through the airport exactly 2 were caught by the screening. Justification: 2. What is the probability that among the 106 passengers exactly 2 are caught by the screening and exactly 8 other passengers carried nuts without being caught? Justification: 18.600, Spring 2023, Final 6 7. (10 pts.) Normal Exponentials In a section of the sky, the times Xi in seconds between consecutive births of new stars are i.i.d and satisfy P[Xi > x] = e−x for all x > 0. 1. What are E[Xi ] and Var[Xi ]? (no need to justify) E[X] = Var[X] = Your work (not to be graded): 6 2. Approximate the probability that ∑10 6 3 i=1 Xi ≥ 10 + 10. You can write you answer in terms of 2 Φ, the CDF of a standard Gaussian, or as an integral of the Gaussian density √12π e−x /2. Justification: 18.600, Spring 2023, Final 7 8. (10 pts.) Conditional expectations Suppose you roll a standard die and the outcome is X. Then you toss a fair coin X times. Let Y denote the number of heads you obtain in these tosses. Compute (no need to justify): 1. E[Y |X], Your work (not to be graded): 2. Var[Y |X], Your work (not to be graded): 3. Var[Y ], Your work (not to be graded): 4. E[E[X|Y ]]. Your work (not to be graded): 18.600, Spring 2023, Final 8 9. (10 pts.) Exponentials of Normals 1. Suppose X is a random variable satisfying E[e2X ] = e10. Show that P[X ≥ 9] ≤ e−8. Derivation: 2. Let Y be a normal variable with mean µ = 1 and variance σ 2 = 4. Explain why E[e2Y ] = e10. This allows us to conclude that P[Y ≥ 9] ≤ e−8. Explanation: 18.600, Spring 2023, Final 9 10. (10 pts.) Up or down Consider a stock whose price at day n is given by Yn = ∏ni=1 Xi , where Xi are i.i.d. random variables with P[0 ≤ Xi ≤ 100] = 1 and E[Xi ] = 2. In this question you will show that this information is not sufficient to determine the limiting behavior of Yn. 1. Come up with a distribution for Xi satisfying the above conditions such that P[limn→∞ Yn = ∞] = 1. Distribution of Xi : Justification: 2. Come up with a distribution for Xi satisfying the above conditions such that P[limn→∞ Yn = 0] = 1. Distribution of Xi : Justification: 18.600, Spring 2023, Final 10 11. (10 pts.) Martingales Consider Xi that are i.i.d random variables such that P[Xi ≥ 0] = 1 and E[Xi ] = 1. Which are of the following are martingales? (no need to justify). 1. Yn = ∏ni=1 Xi. Check one: MARTINGALE  NOT A MARTINGALE  Your work (not to be graded): 2. Yn = X1 + X1 X2 +... ∏ni=1 Xi. Check one: MARTINGALE  NOT A MARTINGALE  Your work (not to be graded): 3. Yn = ∏ni=1 (0.5 + 0.5Xi ). Check one: MARTINGALE  NOT A MARTINGALE  Your work (not to be graded): 4. Yn = (∑ni=1 Xi ) − n. Check one: MARTINGALE  NOT A MARTINGALE  Your work (not to be graded): 18.600, Spring 2023, Final 11 12. (10 pts.) Markov Chains and Entropy   0 1 Consider the following Markov chain on two states 1, 2 with transition matrix A =. 0.5 0.5 Suppose that at time 0, X0 , has distribution µ. In other words, µ = (µ1 , µ2 ) = (P[X1 = 0], P[X0 = 2]) (written as a row vector). 1. Write the distribution ν = (ν1 , ν2 ) = (P[X1 = 1], P[X1 = 2]) of the state X1 of the chain at time 1 as a product of a vector by a matrix (no need to justify). Your work (not to be graded): 2. Find a distribution µ such that H(X1 ) > H(X0 ). Justification: 3. Find a distribution µ such that H(X0 ) > H(X1 ). Justification: 18.600, Spring 2023, Final 12 Extra Space 1 18.600, Spring 2023, Final 13 Extra Space 2 18.600, Spring 2023, Final 14 Extra Space 3 18.600, Spring 2023, Final 15