Mathematics > QUESTIONS & ANSWERS > University of California, Berkeley - CS 70 hw13-solution. CS 70 Discrete Mathematics and Probability (All)

University of California, Berkeley - CS 70 hw13-solution. CS 70 Discrete Mathematics and Probability Theory Spring 2019 . All Solutions Worked.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Spring 2019 Babak Ayazifar and Satish Rao HW 13 1 Markov’s Inequality and Chebyshev’s Inequality A random variable X has variance var(X) = 9 an... d expectation E[X] = 2. Furthermore, the value of X is never greater than 10. Given this information, provide either a proof or a counterexample for the following statements. (a) EX2 = 13. (b) P[X = 2] > 0. (c) P[X ≥ 2] = P[X ≤ 2]. (d) P[X ≤ 1] ≤ 8=9. (e) P[X ≥ 6] ≤ 9=16. (f) P[X ≥ 6] ≤ 9=32. Solution: 2 Subset Card Game Jonathan and Yiming are playing a card game. Jonathan has k > 2 cards, and each card has a real number written on it. Jonathan tells Yiming (truthfully), that the sum of the card values is 0, and that the sum of squares of the values on the cards is 1. Specifically, if the card values are c1;c2;:::;ck, then we have ∑k i=1 ci = 0 and ∑k i=1 c2 i = 1. Jonathan and Yiming also agree on a positive target value of a. The cards are then going to be dealt randomly in the following fashion: for each card in the deck, a fair coin is flipped. If the coin lands heads, then the card goes to Yiming, and if the coin lands tails, the card goes to Jonathan. Note that it is possible for either player to end up with no cards/all the cards. A player wins the game if the sum of the card values in their hand is at least a, otherwise it is a tie. (a) Prove that the probability that Yiming wins is at most 8a12 . (b) Find a deck of k cards and target value a where the probability that Yiming wins is exactly 1 8a2 . Solution: 3 Sampling a Gaussian With Uniform In this question, we will see one way to generate a normal random variable if we have access to a random number generator that outputs numbers between 0 and 1 uniformly at random. As a general comment, remember that showing two random variables have the same CDF or PDF is sufficient for showing that they have the same distribution. (a) First, let us see how to generate an exponential random variable with a uniform random variable. Let U1 ∼ Uni f orm(0;1). Prove that -lnU1 ∼ Expo(1). CS 70, Spring 2019, HW 13 3 (b) Let N1;N2 ∼ N (0;1), where N1 and N2 are independent. Prove that N12 + N22 ∼ Expo(1=2). Hint: You may use the fact that over a region R, if we convert to polar coordinates (x;y) ! (r;q), then the double integral over the region R will be ZZR f (x;y)dxdy = ZZR f (rcosq;rsinq)•r dr dq: (c) Suppose we have two uniform random variables, U1 and U2. How would you transform these two random variables into a normal random variable with mean 0 and variance 1? Hint: What part (b) tells us is that the point (N1;N2) will have a distance from the origin that is distributed as the square root of an exponential distribution. Try to use U1 to sample the radius, and then use U2 to sample the angle. Solution: CS 70, Spring 2019, HW 13 4 4 Optimal Gambling Jonathan has a coin that may be biased, but he doesn’t think so. You disagree with him though, and he challenges you to a bet. You start off with X0 dollars. You and Jonathan then play multiple rounds, and each round, you bet an amount of money of your choosing, and then coin is tossed. Jonathan will match your bet, no matter what, and if the coin comes up heads, you win and you take both yours and Jonathan’s bet, and if it comes up tails, then you lose your bet. (a) Now suppose you actually secretly know that the bias of the coin is 1 2 < p < 1! You use the following strategy: on each round, you will bet a fraction q of the money you have at the start of the round. Let Xn denote the amount of money you have on round n. X0 represents your initial assets and is a constant value. What is E[Xn] in terms of X0; p, and q? (b) What value of q will maximize E[Xn]? For this value of q, what is the distribution of Xn? Can you predict what will happen as n ! ¥? [Hint: Under this betting strategy, what happens if you ever lose a round?] (c) The problem with the previous approach is that we were too concerned about expected value, so our gambling strategy was too extreme. Let’s start over: again we will use a gambling strategy in which we bet a fraction q of our money at each round. Express Xn in terms of n, q, X0, and Wn, where Wn is the number of rounds you have won up until round n. [Hint: Does the order in which you win the games affect your profit?] (d) By the law of large numbers, Wn=n ! p as n ! ¥. Using this fact, what does (lnXn)=n converge to as n ! ¥? (e) The rationale behind (lnXn)=n is that if (lnXn)=n ! c, where c is a constant, then that means for large n, Xn is roughly ecn. Therefore, c is the asymptotic growth rate of your fortune! Find the value of q that maximizes your asymptotic growth rate. (f) Using the value of q you found in the previous part, compute E[Xn]. (g) Now, Jonathan is not going to always believe that the coin is fair. What he will do is play 100 rounds with you, and observe how many times the coin comes up heads. Jonathan will then construct a 95% confidence interval for the true bias of the coin, p. True or false, the probability that Jonathan’s interval captures p is at least 95%. (h) Let’s say after playing 100 rounds, Jonathan observes that 74 heads have appeared. Help Jonathan construct a 95% confidence interval using the CLT. Also, answer true or false: the probability that this interval contains the true bias p of the coin is 95%. You may assume that F(2)-F(-2) ≈ 0:95, where F is the CDF of the standard Gaussian. Solution: 5 Boba in a Straw Imagine that Jonathan is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see figure). Figure 1: A straw with one boba currently inside. The straw only has enough room to fit two boba. Here is a formal description of the drinking process: We model the straw as having two “components” (the top component and the bottom component). At any given time, a component can contain nothing, or one boba. As Jonathan drinks from the straw, the following happens every second: CS 70, Spring 2019, HW 13 7 1. The contents of the top component enter Jonathan’s mouth. 2. The contents of the bottom component move to the top component. 3. With probability p, a new boba enters the bottom component; otherwise the bottom component is now empty. Help Jonathan evaluate the consequences of his incessant drinking! (a) At the very start, the straw starts off completely empty. What is the expected number of seconds that elapse before the straw is completely filled with boba for the first time? [Write down the equations; you do not have to solve them.] (b) Consider a slight variant of the previous part: now the straw is narrower at the bottom than at the top. This affects the drinking speed: if either (i) a new boba is about to enter the bottom component or (ii) a boba from the bottom component is about to move to the top component, then the action takes two seconds. If both (i) and (ii) are about to happen, then the action takes three seconds. Otherwise, the action takes one second. Under these conditions, answer the previous part again. [Write down the equations; you do not have to solve them.] (c) Jonathan was annoyed by the straw so he bought a fresh new straw (the straw is no longer narrow at the bottom). What is the long-run average rate of Jonathan’s calorie consumption? (Each boba is roughly 10 calories.) (d) What is the long-run average number of boba which can be found inside the straw? [Maybe you should first think about the long-run distribution of the number of boba.] Solution: [Show More]

