Random Variables · Theory Problems
Lesson 1
Basic Problems.
- (5 points) You toss a fair coin a million times. What is the expected number of length‑12 occurrences whose first 6 flips are Heads and next 6 flips are Tails?
- (10 points) Here is a dice game: you make three independent rolls of a fair die. If you roll a six: (i) zero times, you lose \(\$1\); (ii) exactly once, you win \(\$1\); (iii) exactly twice, you win \(\$2\); and (iv) all three times, you win \(k\) dollars.
- For what value of \(k\) is this game fair?
- What is the smallest integer \(k\) for which the expected value is positive?
- (10 points) Suppose we flip a fair coin and define:
- \(N_{TT}\) as the number of flips until the first time two consecutive Tails appear;
- \(N_{TH}\) as the number of flips until the first Tail immediately followed by a Head appears.
- (10 points) A random subset of all binary strings of length \(n\) is chosen uniformly among all subsets.
- Find the expected total number of ones across all strings in the subset.
- Answer the same question if a uniformly random \(k\)-element subset is chosen.
- (10 points) Suppose the number of cans of cola sold by a cafeteria in one day has the Poisson distribution with mean seven. Find the minimum stock of cola such that the probability of needing no more than that quantity in a day is at least \(0.8\).
- (10 points) Suppose you have a coin and an initial capital of \(\$\)1. If the coin lands Heads, your cash doubles; conversely, if it lands Tails, your cash is halved. Determine the expected value of your cash after \(n\) steps.
Hint:
Consider the expected multiplicative factor for a single step of the process. Recall that for independent random variables, the expectation of the product equals the product of the expectations. - (10 points) \(n\) individuals reside in \(n\) distinct rooms (one per room). Each evening, every individual enters a random room; if it is occupied, they move to another random room, repeating until all rooms are singly occupied. Determine the expected number of individuals who end up in their own rooms.
- (15 points) In the town of Discretion, two contestants arrive independently and uniformly between 5 A.M. and 6 A.M. Each stays for exactly 5 minutes, and they fight if and only if their time intervals overlap. What fraction of duels lead to violence?
Hint:
Model the arrival times as points \((x, y)\) within a square on the Cartesian plane. - (15 points) A random walker is positioned one step away from an edge. Moving one step toward the edge results in falling over. Each step is taken away from the edge with probability \(2/3\) and toward the edge with probability \(1/3\). Determine the probability that the walker eventually escapes.
Hint:
Model the scenario as a one-dimensional random walk starting at position \(1\), with an absorbing state at position \(0\).Let \(\alpha\) be the probability of ever reaching position \(0\) starting from position \(1\). Establish a recurrence relation for \(\alpha\) by considering the outcome of the first step.
- (15 points) A fair six-sided die is repeatedly thrown until a six appears. Let \(\mathcal{S}\) be the set of finite sequences of outcomes \([5]^{*}6\) that end at the first occurrence of a six, with \(\Pr[s] = (1/6)^{|s|}\) and \(T(s) = |s|\).
- Compute \(E[T]\).
- Let \(V\) be the event that all throws before the six are even (i.e., outcomes are in \(\{2,4\}\)). Compute \(\Pr[V]\).
- Compute \(E[T \mid V]\).
- Explain why the reasoning “replace the die with a 3-sided die \(\{2,4,6\}\), so \(E[T \mid V] = 3\)” is incorrect.
Hint:
Recall that a game is fair if the expected value of the profit is zero.
Find \(E[N_{TT}]\) and \(E[N_{TH}]\).Hint:
Consider defining states based on whether the most recent flip was a Tail or not. Then, write two linear equations for the expected remaining time corresponding to these states.
Hint:
Use the linearity of expectation.