[SOLVED] Probability & statistics for eecs homework 05

1. A treasure is randomly placed in one of the nine realms (numbered from 1 to 9) attached
to the Yggdrasill. Kratos searches for the treasure by asking Mimir yes-no questions.
Find the expected number of questions until Kratos is sure about the location of the
treasure, under each of the following strategies.(a) An enumeration strategy: Kratos asks questions of the form “is it in realm k?”.
(b) A bisection strategy: Kratos eliminates as close to half of the remaining realms
as possible by asking questions of the form “is it in a realm numbered less than
or equal to k?”.2. A particular Youtuber is known for his arbitrary steak-eating habit during live streaming. In each live streaming day, he orders a steak with doneness as one of well done,
medium well, medium, medium rare, and rare (with equal probability, independent of
other live streaming days). How many days of live streaming do you expect to watch
before you see him eating steaks with each possible doneness at least once (suppose
you are a big fan who watches his every live streaming)?3. Mario and Zelda are independently performing independent Bernoulli trials. For concreteness, assume that Mario is flipping a nickel with probability p1 of Heads and Zelda
is flipping a penny with probability p2 of Heads. Let X1, X2, · · · be Mario’s results and
Y1, Y2, · · · be Zelda’s results, with Xi ∼ Bern(p1) and Yj ∼ Bern(p2).(a) Find the distribution and expected value of the first time at which they are simultaneously successful, i.e., the smallest n such that Xn = Yn = 1.
(b) Find the expected time until at least one has a success (including the success).(c) For p1 = p2, find the probability that their first successes are simultaneous, and
use this to find the probability that Mario’s first success precedes Zelda’s.4. Let X and Y be independent geometric random variables, where X has parameter p
and Y has parameter q.
(a) What is the probability that X = Y ?
(b) What is E[max(X, Y )]?
(c) What is P(min(X, Y ) = k)?
(d) What is E[X|X ≤ Y ]?5. You plan to eat m meals at a certain restaurant, where you have never eaten before.
Each time, you will order one dish (without replacement).The restaurant has n dishes on the menu, with n ≥ m. Assume that if you had tried
all the dishes, you would have a definite ranking of them from 1 (your least favorite) to
n (your favorite). If you knew which your favorite was, you would be happy to order
it always (you never get tired of it).Before you’ve eaten at the restaurant, this ranking is completely unknown to you.
After you’ve tried some dishes, you can rank those dishes amongst themselves, but
don’t know how they compare with the dishes you haven’t yet tried. There is thus an
exploration-exploitation trade-off : should you try new dishes, or should you order your
favorite among the dishes you have tried before?A natural strategy is to have two phases in your series of visits to the restaurant: an
exploration phase, where you try different dishes each time, and an exploitation phase,
where you always order the best dish you obtained in the exploration phase. Let k be
the length of the exploration phase (so m − k is the length of the exploitation phase).Your goal is to maximize the expected sum of the ranks of the dishes you eat there
(the rank of a dish is the true rank from 1 to n that you would give that dish if you
could try all the dishes). Show that the optimal choice is
k = �2(m + 1) − 1
or this rounded up or down to an integer if needed.Do this in the following steps:
(a) Let X be the rank of the best dish that you find in the exploration phase. Find
the expected sum of the ranks of the dishes you eat, in terms of E[X].
(b) Find the PMF of X, as a simple expression in terms of binomial coefficients.
(c) Show that
E[X] = k(n + 1)
k + 1 .
(d) Use calculus to find the optimal value of k.