Last updated: 1 year ago

Preview 1 out of 10 pages

Reviews( 0 )

Recommended For You

 Financial Accounting> QUESTIONS & ANSWERS > DeVry University, Keller Graduate School of Management - BUSN 278FINALS3. All Solutions Worked Out. (All)

preview
DeVry University, Keller Graduate School of Management - BUSN 278FINALS3. All Solutions Worked Out.

DeVry University, Keller Graduate School of Management - BUSN 278FINALS3 7. The production budget shows that expected unit sales are 40,000. The total required units are 45,000. What are the requi...

By Kirsch , Uploaded: May 19, 2020

$9

 Mathematics> QUESTIONS & ANSWERS > CS 70 Discrete Mathematics and Probability Theory HW 10 Worked Solutions (All)

preview
CS 70 Discrete Mathematics and Probability Theory HW 10 Worked Solutions

University of California, Berkeley COMPSCI 70 CS 70 Discrete Mathematics and Probability Theory HW 10 1 Sundry Before you start your homework, write down your team. Who else did you work with on...

By Kirsch , Uploaded: Aug 05, 2022

$7

 Business> QUESTIONS & ANSWERS > CS 70 Discrete Mathematics and Probability Theory Spring 2017 Rao (All)

preview
CS 70 Discrete Mathematics and Probability Theory Spring 2017 Rao

