Exercises and questions

I plan to document some probability-ish questions and solutions here. Some problems are significantly more difficult than others, however there can be multiple ways to approach the more difficult problems.
Probability
Combinatorics
Problem Solving
Interview Prep
Author

Alex Yuan

1 Combinatorics

1.1 Not one-to-one

How many functions \(f:\{1,\ldots,n\}\to \{1,\ldots,n\}\) are not one-to-one?

There are \(n^n\) total functions and \(n!\) one-to-one functions. Hence, the number of functions that are not one-to-one is \(n^n-n!\)

2 Brainteasers/Puzzles/Paradoxes

2.1 To begin or not?

An urn contains k black balls and a single red ball. You and a clone draw without replacement, alternating after each draw until the red ball is drawn at which point the person who drew the red ball wins. The clone has graciously offered you the the choice of whether to draw first or not. How should you decide in order to maximize your probability of winning?

2.2 Drunk Airplane

100 people are line up to board an airplane. For convenience, we can assume that the nth person is assigned the nth seat. However, the first person is drunk and unfortunately takes a random seat. The boarding process commences and if a person isn’t able to sit in their assigned seats they will randomly take an available one. This continues on until the plane has boarded. What is the probability that passenger number 100 ends up in seat 100?

We can think about this symmetrically. The only two events of interest are 1) the event that seat 1 is filled before seat 100 and 2) the event that seat 100 is filled before seat 1. If 1) occurs then the 100th person gets to sit in their assigned seat. If 2) occurs then surely passenger number 100 is in the wrong seat. By symmetry the probability is \(\frac{1}{2}\).

2.3 Bertrand’s Paradox

Take a circle of radius 2 inches in the plane and choose a chord of this circle at random. What is the probability this chord intersects the concentric circle of radius 1 inch? (What are the different solutions?)

2.4 Unknown Correlation

Suppose we have three random variables X, Y , Z, and we know two of the three pairwise correlations. We know X, Y have a correlation of 0.9, and Y, Z have a correlation of 0.8, but we don’t know the correlation of X, Z exactly. What are the best bounds that we can find for the correlation of X, Z?

Define the correlation matrix \[ \rho = \begin{bmatrix} 1 & 0.9 & r\\ 0.9 & 1 & 0.8\\ r & 0.8 & 1 \end{bmatrix} \]

and note that this must be positive semidefinite. Now note \(\det\rho\ge 0\) which leads us to \(-r^2+1.44r-0.45 \geq 0\) giving us the bound \[ |r-0.72| \le \sqrt{0.0684}. \]

3 Expected Value

3.1 Roll Again I

Kelly rolls a fair standard die. She observes the value on the face. Afterwards, she is given the option to either receive the number on the face as a payout or to roll again. If she rolls again, she receives the number on the face as a payout, regardless of what she rolled in the first turn. If Kelly plays optimally, what is her expected pay out?

The optimal strategy is to re-roll if Kelly initially rolls lower than a 4. If Kelly re-rolls the average face value she observes is 3.5, otherwise her average face value is a 5. Hence our expected value is: \[ \mathbb{E}X=\frac{1}{2}(3.5)+\frac{1}{2}(5)=4.25 \]

3.2 Roll Again II

Kelly rolls a fair standard die. She observes the value on the face. Afterwards, she is given the option to either receive the number on the face as a payout or to roll again. If she rolls again, she is given the same decision of paying out or rolling a third time. If she chooses to roll for the third time, she receives a payout equal to the final roll, regardless of what she rolled previously, If Kelly plays optimally, what is her expected pay out?

We use backwards induction on this. Suppose we are on the third roll, our expected value is \(3.5\). Moving on to the second roll, we should take if the value is greater than or equal to 4. Our expected value on the second roll is \[ \frac{1}{6}(3.5+3.5+3+3.5+4+5+6)=\frac{51}{12}=4.25 \] Now, on the first roll, we should take any value greater than or equal to 5. Our expected value on the first roll is \[ \frac{1}{6}(\frac{51}{12}+\frac{51}{12}+\frac{51}{12}+\frac{51}{12}+5+6)=\frac{14}{3} \]

3.3 Roll Again III

Kelly plays a game where she has a standard fair die and repeatedly rolls the die. After each roll, she is allowed to decide whether to re-roll the die or recieve a payout equal to the face of the roll. If she decided to re-roll, Kelly must pay $1 and then is face with the same decision. Under optimal play from Kelly, what is her expected payout?

3.4 4head I

Varun has 4 fair coins. He tosses all 4 at once and checks the parity of each. Varun is now allowed to turn over any pair of coins. In other words, he is only allowed to turn over a coin if he turns over another. He may iterate this process as many times as he would like to maximize his expected number of heads. What is his expected number of heads?

