Strategic Practice and Homework - Home | Projects at Harvard
Stat 110 Strategic Practice 4, Fall 2011
Prof. Joe Blitzstein (Department of Statistics, Harvard University)
1 Distributions and Expected Values for Discrete
Random Variables
1. Find an example of two discrete random variables and (on the same
XY
sample space) such that and have the same distribution (i.e., same PMF
XY
and same CDF), but the event =
occurs.
X Y never
2. Let be a random day of the week, coded so that Monday is 1, Tuesday is 2,
X
etc. (so takes values 1 2 7 with equal probabilities). Let be the next
X
, ,..., ,
Y
day after (again represented as an integer between 1 and 7). Do and
X
XY
have the same distribution? What is (
)?
P X EY
is greater than with probability at least 0.99?
Y
X
5. Let be a discrete r.v. with possible values 1,2,3,. . . . Let ( ) = ( )
X
Fx PX x
be the CDF of . Show that
X
X 1 E(X) = (1 F (n)) .
n=0
Hint: organize the order of summation carefully, using the fact that, for exam-
ple, ( 3) = ( = 4) + ( = 5) + .
P X> P X
PX
...
6. Job candidates C1, C2, . . . are interviewed one by one, and the interviewer compares them and keeps an updated list of rankings (if candidates have n been interviewed so far, this is a list of the candidates, from best to worst). n Assume that there is no limit on the number of candidates available, that for any n the candidates C1, C2, . . . , Cn are equally likely to arrive in any order, and that there are no ties in the rankings given by the interview.
1
Let X be the index of the first candidate to come along who ranks as better
than the very first candidate C1 (so CX is better than C1, but the candidates after 1 but prior to X (if any) are worse than C1. For example, if C2 and C3 are worse than C1 but C4 is better than C1, then X = 4. All 4! orderings of the first 4 candidates are equally likely, so it could have happened that the first
candidate was the best out of the first 4 candidates, in which case
4.
X>
What is ( ) (which is a measure of how long, on average, the interviewer EX
needs to wait to find someone better than the very first candidate)? Hint: find
( PX
>
) n
by
interpreting
what
X
>
n
says
about
how
C1
compares
with
other
candidates, and then apply the result of the previous problem.
2 Indicator Random Variables and Linearity of
Expectation
1. A group of 50 people are comparing their birthdays (as usual, assume their birthdays are independent, are not February 29, etc.). Find the expected number of pairs of people with the same birthday, and the expected number of days in the year on which at least two of these people were born.
2. A total of 20 bags of Haribo gummi bears are randomly distributed to the 20 students in a certain Stat 110 section. Each bag is obtained by a random student, and the outcomes of who gets which bag are independent. Find the average number of bags of gummi bears that the first three students get in total, and find the average number of students who get at least one bag.
3. There are 100 shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from dierent pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops? (This is a famous interview problem; leave the latter answer as a sum.)
Hint: for each step, create an indicator r.v. for whether a loop was created then, and note that the number of free ends goes down by 2 after each step.
4. A
is a commonly used data structure in computer science, allowing
hash table
for fast information retrieval. For example, suppose we want to store some
people's phone numbers. Assume that no two of the people have the same
2
name. For each name x, a hash function h is used, where h(x) is the location
to store 's phone number. After such a table has been computed, to look up
x
's phone number one just recomputes ( ) and then looks up what is stored
x
hx
in that location.
The hash function h is deterministic, since we don't want to get dierent results
every time we compute ( ). But is often chosen to be
. For
hx
h
pseudorandom
this problem, assume that true randomness is used. So let there be people,
k
with each person's phone number stored in a random location (independently),
represented by an integer between 1 and . It then might happen that one n
location has more than one phone number stored there, if two dierent people
x and y end up with the same random location for their information to be stored.
Find the expected number of locations with no phone numbers stored, the expected number with exactly one phone number, and the expected number with more than one phone number (should these quantities add up to n?).
3
Stat 110 Strategic Practice 4 Solutions, Fall 2011
Prof. Joe Blitzstein (Department of Statistics, Harvard University)
1 Distributions and Expected Values for Discrete
Random Variables
1. Find an example of two discrete random variables and (on the same
XY
sample space) such that and have the same distribution (i.e., same PMF
XY
and same CDF), but the event =
occurs.
X Y never
For a simple example, let Bernoulli(1 2) (i.e., can be thought of as a fair
X
/
X
coin flip), and let = 1 . Then is also Bernoulli(1 2) by symmetry, but
Y
X
Y
/
X
= Y
is
impossible.
A
more
general
example is to
let
X
Binomial( n,
1 2) /
and =
, where is any odd number (think of this as interchanging the
Y nX
n
definitions of "success" and "failure"!).
2. Let be a random day of the week, coded so that Monday is 1, Tuesday is 2,
X
etc. (so takes values 1 2 7 with equal probabilities). Let be the next
X
, ,..., ,
Y
day after X (again represented as an integer between 1 and 7). Do X and Y
have the same distribution? What is (
)?
P Xx
p
for 1, since
says that the first b c flips land tails. The CDF is 0 for
x
X >x
x
1. For a fair coin, the CDF is ( ) = 1
x<
Fx
1 2bxc
for
x
1, and ( ) = 0 for Fx
1, as illustrated below.
x<
1
CDF
1.0
0.8
0.6
F(x)
0.4
0.2
0.0
0
2
4
6
8
10
x
4. Are there discrete random variables and such that ( ) 100 ( ) but
XY
EX > EY
is greater than with probability at least 0.99?
Y
X
Yes: consider what happens if we make usually 0 but on rare occasions,
X
X
is extremely large (like the outcome of a lottery); , on the other hand, can be Y
more moderate. For example, let be 106 with probability 1 100 and 0 with
X
/
probability 99 100, and let be the constant 1.
/
Y
5.
Let
X
be
a
discrete
r.v.
with
possible
values
1,2,3,. . . .
Let
() Fx
=
( PX
) x
be the CDF of . Show that
X
X 1
( ) = (1 ( ))
EX
Fn .
n=0
Hint: organize the order of summation carefully, using the fact that, for exam-
ple, ( 3) = ( = 4) + ( = 5) + .
P X> P X
PX
...
Note that X 1 (1
=0 n
X 1
X 1 X 1
( )) =
(
)=
Fn
P X>n
( =) PX k
=0 n
=0 n
= +1 kn
For each , the term ( = ) appears exactly times: there is one ( = )
k
PX k
k
PX k
term for each nonnegative integer
. More visually, write out some terms:
n ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 7th grade math mrs callahan and mr wilson inequalities 1 w
- math 54 selected solutions for week 7 section 5 1 page 241
- igcse mathematics 0580 41 paper 4 extended may jun 2020
- interval notation and linear inequalities section 1 7 math 1300
- go math practice book te g5 geneseo schools
- chapter 2 set theory page 42 university of north georgia
- strategic practice and homework home projects at harvard
- 14 1 lesson big ideas learning
- translating linear inequalities math worksheets 4 kids
- use the number line to write the in inequality use x as the variable
Related searches
- strategic leadership and strategic management
- kid crafts projects at home
- wells fargo home projects credit card payment
- wells fargo home projects program
- wells fargo home projects vendors
- wells fargo home projects participants
- wells fargo home projects credit card reviews
- practice and homework lesson 6 2
- at and t home internet
- craft and home projects magazine
- wells fargo home projects account
- wells fargo home projects card