CS 70 Discrete Mathematics and Probability Theory Spring 2017 Rao CS 70 Discrete Mathematics and Probability Theory Spring 2017 RaoCS 70 Discrete Mathematics and Probability Theory Spring 2017 RaoCS 7...

By QUIZBANK , Uploaded: Jan 05, 2022

$11

 Business> QUESTIONS & ANSWERS > CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and Walrand (All)

preview
CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and Walrand

CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and Walrand CS 70 Fall 2016 Discrete Mathematics and Probability Theory Seshia and WalrandCS 70 Fall 2016 Discrete Mathematics and...

By QUIZBANK , Uploaded: Jan 05, 2022

$11

 Business> QUESTIONS & ANSWERS > CS 70 Fall 2017 Discrete Mathematics and Probability Theory Kannan Ramchandran and Satish Rao (All)

preview
CS 70 Fall 2017 Discrete Mathematics and Probability Theory Kannan Ramchandran and Satish Rao

CS 70 Fall 2017 Discrete Mathematics and Probability Theory Kannan Ramchandran and Satish Rao CS 70 Fall 2017 Discrete Mathematics and Probability Theory Kannan Ramchandran and Satish RaoCS 70 Fall...

By QUIZBANK , Uploaded: Jan 05, 2022

$11

 Mathematics> QUESTIONS & ANSWERS > Berkeley - CS 70 HW 12. CS 70 Discrete Mathematics and Probability Theory (All)

preview
Berkeley - CS 70 HW 12. CS 70 Discrete Mathematics and Probability Theory

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 13 Note: This homework consists of two parts. The first part (questions 1-6) will be graded and will...

By Maxquizer , Uploaded: Jul 19, 2021

$9

 Mathematics> QUESTIONS & ANSWERS > Berkeley - CS 70 HW 12. CS 70 Discrete Mathematics and Probability Theory (All)

preview
Berkeley - CS 70 HW 12. CS 70 Discrete Mathematics and Probability Theory

CS 70 Discrete Mathematics and Probability Theory Fall 2017 Kannan Ramchandran and Satish Rao HW 12 Sundry Before you start your homework, write down your team. Who else did you work with on this...

By Maxquizer , Uploaded: Jul 19, 2021

$8

 Mathematics> QUESTIONS & ANSWERS > University of California, BerkeleyCS 70FA19hw13sol.Discrete Mathematics and Probability Theory (All)

preview
University of California, BerkeleyCS 70FA19hw13sol.Discrete Mathematics and Probability Theory

1 Short Answer (a) Let X be uniform on the interval [0,2], and define Y = 2X +1. Find the PDF, CDF, expectation, and variance of Y. (b) Let X and Y have joint distribution f (x,y) = (cxy 0 else +1...

By proff JAY , Uploaded: May 13, 2021

$17.5

 Electrical Engineering> QUESTIONS & ANSWERS > University of California, Berkeley - EECS 126hw12-sol (All)

preview
University of California, Berkeley - EECS 126hw12-sol

Department of Electrical Engineering and Computer Sciences EECS 126: Probability and Random Processes Problem Set 12 Spring 2018 Self-Graded Scores Due: 5 PM, Friday May 4, 2018 Submit your self-...

By AGRADES , Uploaded: Apr 17, 2021

$6

 Electrical Engineering> QUESTIONS & ANSWERS > University of California, Berkeley - EECS 126hw11-sol. (All)

preview
University of California, Berkeley - EECS 126hw11-sol.

UC Berkeley Department of Electrical Engineering and Computer Sciences EECS 126: Probability and Random Processes Problem Set 11 Spring 2018 Self-Graded Scores Due: 5 PM, Monday April 23, 2018 S...

By AGRADES , Uploaded: Apr 17, 2021

$6

$13.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
126
0

Document information


Connected school, study & course



About the document


Uploaded On

Apr 16, 2021

Number of pages

10

Written in

Seller


seller-icon
Kirsch

Member since 4 years

898 Documents Sold


Additional information

This document has been written for:

Uploaded

Apr 16, 2021

Downloads

 0

Views

 126

Document Keyword Tags

THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

custom preview

Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

custom preview

Get the best grades

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

custom preview

Earn from your notes

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.


$13.00

WHAT STUDENTS SAY ABOUT US


What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·