If Varun tosses either \(2\) or \(4\) heads, he is guaranteed \(4\) coins. On the contrary, if Varun flips either \(1\) or \(3\) heads, he is guaranteed \(3\) coins. Hence our expected value is: \[ \mathbb{E}X=\frac{1}{2}(3)+\frac{1}{2}(4)=3.5 \]

3.5 4head II

Varun has 4 fair coins. He tosses all 4 at once and checks the parity of each. Varun is now allowed to toss any pair of coins. In other words, he is only allowed to toss a coin if he tosses another. He may iterate this process as many times as he would like to maximize his expected number of heads. What is his expected number of heads?

Varun’s optimal strategy is to keep tossing pairs until he has all 4 heads as there is no cost to do so. We can think of this as a Markov chain that will hit an all-heads state with probability 1. Hence, our expected value is 4 heads.

3.6 4head III

Varun has 4 fair coins. He tosses all 4 at once and notes the parity of each. After seeing the outcomes, he may toss any pair of tails again. Varun may not toss a single coin without tossing another. He can iterate as many times as he desires, as long as he has less than 3 heads obtained (otherwise, no pairs of tails exists and game over). Find the expected number of tosses Varun performs. Note that the initial 4 tosses are still tosses and each pair counts as 2 tosses.

Denote \(F(k)\) as the maximum expected number of heads after \(k\) tails on the first toss. Our strategy is to iterate until we have less than 2 tails. Immediately, \(F(0)=4, \ F(1)=3\). Suppose we toss k tails at first, then with probability \(\frac{1}{2}\) we go to k-1 tails on the next toss, probability \(\frac{1}{4}\) we go to k-2 tails, and probability \(\frac{1}{4}\) we stay at k tails. Hence we get the recursion: \[ F(k)= \frac{1}{2}F(k-1)+\frac{1}{4}F(k-2)+\frac{1}{4}F(k) \]

Now, \[ F(2) = \frac{1}{2}F(1)+\frac{1}{4}F(0)+\frac{1}{4}F(2) \]

\[ =\frac{3}{2} + \frac{4}{4} + \frac{F(2)}{4} \] which gives \(F(2)=\frac{10}{3}\). Similarly, \[ F(3) = \frac{1}{2}F(2)+\frac{1}{4}F(1)+\frac{1}{4}F(3) \] \[ =\frac{1}{2}(\frac{10}{3}) + \frac{3}{4} + \frac{F(3)}{4} \] which gives \(F(3)=\frac{29}{9}\). Finally, \[ F(4) = \frac{1}{2}F(3)+\frac{1}{4}F(2)+\frac{1}{4}F(4) \] \[ =\frac{1}{2}(\frac{29}{9}) + \frac{1}{4}\frac{10}{3} + \frac{F(4)}{4} \] which gives \(F(4) = \frac{88}{27}\). Taking the expected value, \[ \mathbb{E}[F(k)] = \frac{4 \choose 0}{16}F(0)+\frac{4 \choose 1}{16}F(1)+\frac{4 \choose 2}{16}F(2)+\frac{4 \choose 3}{16}F(3)+\frac{4 \choose 4}{16}F(4) = \frac{88}{27} \]

3.7 The Dice Game

Consider “The Dice Game” consisting of the following steps: 1) Roll a 4-sided die (d4). If you roll a 4, go on; otherwise, start over. 2) Roll a 6-sided die (d6). If you roll a 6, go on; otherwise, start over from the 4-sided die. 3) Repeat the process for a d8, d10, d12, and d20, starting over from the d4 if you do not attain the maximum value of the die you are rolling. If you manage to roll a 20 on the d20, you “win” the game. What is the expected number of rolls required to “win” the game?

3.8 Same Parity Stop

Suppose we have an unfair coin with success probability 0.7. We continually flip until we have the same number of heads and tails which is when the game finishes. What is the expected number of flips that it will take for the game to end, given that your first flip is a Tails?

4 General

4.1 Uniform product

Suppose we draw two random numbers X and Y each distributed uniform on the interval [0, 1]. If X and Y are independent, what is the probability that their product is greater than 1/2?

\[ \mathbb{P}(XY>1/2)=\int \int_{[0,1]^2}\mathbb{I}_{\{\ XY> 1/2 \}}dxdy \]

\[ = \int_{\frac{1}{2}}^1 \int_{\frac{1}{2x}}^1dydx=\int_{\frac{1}{2}}^11-\frac{1}{2x}dx \] \[ =\frac{1}{2}+\frac{1}{2}\text{ln}(\frac{1}{2}) \]