CSE 312 – Problem Set 4

Due Wednesday, April 29, 11:59pm
Spring 2026

Instructions

For details on expectations for solutions, collaboration policy, late policy, etc, see the instructions on problem set 1.

Solutions submission. You must submit your solution via Gradescope. In particular:

Problem 1 will be done on Gradescope.
Submit the solutions to problems 2-6 under “PSet 4 [Written]” as on previous problem sets.

1 Gradescope Problems (34 points)

Complete these questions about random variables by answering these questions on this gradescope assignment. Please check your answers as it will be autograded so we cannot give partial credit.

2 CDF to PMF (10 points)

Suppose that $X$ is a discrete random variable that takes integer values from 1 to 100 (both inclusive), and has cumulative distribution function (CDF) \[ F_X (x)=\Pr (X \le x) = \frac {\lfloor x \rfloor ^2}{10000} \quad \quad 1 \le x \le 100 \] and \[ F_X(x) = 0 \quad \text { for }x < 1\quad \text { and }\quad F_X(x) = 1 \quad \text { for }x > 100 \] (Thus, for example, $F_X(1) = 1/10000$ and $F_X(2) = 4/10000$ and so on. Also note that the $\lfloor x \rfloor $ (floor of $x$) is the largest integer less than or equal to $x$.)

Find the probability mass function (pmf) for $X$. In other words, provide a formula for $p_X(x)$ that is correct for any integer $x$ in $\{1, 2, \ldots , 100\}$. Simplify it as much as possible.

3 Just double your bet! (12 points)

You go to a casino and make a bet that pays 1:1. In other words, if you bet $$n$, then with probability 1/2 you win $$n$ dollars (i.e., you came into the casino with $$n$ and leave with $2$n$). If you lose the bet (which happens with probability 1/2), you lose the $$n$ that you originally bet.

a): (2 points) What is your expected payoff for this wager (money earned - money spent)?
You decide to try out the following "Doubling Strategy". You bet $1. If you win, you walk away. If you lose, you bet again, doubling your bet. You continue doing this until you win.
b): (1 point) Let $X$ be the number of rounds until you win. What is $\Omega _X$?
c): (4 points) Let $g(k)$ be your payoff (earnings - money spent on the bets) if you win on the $k$-th round . What is $g(k)$? (You may use the fact that $\sum _{j=0}^{k-1} 2^j = 2^k - 1$.)
d): (3 points) What is $\Exp [g(X)]$? You may find the following formula useful: \[\sum _{k=0}^\infty a^k = \frac {1}{1-a}\]
e): (2 points) As you will find, using the above strategy, your expected payoff is strictly positive. Why doesn’t this work in real life?

4 Packet Failures (18 points)

Consider three different models for sending $n$ packets over the Internet:

a): (6 points) each packet takes a different path. Each path fails independently with probability $p$;
b): (6 points) all packets take the exact same path which fails with probability $p$. Thus, either all the packets get through or none get through;
c): (6 points) half the packets take one path, and half take the other (assume $n$ is even), and each of the two paths fails independently with probability $p$.

Let $X_i$ be the number of packets lost in case $i$, for $i = 1, 2, 3$. Write down the probability mass function, the expectation of $X_i$, and the variance of $X_i$ for $i = 1, 2, 3$.

5 Coin tossing fun (12 points)

A group of $n$ friends get together for a party. Each person tosses a fair coin independently. Say that a triple, i.e., a group of 3 people, is a “mixed" triple if at least one of their coins came up heads and at least one came up tails. What is the expected number of mixed triples at the party? So, for example, if $n=4$, and A’s toss came up heads, B’s toss came up heads, C’s toss came up tails and D’s toss came up heads, then the mixed triples are ABC, BCD, ACD.

6 Tennis Tournament (10 points)

Consider a tennis tournament in which each of the $n$ people participating plays a match against every other person participating. (So there are $\binom {n}{2}$ matches.) Suppose that every match is equally likely to be won by either player, and the outcomes of different matches are independent. For a fixed permutation $\pi = (\pi _1, \pi _2, \pi _3, ..., \pi _n)$ of the $n$ people, we say that “$\pi $ is ordered" if person $\pi _1$ wins their match against person $\pi _2$, and person $\pi _2$ wins their match against person $\pi _3$ and person $\pi _3$ wins their match against person $\pi _4$ and so on. What is the expected number of “ordered" permutations (see definition above for “ordered" permutations)?

A Cool For-Fun Problem (will not be graded)

The names of 100 people are placed into 100 closed bags, one name per bag, and the bags are lined up on a table in a room. One by one the people are led into the room; each may look in at most 50 bags, but must leave the room exactly as they found it. From the moment a person is led into the room, that person is not allowed any further communication with the others. The people have a chance to plot their strategy in advance (and come up with a coordinated strategy if they so desire) and they really want to, because if every single person finds their own name among the 50 bags they look in, they will each win a million dollars. Otherwise, nobody wins anything. What can they possibly do to win the money? For example, if they each look into 50 random bags, then the chance any one of them finds their name is 1/2. But that means that the chance that they all find their names is $2^{-100}$, miniscule! The question is: Can you come up with a strategy that guarantees that they win with probability more than 0.3? After you’ve thought about it for a bit, read the rest of this.

Here is a strategy that works: The players first agree amongst themselves on a random labelling of the bags with their names. Then, when a person walks into the room, he first looks at his own bag (the one that has his label in the random labelling). If he doesn’t find his name inside, he looks into the bag belonging to the name he just found, and then into the bag belonging to the name he found in the second bag, etc. until he either finds his own name, or has opened 50 bags. Let me run a quick example assuming 5 people that are each allowed to look into at most 3 bags. Say the random labelling $\pi $ the people agree on for the bags on the table is (Carol, Alice, Darin, Elise, Bob) in order and suppose that what’s inside the corresponding bags in their order on the table are the names (Alice, Bob, Elise, Darin, Carol)

Then when Alice comes in, she will go to the bag labelled with Alice’s name which is bag 2, see Bob’s name inside it, then go to the bag labelled with Bob’s name (bag 5), see Carol’s name inside it and then go to the bag labelled with Carol’s name and see her own name inside it. Yippee, she has found her own name without looking into more than 3 bags. In fact, in this example, using the above strategy, everyone will find their name without looking into more than 3 bags. On the other hand, suppose that the random labelling $\pi '$ of the bags on the table in order was (Darin, Bob, Alice, Carol, Elise) (but still inside the bags the names are in the same order: Alice, Bob, Elise, Darin, Carol) Then, using the above strategy, Bob will find his own name, but none of the rest of them will find their names after looking in 3 bags, and so no money for any of them. Think of the names inside the bags in the order they are on the table as $1, 2, \ldots n$, and the random labelling (random permutation) $\pi $ the people agree on ahead of time as $\pi _1, \pi _2, \ldots , \pi _n$. Then the strategy for the person whose name is $i$ is to go to the bag j such that $\pi _j=i$, then go to the bag $k$ such that $\pi _k = j$ and then go to the bag $\ell $ such that $\pi _{\ell }= k$, until you either find your name or have taken too many steps. Such a sequence is called a cycle in a permutation $\pi $. It is a sequence of indices $i_1, \ldots , i_k$ such that $\pi _{i_1} = i_k$, $\pi _{i_2} = i_1$, $\pi _{i_3}= i_2$ $\ldots $, $\pi _{i_k}=i_{k-1}$.¹

So in the first example above, if we think of (Alice, Bob, Elise, Darin, Carol) as (1, 2, 3, 4, 5) then the random permutation $\pi $ is (5, 1, 4, 3, 2) (i.e. $\pi _1 = 5$, $\pi _2 = 1$ and so on). Thus, in this permutation (2, 5, 1) is a cycle (because $\pi _2 = 1$, $\pi _5 = 2$ and $\pi _1 = 5$). Similarly, (3, 4) is a cycle. and in the second example, the permutation $\pi '$, (2) is a cycle and (3, 5, 4, 1) is a cycle. (You might want to convince yourself that every permutation is the union of disjoint cycles). Now the questions:

a): Convince yourself that if the random permutation that people pick has no cycle of length more than 50, then they will win the money.
b): What is the probability that a random permutation of the numbers 1 to $2n$ does not contain any cycle of length greater than $n$?
c): Using the approximation \[\sum _{1 \le i\le n} \frac {1}{i} \approx \ln (n),\] evaluate the probability that the 100 people each win a million dollars (i.e., all of them find their own name). (FYI: $\sum _{1 \le i\le n} \frac {1}{i}$ is called the $n$-th harmonic number and is denoted by $H_n$).