A Working List of Probability Questions: Week 1

In Preparation For Quantitative Trading Interviews
June 21, 2020 | Updated June 28, 2020

This series is mostly for my own self-documentation purposes as I prepare for recruiting at the end of summer. I’ll be updating this page with 5 new problems/brain teasers and solutions every day to keep myself accountable. These problems will come from a variety of sources, including A Practical Guide to Quantitative Finance Interviews, Math Stack Exchange, and UC Berkeley’s EECS 126 course notes. You can skip to my week one review here or navigate to a specific day using the legend below. Thanks for tuning in!

Day 1   |   Day 2   |   Day 3   |   Day 4   |   Day 5   |   Day 6   |   Day 7  

Day One: June 21

Today’s problems are relatively simple as I spent a while figuring out the LaTeX formatting on websites.

Problem 1. What is the expected number of tosses to get three consecutive heads when flipping a fair coin? Solution. Let E[3]\mathbb{E}[3] denote the expected number of rolls for 33 consecutive heads. If we start rolling and roll a tail first, which has probability 12\frac{1}{2}, then the expected number of tosses will be E[3]+1\mathbb{E}[3] + 1. If we roll a head then a tail, which has probability 14\frac{1}{4}, then the expected number will be E[3]+2\mathbb{E}[3] + 2. If we roll 2 heads then a tail with probability 18\frac{1}{8} then expected value is E[3]+3\mathbb{E}[3] + 3. Finally if we roll 33 heads consecutively, which has probability 18\frac{1}{8}, then E[3]=3\mathbb{E}[3] = 3. Combining these together, we have

E[3]=12(E[3]+1)+14(E[3]+2)+18(E[3]+3)+18(3)\mathbb{E}[3] = \frac{1}{2}(\mathbb{E}[3] + 1) + \frac{1}{4}(\mathbb{E}[3] + 2) + \frac{1}{8}(\mathbb{E}[3] + 3) + \frac{1}{8}(3)

Solving this equation gives E[3]=14\mathbb{E}[3] = 14. We can extend this to find the expected number of rolls for nn consecutive heads to get E[n]\mathbb{E}[n]:

E[n]=12(E[n]+1)+14(E[n]+2)++12n(E[n]+n)+12n(n)\mathbb{E}[n] = \frac{1}{2}(\mathbb{E}[n] + 1) + \frac{1}{4}(\mathbb{E}[n] + 2) + \cdots + \frac{1}{2^n}(\mathbb{E}[n] + n) + \frac{1}{2^n}(n)

Solving for this in general gives us the formula E[n]=2(2n1)\mathbb{E}[n] = 2(2^n - 1). A number of other solutions of this type of problem can be found here.

Problem 2. Suppose there are five pirates with 100100 pieces of gold who are voting on splitting up the gold. The most senior pirate will propose a way to distribute the gold and requires 50%50\% of the votes in order to pass his proposal. If he receives less than 50%50\% of the votes then he will be killed and the process will begin with the next most senior pirate. How will the gold coins be divided? Solution. Let’s label each pirate in ascending order based on seniority, so pirate 55 will be most senior and 11 will be least senior. Building this up from the two pirate case: Pirate 2 can safely propose he take all 100100 gold pieces as he constitutes 50%50\% of the votes. Then Pirate 1 receives nothing.

Moving on to the three pirate case—Pirate 3 knows that if his plan is voted down, then Pirate 2 can take all 100100 coins and Pirate 1 will receive nothing. All he needs to do is give Pirate 1 one coin to secure his vote. Adding a fourth pirate, Pirate 4 knows that if his plan is voted down, then Pirate 2 will get nothing. Then all he needs to do is propose to offer Pirate 2 one coin and keep the remaining 99. Now considering all five pirates, Pirate 5 knows that if his plan is voted down, Pirate 1 and Pirate 3 will receive nothing. Then all he needs to do is offer 1 gold coin each to Pirate 1 and Pirate 3, keeping the 98 coins.

We can extend this to any number nn pirates (so long as n<=200n<= 200). If nn is odd, the most senior pirate will offer Pirates 1,3,,n21, 3, \dots, n - 2 each one coin and keep the remainder for himself. If nn is even, then he will offer Pirates 2,4,,n22, 4, \dots, n-2 one coin each and keep the remainder.

Problem 3. For a best of 3 set tennis match, would you bet on it finishing in two sets or three sets given that probabilty of winning a set is constant? Solution. Let p=P(player 1 wins)p = P(\text{player 1 wins}) and q=P(player 2 wins)q = P(\text{player 2 wins}). To win in two sets, we can have player 1 or player 2 win two consecutive sets, giving a total probability of p2+q2p^2 + q^2. In order for the match to end in three sets, one player must win 2 sets (assume thats its player 1) and the other one set. This corresponds with a probability of 2pq2pq. Note that (pq)20(p - q)^2 \geq 0, implying that p2+q22pqp^2 + q^2 \geq 2pq, so I would bet on the match finishing in two sets.

Problem 4. You break a stick of length 1 at two points uniformly. What is the probability that the three resulting pieces can form a triangle? Solution. A triangle is possible to form so long as one piece is not longer than the sum of the other two (one side >12> \frac{1}{2}) and the difference between two pieces is not longer than the third. Consider the midpoint MM of the original stick: if both cuts are made on the same side of MM (probability 12)\frac{1}{2}), then one side will have length greater than 12\frac{1}{2} and a triangle is not possible. Let’s say we break the stick at two points xx and yy with x<yx < y and xx and yy are on different side of MM. There is probability 12\frac{1}{2} that xx is farther left on it half of the stick than yy is right on its half or the vice versa. In this case, we can’t form a triangle either because the difference between two sides will be longer than the third. Then only (112)(112)=14(1 - \frac{1}{2}) \cdot ( 1 - \frac{1}{2}) = \frac{1}{4} of breaks can form a triangle (my justification of this seems a bit shady and I’ll work on a more analytical solution another time).

Problem 5. Consider a game where there are two blue balls and two red balls in a bag. Each ball is removed from the bag without replacement and if you guess the color of the ball correctly you earn a dollar. How much would you pay to play this game? Solution. On your first draw you have a 24\frac{2}{4} chance of guessing correctly. On the second draw, you have a 23\frac{2}{3} chance of guessing correctly so long as you guess the color opposite of the first ball. By the third ball, either you have selected two balls of the same color with probability 13\frac{1}{3} or you selected two balls of different color with probability 23\frac{2}{3}. In the first case you are guaranteed to know the colors of the next ball and in the second you have a 50%50\% chance of guessing the next ball correctly. Finally, the probability of guessing correctly on the last ball is 11. Then calculating the expected value of the game from our individual draws:

E[x]=(241)+(231)+(131+23121)+1=176\mathbb{E}[x] = (\frac{2}{4}\cdot 1) + (\frac{2}{3}\cdot 1) + (\frac{1}{3} \cdot 1 + \frac{2}{3}\cdot\frac{1}{2} \cdot 1) + 1 = \frac{17}{6}

So I would pay $176\frac{17}{6} to play this game.

Day Two: June 22

Today’s problems focus on stochastic processes and Markov chains. A couple of these problems come from David Aldous’s STAT 150 page. I also came across a pretty sick compilation of different resources this morning.

Problem 1. A calculating machine uses the digits 00 and 11 and transmits one of these digits through several stages. At every stage, there is a probability pp that the digit will be changed when it leaves and probability q=1pq = 1 - p that it will not. Suppose the machine starts at state 0. What is the probability that the machine will display the correct digit after 2 stages? Solution. We can identify the Markov chain for this problem as below:

010qp1pq\begin{matrix} & 0 & 1\\ 0 & q & p\\ 1 & p & q \end{matrix}

which produces the transition matrix

P=(qppq)P= \begin{pmatrix} q & p\\ p & q \end{pmatrix}

We are interested in finding the probability that the state remains in state 0 after two time periods, which is indexed by the (1,1)(1,1)-entry of P2P^2. Then,

P2=(qppq)(qppq)=(q2+p22qp2pqp2+q2)P^2 = \begin{pmatrix} q & p\\ p & q \end{pmatrix}\begin{pmatrix} q & p\\ p & q \end{pmatrix} = \begin{pmatrix} q^2 + p^2 & 2qp\\ 2pq & p^2 + q^2 \end{pmatrix}

and our desired probability is q2+p2q^2 + p^2.

Problem 2. A transmitter is sending binary code (+ and - signals) that must pass through three relay signals before being sent on to the receiver. At each relay station, there is a 25%25\% chance that the signal will be reversed. Suppose ++ signals make up 60%60\% of the messages sent. If a ++ signal is received, what is the probability that a ++ was sent? Solution. This was a problem in the notes of my statistics class last semester and was solved using a tree diagram. I decided to take a stochastic approach:

Let AA be the event that a ++ was transmitted and BB be the event that ++ is received after it passes through the third relay. We’re interested in finding P(AB)P(A \, | \, B), which by Bayes’ Theorem can be written as

P(AB)=P(BA)P(A)P(B)=P(BA)P(A)P(BA)P(A)+P(BAc)P(Ac)P(A \, | \, B) = \frac{P(B\, | \, A)P(A)}{P(B)} = \frac{P(B\, | \, A)P(A)}{P(B \, | \, A)P(A) + P(B \, | \, A^c)P(A^c)}

Note that AcA^c is the event that a - was transmitted. Let’s consider the Markov chain for this problem:

++0.750.250.250.75\begin{matrix} & + & -\\ + & 0.75 & 0.25\\ - & 0.25 & 0.75 \end{matrix}

giving us the transition matrix

P=(0.750.250.250.75)P3=(0.56250.43650.43650.5625)P= \begin{pmatrix} 0.75 & 0.25\\ 0.25 & 0.75 \end{pmatrix} \to P^3 = \begin{pmatrix} 0.5625 & 0.4365\\ 0.4365 & 0.5625 \end{pmatrix}

We can see that P(BA)=P1,13=0.5625P(B\, | \, A) = P^3_{1,1} = 0.5625 and P(BAc)=P2,13=0.4365P(B \, | \, A^c) = P^3_{2,1} = 0.4365. Then, we have

P(AB)=0.56250.60.56250.6+0.43650.4=0.6585P(A \, | \, B) = \frac{0.5625 \cdot 0.6}{0.5625 \cdot 0.6 + 0.4365 \cdot 0.4} = 0.6585

Problem 3. Consider a Markov chain with two states: 1 and 2. If p1,2=ap_{1,2} = a and p2,1=bp_{2,1} = b. For which values of aa and bb do we have an absorbing Markov chain? Solution. An absorbing Markov chain is one in which every state can reach a state where, once entered, cannot be left. Our transition matrix looks something like this:

P=(?ab?)P= \begin{pmatrix} ? & a\\ b & ?\\ \end{pmatrix}

aa and bb are the probabilities of state 11 changing to 22 and vice versa. In order for a state to remain constant between time periods, we must have at least one of aa or bb be 0 so that upon reaching one of the states, we will leave it.

Problem 4. A Markov chain with the state space {1,2,3}\{1, 2, 3\} has the transition matrix

P=(1/31/31/301/21/3001)P= \begin{pmatrix} 1/3 & 1/3 & 1/3\\ 0 & 1/2 & 1/3\\ 0 & 0 & 1 \end{pmatrix}

Starting from each state, find the expected time until absorption occurs. Solution. Clearly, absorption happens at state 3. Let E[i]\mathbb{E}[i] denote the expected time to reach state 33 from i=1,2,3i = 1, 2, 3. Then, we have

E[1]=1+13E[1]+13E[2]+13E[3]E[2]=1+12E[2]+12E[3]E[3]=0\begin{aligned} \mathbb{E}[1] &= 1 + \frac{1}{3}\mathbb{E}[1] + \frac{1}{3}\mathbb{E}[2] + \frac{1}{3}\mathbb{E}[3]\\ \mathbb{E}[2] &= 1 + \frac{1}{2}\mathbb{E}[2] + \frac{1}{2}\mathbb{E}[3]\\ \mathbb{E}[3] &= 0 \end{aligned}

Walking through the case of E[1]\mathbb{E}[1], we get the recursion in the following manner: if we go forward one time period, then there is a 13\frac{1}{3} chance that we are still at state 11 and our expected time is now 1+E[1]1 + \mathbb{E}[1]. Similarly, we have a 13\frac{1}{3} chance of being at state 22 or 33 respectively, which brings us to E[1]=1+13E[1]+13E[2]+13E[3]\mathbb{E}[1] = 1 + \frac{1}{3}\mathbb{E}[1] + \frac{1}{3}\mathbb{E}[2] + \frac{1}{3}\mathbb{E}[3].

Solving these equations gives us E[i]={5/2if i=12if i=20if i=3\mathbb{E}[i] = \begin{cases} 5/2 & \text{if } i = 1\\ 2 & \text{if } i = 2\\ 0 & \text{if } i =3 \end{cases}

Problem 5. A group of quants wants to determine their average salary but want to do so such that no person has access to anyone else’s salary. Can they accomplish this, and, if so, how? Solution. The quants can do this by having the first quant taking a random number and adding his salary to it and passing that number onto the second quant. Then each subsequent quant will add their salary to the sum and tell the number to the next quant. Finally, the first quant removes the random number they chose and divides by the number of total quants for the average salary.

Day Three: June 23

I threw in some statistics questions for today’s problems in addition to the usual bunch.

Problem 1. There are N lions and 1 sheep in a field. All the lions really want to eat the sheep, but the problem is that if a lion eats a sheep, it becomes a sheep. A lion would rather stay a lion than be eaten by another lion. There is no other way for a lion to die than to become a sheep and then be eaten. When is it safe for any lion to eat? Solution. Let’s consider this similarly to Problem 2 of Day 1. If there is one lion, then it can happily eat the sheep. If there are two lions, no lion would eat the sheep for fear of getting eaten by the other lion. If there are three lions, then a lion eating the sheep would reduce us to the two lion scenario, in which no lion would eat the sheep. We can continue on this train of thought for any number NN and conclude that the sheep will be eaten when NN is odd. I actually think this problem is actually quite similar to the game of Nim or other impartial combinatorial games in the sense that we’re thinking in terms of a recursion.

Problem 2. You draw cards from a deck without replacement. What is the expected number of cards you draw before you get an ace? Solution. I had to refer to Stack Exchange for this question. You can find the solution here. I was initiallly tempted to use μx\mu_x for a negative binomial distribution but I later realized that cards are drawn without replacement. Let DD be the r.v. that represents the number of draws before we draw an ace and assign each of the non-ace cards in the deck a number between 11 and 4848. Then we can define the random indicator variable Xi=1X_i = 1 if the card with label ii was drawn before any ace and 00 otherwise. Then, we have that

D=X1+X2++X48D = X_1 + X_2 + \cdots + X_{48}

From linearity of expectation, we have

E[D]=E[X1+X2+X48]=E[X1]+E[X2]++E[X48]\mathbb{E}[D] = \mathbb{E}[X_1 + X_2 + \cdots X_{48}] = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \cdots + \mathbb{E}[X_{48}]

Let’s consider P(X1=1)P(X_1 =1). If we look card 11 along with the 44 aces, it’s pretty simple to see that P(X1=1)=15P(X_1 = 1) = \frac{1}{5}. It follows that E[X1]=15\mathbb{E}[X_1] = \frac{1}{5}. Symmetry guarantees that all the XiX_i have the same distribution so P(Xi=1)=P(Xj=1)P(X_i = 1) = P(X_j = 1) for all i,j[1,,48]i,j\in[1,\dots, 48]. Then each E[Xi]=15\mathbb{E}[X_i] = \frac{1}{5} and E[D]=485\mathbb{E}[D] = \frac{48}{5}.

Problem 3. You roll a die up to three times. You can decide to stop and choose the number on the die (where the number is your payoff) during each roll. What’s your strategy? Solution. Trading firms often ask these types of questions, where you have to devise an optimal strategy to a given game with uncertainty. Work backwards from the end of the game, we know that the expected value of the last roll is 72\frac{7}{2}. Then, for our second to last roll, it makes sense to reroll if we rolled a 1,2,31,2,3, and just keep the money and quit if we rolled a 4,5,64, 5, 6. Then, the expected value of our last two rolls is 16(4+5+6)+1272=4.25\frac{1}{6}(4 + 5 + 6) + \frac{1}{2}\cdot\frac{7}{2} = 4.25 (it should make sense why we multiply each EV by 12)\frac{1}{2}). Using similar logic to before, it makes sense to reroll if we rolled a 1,2,3,41,2,3,4 and keep the money if we rolled a 55 or 66. Then, our strategy is to roll once if we roll a 55 or a 66, reroll otherwise. When rerolling, we’ll keep anything 44 and beyond and reroll our final time otherwise.

Problem 4. A hat contains 100100 coins, 9999 of them are guaranteed to be fair and 11 that has a 12\frac{1}{2} chance to be double-headed. A coin is randomly chosen at random and flipped 77 times. If it landed heads each time what is the probability that one of the coins is double-headed? Solution. Let’s use Bayes’ Theorem for this question. Let AA be the event that one of the 100100 coins is double-headed and BB be the event that a randomly chose coin lands heads on all 77 flips. We’re interested in finding P(AB)P(A \, | \, B). Then,

  • P(A)=12P(A) = \frac{1}{2}
  • P(Ac)=12P(A^c) = \frac{1}{2}
  • P(BA)=P( all head flips given unfair coin)=1100+12799100P(B \, | \, A) = P( \text{ all head flips given unfair coin}) = \frac{1}{100} + \frac{1}{2^7}\cdot \frac{99}{100}
  • P(BAc)=P( all head flips given no unfair coin)=127P(B \, | \, A^c) = P( \text{ all head flips given no unfair coin}) = \frac{1}{2^7}

The third bullet point can be solved for by breaking down the components of the probability of rolling all 77 heads in the case of having a guaranteed rigged coin, which is 11001+12799100\frac{1}{100}\cdot 1 + \frac{1}{2^7}\cdot \frac{99}{100}. Then we have

P(AB)=(1100+12799100)12(1100+12799100)12+12712=0.3194P(A \, | \, B) = \frac{(\frac{1}{100} + \frac{1}{2^7}\cdot \frac{99}{100})\cdot \frac{1}{2}}{(\frac{1}{100} + \frac{1}{2^7}\cdot \frac{99}{100})\frac{1}{2} + \frac{1}{2^7}\cdot\frac{1}{2}} = 0.3194

So if we roll 7 heads in a row, there is a 32%32\% chance that there is an unfair coin in the bunch.

Problem 5. Let X,YN(0,1)X, Y \sim N(0,1) be i.i.d. random variables. What is the probability that X>3YX > 3Y? Solution. This is a pretty simple problem that I’m using as statistics review. Lets define Z:=X3YZ := X - 3Y. Then we simply need to find P(Z>0)P(Z > 0). We know that ZZ is normally distributed as it’s a linear combination of standard normal variables so we only need to find the mean and standard deviation in order to find P(Z>0)P(Z > 0). Note that

E[Z]=E[X]3E[Y]=0\mathbb{E}[Z] = \mathbb{E}[X] - 3\mathbb{E}[Y] = 0


σ(Z)=σ(X3Y)=σ(X)+(3)2σ(Z)=10\sigma(Z) = \sigma(X-3Y) = \sigma(X) + (-3)^2\sigma(Z) = 10

Note that since ZZ is normally distributed about 00, we technically don’t even need σ(Z)\sigma(Z) since P(Z>0)=12P(Z >0) = \frac{1}{2} for ZN(0,σ)Z \sim N(0, \sigma). Then, P(X>3Y)=12P(X > 3Y) = \frac{1}{2}.

Day Four: June 24

I didn’t get to this until pretty late this evening so I did some relatively simple questions for today.

Problem 1. In unprofitable times corporations sometimes suspend dividend payments. Suppose that after a dividend has been paid the next one will be paid with probability 0.90.9, while after a dividend is suspended the next one will be suspended with probability 0.6. In the long run what is the fraction of dividends that will be paid? Solution. This is another Markov chain problem so we’ll tackle it like we have before. We can call the two states of this chain State 1: “dividend paid” and State 2: “dividend suspended”. We’re provided that p1,1=0.9p_{1,1} = 0.9 and p2,2=0.6p_{2,2} = 0.6, which implies that p1,2=0.1p_{1,2} = 0.1 and p2,1=0.4p_{2,1} = 0.4. This gives us the transition matrix

P=( = \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix}

Let π\pi be the stationary distribution for our Markov chain. In the steady state,

[π1π2]=[π1π2](\begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix} = \begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix}\begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix}

Then, 0.9π1+0.6π2=π10.9 \pi_1 + 0.6\pi_2 = \pi_1 and 0.1π1+0.4π2=π20.1\pi_1 + 0.4\pi_2 =\pi_2. Note also the π1+π2=1\pi_1 + \pi_2 = 1 be definition. Then, solving this system of linear equations gives us that π1=0.8\pi_1 = 0.8 and π2=0.2\pi_2 = 0.2 and

π=[π1π2]=[0.80.2]\pi = \begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}

so 80%80\% of dividends will be paid.

Problem 2. If you repeatedly flip a fair coin. What is the expected number of flips you need to do in order to get a head immediately followed by a tail? Solution. We know that we’ll end with HTHT so let’s think about the tosses we make before this happens. If we roll a heads on our first try, then we have to roll only heads until we roll our final HTHT. For this reason, if there are mm tosses before HTHT, then it has to be of the form TkHmkT^kH^{m-k} where k=0,1,,mk = 0,1, \dots, m. Then let XX be a random variable that describes the number of tosses until we get TT. We can flip TT on our first try (p=12p = \frac{1}{2}), or we could flip heads first and we’d effectively start the process over again (p=12p = \frac{1}{2}). Then,

E[X]=121+12(1+E[X])\mathbb{E}[X] = \frac{1}{2}\cdot 1 + \frac{1}{2}(1 + \mathbb{E}[X])

Solving this gives us E[X]=2\mathbb{E}[X] = 2. Now define YY is the random variable that describes the number of tosses until we get our first HTHT. We can either roll a tails on our first try (p=12p=\frac{1}{2}) and making it so that we have to start over again, or we can roll heads on our first try (p=12p = \frac{1}{2}), and all we need to do now is roll at TT, whose EV we just modeled with XX. Then,

E[Y]=12(1+E[Y])+12(1+E[X])\mathbb{E}[Y] = \frac{1}{2}(1 + \mathbb{E}[Y]) + \frac{1}{2}(1 + \mathbb{E}[X])

We can plug in E[X]=2\mathbb{E}[X] = 2 and find that E[Y]=4\mathbb{E}[Y] = 4! Other solutions to this can be found here.

Problem 3. Let XX be an r.v. such that E[X2]<\mathbb{E}[X^2] < \infty. What constant cc minimizes E[(Xc)2]\mathbb{E}[(X-c)^2]? Solution. I thought that this would be a difficult problem but then I realized that it was extremely simple. Taking the derivative with respect to cc gives us

ddcE[(Xc)2]=ddcE[X22cX+c2]=E[2X+2c]=2E[X]+2c\begin{aligned} \frac{d}{dc}\mathbb{E}[(X-c)^2] &= \frac{d}{dc}\mathbb{E}[X^2 - 2cX + c^2] = \mathbb{E}[-2X + 2c] \\ &= -2\mathbb{E}[X] + 2c \end{aligned}

Setting this equal to 00 makes it pretty clear that c=E[X]c = \mathbb{E}[X] minimizes the expression. You could also solve for this by finding the XX that minimizes the the expression by differenting with respect to XX and get the same conclusion but the question specified finding a cc value. Also, it never hurts to plug this back in and make sure that it is actually a minimum.

Problem 4. What is the expected number of rolls of a fair die needed to get all six numbers? Solution. This was a nice brush-up on geometric distributions. It takes one roll in order to roll out first number. After our first roll, the number of rolls until a second number is rolled is geometrically distributed with success probability p=56p = \frac{5}{6}. Since μX=1p\mu_X = \frac{1}{p} for a geometric distribution, the expected number of rolls until a second number is rolled is 56\frac{5}{6}. Continuing in this fashion, the number if rolls before each additional unique number geometrically distributed with probability p=n6p = \frac{n}{6} where nn is the number of remaining numbers to be rolled. Then,

E[6]=i=166i=14.7\mathbb{E}[6] = \sum_{i = 1}^6 \frac{6}{i} = 14.7

We can extend this further and say that for an nn-sided die,

E[n]=ni=11i\mathbb{E}[n] = n\sum_{i=1}\frac{1}{i}

Problem 5. You are on a game show, and there are 3 doors. Two of the doors conceal something worthless, and one door conceals a valuable prize. The game show host, Monty Hall, knows where the prize is. He lets you pick a door, then he opens one of the remaining two doors to reveal something worthless. He then offers you the chance to switch doors. Should you? Solution. This is the Monty Hall Problem. Lets call the doors A,B,CA, B, C. If you chose AA, you have p=13p =\frac{1}{3} of guessing the prize, and p=23p = \frac{2}{3} of guessing incorrectly. This probability of AA being correct does not change after the host offers to let you switch after he uncovers one of the other doors (lets say BB). In allowing you to switch doors, the host is offering you the option to bet on or against whether your first guess was right with p=13p = \frac{1}{3} or that it was wrong p=23p= \frac{2}{3}. In essence, when you choose door AA there a 23\frac{2}{3} chance that the prize door is either between doors BB or CC. This doesn’t change when you open up door BB to see nothing in it—instead it now means that there is a 23\frac{2}{3} chance that door CC holds the prize so its better for you to switch.

Day Five: June 25

Today’s problems focus on betting games and review of probability distributions.

Problem 1. You play a game where you toss two fair coins in the air and win $1 each time you toss. However, if you have tossed 2 heads at least once, and 2 tails at least once, you lose all your winnings and the game ends. You can also choose to stop playing at anytime. What’s your strategy? Solution. I pulled this problem from stack exchange so you can find some solutions here. Solution 1 on this page derives the solution in a cleaner manner than the solution my friend and I came up with for this.

It takes at least 2 tosses in order to get HHHH and TTTT. Then, after we roll our first bad event we have probability 14\frac{1}{4} to lose everything and probability 34\frac{3}{4} to win an additional dollar. Coin tosses are independent so each kthk^{th} toss we make after our first bad toss, we have probability (34)k(\frac{3}{4})^k of gaining an additional kk dollars and 1(34)k1 -(\frac{3}{4})^k of losing the whole thing. So if we get our first bad toss on toss nn (by which we have acquired nn dollars), our expected value for n+kn+k is E[n+k]=(34)k(n+k)\mathbb{E}[n+k] = (\frac{3}{4})^k(n+k). To find the optimal time to stop tossing, we need to find the boundary of E[n+k]E[n+k+1]\mathbb{E}[n+k] \leq \mathbb{E}[n+k+1]. That is,

(34)k(n+k)(34)k+1(n+k+1)4(n+k)3(n+k+1)4n+4k3n+3k+3n+k3\begin{aligned} (\tfrac{3}{4})^k(n+k) &\leq (\tfrac{3}{4})^{k+1}(n+k+1)\\ 4(n+k) &\leq 3(n+k+1)\\ 4n + 4k &\leq 3 n + 3k + 3\\ n+ k &\leq 3 \end{aligned}

Note that it’s not always optimal to stop at a total number of rolls 3\leq 3. The whole premise of this question revolves around the first bad toss. So if n<3n < 3 (our first bad toss is on toss 1 or 2), we should keep tossing until we’ve tossed 3 times. Otherwise, we should just take our earnings and end the game.

Problem 2. A room of 100 people put their business cards in a hat, then each person randomly draws a business card. What’s the expected number of people who draw their own business card? Solution. Each person has a 1100\frac{1}{100} chance of drawing their particular name, assuming that everyone draws at the same time. Let XiX_i be a Bernoulli r.v. with success being person ii drawing their own card. Then, P(Xi=1)=1nP(X_i = 1) = \frac{1}{n} from our first observation. It follows that

E[Xi]=xRxp(x)=x=01xp(x)=099100+11100=1100\mathbb{E}[X_i] = \sum_{x \in \mathbb{R}}xp(x) = \sum_{x=0}^1 xp(x) = 0 \cdot \frac{99}{100} + 1 \cdot \frac{1}{100} = \frac{1}{100}


E[X1++X100]=E[X1]++E[X100]=n(1n)=1\mathbb{E}[X_1 +\cdots + X_{100}] = \mathbb{E}[X_1] + \cdots + \mathbb{E}[X_{100}] = n(\tfrac{1}{n}) = 1

so we expect 11 person to draw their own name. Note that 100100 is not a special number or anything—if we replace every instance of 100100 with nn in our argument, we observe that our EV is still 11 person.

Problem 3. There are 100100 noodles in a soup bowl you are eating. You are blindfolded and told to take the ends of some noodles and connect them (each end is chose with equal probability). You do this until there are no more free ends. What is the expected number of circles created in this fashion? Solution. This is actually be solved in a stochastic manner. Let f(n)f(n) be a random variable that describes the number of circles that are made from connecting noodles. Starting from n=1n=1 noodle, you must connect the two ends together, forming E[f(1)]=1\mathbb{E}[f(1)] = 1 circle. For n=2n=2 noodles, there are 4 ends and you must make 2 connections, forming (42)=6\binom{4}{2} = 6 possible connections. Of these, 22 connections will connect the same ends of the same noodle together, giving us 11 noodle and 11 circle. The other four combinations give us a single noodle. Notice that we’re only doing so much as to connect two of the ends, which brings us to a n=1n=1 case. Then the expected number of circles for n=2n=2 is

E[f(2)]=23(1+E[f(1)])+46E[f(1)]\mathbb{E}[f(2)] = \tfrac{2}{3}(1 + \mathbb{E}[f(1)]) + \tfrac{4}{6}\mathbb{E}[f(1)]

Solving this gives us that E[f(2)]=43=1+13\mathbb{E}[f(2)] = \frac{4}{3} = 1 + \frac{1}{3}. Moving on to n=3n=3, we have (62)=15\binom{6}{2} = 15 choices for connections. Of these, 33 choices will yield 11 circle and 22 noodles and the other 1212 will simply yield 22 noodles. Then, we have

E[f(3)]=315(E[1+f(2)])+1215E[f(2)]\mathbb{E}[f(3)] = \tfrac{3}{15}(\mathbb{E}[1 + f(2)]) + \tfrac{12}{15}\mathbb{E}[f(2)]

Solving this yields E[f(3)]=2315=1+13+15\mathbb{E}[f(3)] = \frac{23}{15} = 1 + \frac{1}{3} + \frac{1}{5}. There’s a pretty clear pattern that’s starting to appear. If we extend it to nn noodles in general, we have that

E[f(n)]=1+13+15++12n1=k=1n12k1\mathbb{E}[f(n)] = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{2n-1} = \sum_{k = 1}^n \frac{1}{2k -1}

Plugging n=100n=100 gives us E[100]3.28\mathbb{E}[100] \approx 3.28 (I cheated a bit and used a calculator to find this sum).

Problem 4. Two archers shoot at a target. The distance of each shot from the center of the target is uniformly distributed from 0 to 1, independently of the other shot. What is the PDF (probability density function) of the distance from the center for the losing shot? Solution. Let XX be the distance from the center of the shot by Archer 1 and YY be that of Archer 2. Let Z=max{X,Y}Z = \max\{X,Y\} be the distance from the center of the losing shot. As XX and YY are uniformly distributed over [0,1][0,1], we have that for all z[0,1]z\in[0,1],

P(Xz)=P(Yz)=z010=zP(X\leq z) = P(Y\leq z) = \frac{z - 0}{1 - 0} = z

Then, as XX and YY are independent,

FZ(z)=P(max{X,Y}z)=P(Xz,YZ)=P(Xz)P(Yz)=z2\begin{aligned} F_Z(z) &= P(\max\{X,Y\}\leq z) = P(X \leq z \, , \, Y \leq Z)\\ &= P(X \leq z)P(Y \leq z) = z^2 \end{aligned}

When we differentiate we then get the pdf of ZZ

fZ(z)={2z if z[0,1]0 otherwisef_Z(z) = \begin{cases} 2z& \text{ if } z\in[0,1]\\ 0& \text{ otherwise} \end{cases}

This is an interesting problem that I haven’t seen before. I’ve seen another form of the question that asks for the pdf of the winning shot, which is a bit more tricky as ZZ would be defined as min{X,Y}\min\{X, Y\} and it wouldn’t be clear that we could use the P(X,Yz)P(X,Y \leq z) since the minimum requires only one of them to satisfy the condition.

Problem 5. Let X1,XnX_1, \dots X_n be independent random variables uniformly distributed on [0,1][0,1]. Find P(X1++Xn1)P(X_1 + \cdots + X_n \leq 1)? Solution. Like Problem 33, I’m going to try to start from the n=1n=1 case and try to build up a solution. Clearly, P(X1)=1P(X \leq 1) = 1 by definition. P(X1+X21)P(X_1 + X_2 \leq 1) is the probability that X1X_1 and X2X_2, distributed over the unit square, lie on or below the line that separates the lower left and upper right triangles so P(X1+X21)=12=12!P(X_1 + X_2 \leq 1) = \frac{1}{2} = \frac{1}{2!}. Moving on to n=3n =3, P(X1+X2+X3)P(X_1 + X_2 + X_3) describes the probability that the set of points in the unit cube all lie in the bottom-left-front triangular pyramid (probability 16)=13!\frac{1}{6}) = \frac{1}{3!}. Again, a bit of a pattern is showing up: it seems like P(X1++Xn)=1n!P(X_1 + \cdots + X_n) = \frac{1}{n!}. We can confirm this with induction of a more general case, that for 0t10 \leq t \leq 1

P(X1++Xnt)=tnn!P(X_1 + \cdots + X_n \leq t) = \frac{t^n}{n!}

For simplicity sake, I’ll call Sn:=X1+X2++XnS_n := X_1 + X_2 + \cdots + X_n. We’ve already proved the base case earlier in our solution. Then suppose our assumption holds for nn, then for n+1n+1:

P(Sn+1t)=01P(Sn+xt)f(x)dx=0t(tx)nn!dx=tn+1(n+1)!\begin{aligned} P(S_{n+1}\leq t) &= \int_0^1P(S_n + x \leq t)f(x)\,dx = \int_0^t\frac{(t-x)^n}{n!}\, dx \\ &= \frac{t^{n+1}}{(n+1)!} \end{aligned}

and thus our claim is proved by induction. This last part does require a bit of massaging but should be clear after applying a bit of calculus/analysis. Then, it follows that P(Sn1)=1n!P(S_n \leq 1) = \frac{1}{n!}

Day Six: June 26

Most of the questions today come from A Practical Guide to Quantitative Finance Interviews and past interview questions.

Problem 1. Bond AA will default next year with p=0.5p = 0.5 and bond BB will default next year with p=0.3p= 0.3. What is the range of probability that at least one bond defaults and what is the range of their correlation? Solution. The upper bound on the the probability of at least one bond defaulting takes place when AA defaulting and BB defaulting are mutually exclusive, in which case,

P(A or B defaults)=P(A)+P(B)=0.5+0.3=0.8P(\text{A or B defaults}) = P(A) + P(B) = 0.5 + 0.3 = 0.8

For the lower bound, we consider the case when AA and BB are completely dependent events. Then,

P(A or B defaults)=max{A,B}=0.5P(\text{A or B defaults}) = \max\{A, B\} = 0.5

Then P(A or B defaults)[0.5,0.8]P(\text{A or B defaults}) \in [0.5, 0.8]. To calculate the correlation between AA and BB, let IAI_A and IBI_B be indicator variables for the events that AA and BB default and let ρ\rho be their correlation. We have that E[IA]=0.5\mathbb{E}[I_A] = 0.5 and E[IB]=0.3\mathbb{E}[I_B] = 0.3. Since AA and BB are Bernouli random variables, we have that σIA=pA(1pA)=0.52=0.25\sigma_{I_A} = p_A(1 - p_A) = 0.5^2 = 0.25. Similarly, σIB=0.21\sigma_{I_B} = 0.21. We have that

P(A or B defaults)=E[IA]+E[IB]E[IAIB]=E[IA]+E[IB](E[IA]E[IB]Cov(IA,IB))=0.5+0.3(0.50.3ρσIAσIB)=0.650.212ρ\begin{aligned} P(\text{A or B defaults}) &= \mathbb{E}[I_A] + \mathbb{E}[I_B] - \mathbb{E}[I_AI_B]\\ &= \mathbb{E}[I_A] + \mathbb{E}[I_B] - (\mathbb{E}[I_A]\mathbb{E}[I_B] - Cov(I_A, I_B))\\ &= 0.5 + 0.3 - (0.5 \cdot 0.3 - \rho\sigma_{I_A}\sigma{I_B})\\ &= 0.65 - \frac{\sqrt{0.21}}{2 \rho} \end{aligned}

Plugging in the bounds of P(A or B defaults)P(\text{A or B defaults}), we have ρ[37,37]\rho \in \left[-\sqrt{\tfrac{3}{7}}, \sqrt{\tfrac{3}{7}}\right].

Problem 2. What is the expected number of dice rolls until we get two 66’s in a row? Solution. This is similar to our expected value of HTHT problem. Let XX be a random variable that describes the number of throws to get two sixes in a row. There are three scenarios that we should consider:

Case 1: throwing two consecutive sixes (p=136p = \frac{1}{36})
Case 2: throwing a six on the first toss and a different number on the second (p=536p = \frac{5}{36})
Case 3: nothing throwing a six on the first toss (p=56p = \frac{5}{6})

In Case 1, were are done and our ev is 22. In Case 2, rolling a different number means we’re exactly back where we started and our ev is 2+E[X]2 + \mathbb{E}[X] since we “wasted” our first two throws. In Case 3, we’re back where we started and we’ve only used up the first throw, giving expecation of 1+E[X]1 + \mathbb{E}[X]. Then,

E[X]=1362+536(2+E[X])+56(1+E[X])=4236+3536E[X]\begin{aligned} \mathbb{E}[X] &= \tfrac{1}{36}\cdot 2 + \tfrac{5}{36}(2 + \mathbb{E}[X]) + \tfrac{5}{6}(1 + \mathbb{E}[X])\\ &= \tfrac{42}{36} + \tfrac{35}{36}\mathbb{E}[X] \end{aligned}

Solving this gives us E[X]=42\mathbb{E}[X] = 42 so we expect to roll 4242 times total in order to get our first string of consecutive 66‘s.

Problem 3. You flip a weighted coin with P(heads)=0.6P(\text{heads}) = 0.6 four times. Every time that a heads is rolled AA wins $1\$1 and every time a tails is flipped, BB wins $1\$1. What is the expected value of a bet where if A wins overall, you get his winnings, if B wins overall you get 0. Solution. This questions is from DRW’s Glassdoor page. It’s a bit unclear what the question means by expected value of a bet so I’ll be solving for the expected value of the game. Additionally, since it doesn’t state what happens if AA and BB tie, I’ll be increasing the number of rolls to five. Note that AA wins if we roll 3,4,53,4,5 heads and BB wins if we roll 0,1,20, 1, 2 heads. Let XX be a Bernoulli random variable with success being flipping heads (p=0.6p= 0.6). Then, XX follows a binomial distribution and we can caculate the expected value of the game as follows:

E[X]=xRxp(x)=x=35xb(x;5,0.6)=x=35x(nx)px(1p)5x=3(53)(0.6)3(0.4)2+4(54)(0.6)4(0.4)1+5(55)(0.5)52.23\begin{aligned} \mathbb{E}[X] &= \sum_{x\in \mathbb{R}}xp(x) = \sum_{x= 3}^5xb(x; 5, 0.6) = \sum_{x= 3}^5x\binom{n}{x}p^x(1-p)^{5-x}\\ &= 3 \binom{5}{3}(0.6)^3(0.4)^2 + 4 \binom{5}{4}(0.6)^4(0.4)^1 + 5 \binom{5}{5}(0.5)^5\\ &\approx 2.23 \end{aligned}

Then, the expected value of the game is 2.232.23, so it would make sense of us to play is so long as our cost of playing is less than $2.23\$2.23.

Problem 4. You’re presented with two empty jars and 100100 marbles on a table, 5050 of which are white and the other 5050 are black. You are to put all 100100 of the marbles into the two jars in any way you choose. I then blindfold you and shakethe jars up to ensure good mixing and rearrange the placing of the jars randomly. You can then request the left-hand jar or the right-hand jar. You get to choose exactly one jar and and can withdraw at most one marble from the jar and you do not get a second chance if you are unhappy with your choice. How many of each color marble should you put in each jar to maximize the probability your blindfolded random draw obtains a white marble? Solution. At first I thought that both jars needed to contain 5050 marbles, in which case it didn’t matter how we distributed the black and white marbles. Due to the mixing and the randomization of which of the two jars you’re picking, you have p=0.5p=0.5 of picking either jar. Say you have xx white marbles in one jar and 50x50-x in another jar. Then, your probability of picking a white marble is 12x50+1250x50\frac{1}{2} \cdot \frac{x}{50} + \frac{1}{2} \cdot \frac{50 - x}{50} which gives a 50%50\% chance of picking a white marble no matter how you distribute them.

I then realized that we could distribute the marbles however we’d like, meaning that we could keep at little as 00 marbles in one jar and all 100100 in the other jar. Instead of divising a function to describe how to optimize for this problem I decided to approach it with several cases. We know we have p=12p = \frac{1}{2} of choosing either jar. We want to maximize the chance of picking a white marble regardless of which jar you choose. This can be done by placing 11 white marble in the first jar, and the other 9999 marbles in the second jar. This ensures that we have p=121+1249990.75p = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{49}{99} \approx 0.75 of picking a white marble. Just testing out some other placements of marbles it’s clear that this is the optimal configuration. Approaching the problem analytically, we simply need to find the maximum of the function

f(x,y)=12xy+1250x100yf(x,y) = \tfrac{1}{2} \cdot \tfrac{x}{y} + \tfrac{1}{2} \cdot \tfrac{50 -x}{100 -y}

where xx is the number of white marbles we place in the first jar and yy is the total number of marbles we place in the first jar.

Problem 5. I will spin a fair roulette wheel with five sections. Four of the five sections pay 11 and the other pays 55. If the cost is $1.5\$1.5 per spin should you play the game? What if you can only spin once and the payoffs to enter and cost per spint were multiplied by 10001000? Solution. This is a really simple EV problem. Let XX be the payoff of playing the game. Then,

E[X]=45×1+15×5=1.8>1.5\mathbb{E}[X] = \tfrac{4}{5} \times 1 + \tfrac{1}{5} \times 5 = 1.8 > 1.5

When you have the option of playing as much as you like, it makes sense to play the game as the actual payoff converges to the expected payoff in the long run so we expect to make $0.30\$0.30 profit every 55 times we play.

If we can only spin once, our EV for the game doesn’t change. However, this scenario guages how risk-averse we might be: 80%80\% of the time we expect to lose 5050 cents, and 20%20\% of the time we expect to win $3.50\$3.50 beyond what we spent to play the game. Since the cost of the game is relatively low, I would probably still take the bet. However, when the numbers are scaled up by 10001000, we either have a net loss of $500\$500 or net gain of $3500\$3500. While the problems hasn’t changed in nature, the risk of playing the game has increased dramatically, and depending on my initial amount of money, I would be much more cautious when playing.

Day Seven: June 27

Todays problems focus on betting games and expected value.

Problem 1. Suppose there are 1111 pirates who are placing their treasure in a safe. As a democratic group of pirates, they have decided that any majority of the pirates should be able to open the safe. They decide to implement this by placing several locks on the the safe, which all need to be openned to open the safe. Each lock can have multiple keys but each key can only open one lock. What is the smallest number of locks needed to secure the safe in this manner? In addition, how many keys should each pirate carry if each pirate can carry multiple keys? Solution. Note that any combination of 55 pirates should not be able to open the safe. That is, there must be a unique lock for every combination of 55 pirates such that none of these pirates have the key to this lock. Then, there should be a total of (115)=462\binom{11}{5} = 462 locks. Each of these locks should have 66 copies in order maintain the majority criterion and these keys should be evenly distributed between all 1111 pirates, giving us 462611=252\frac{462 \cdot 6}{11} = 252 keys per pirate.

Problem 2. There is a population of ants that for each time period has p=0.2p = 0.2 of dying out (E), p=0.5p = 0.5 of staying the same (S), and p=0.3p= 0.3 of doubling in size. Is the ant population likely to die long term? Solution. This is a spinoff of a question regarding amoeba populations from A Practical Guide. Lets call P(E)P(E) the probability that the ant population goes extinct. We can break this down into the different conditional probabilities: P(ES)P(E\, | S), P(EE)P(E\, | E), and P(ED)P(E\, | D). P(ES)=P(E)P(E \, |\, S) = P(E) since the state is the same as the beginning state, P(ED)=P(E)2P(E\, |\, D) = P(E)^2 (assuming each additional population of ants is independent to one another) as there are now two populations of ants, and P(EE)=1P(E \, | \, E) = 1. Then,

P(E)=0.5P(E)+0.3P(E)2+0.21P(E) = 0.5 \cdot P(E) + 0.3 \cdot P(E)^2 + 0.2 \cdot 1

Solving for this gives us that P(E)=23P(E) = \frac{2}{3} so it is quite likely the ant population dies out. The question doesn’t clarify what it means to double in size long term and EE, DD, and SS are not collectively exhaustive events so it’s quite tricky to calculate the other two outcomes. One could potentially use a Markov chain to simulate what happens in the future

Problem 3. A gambler starts with an initial fortune of ii dollars. On each successive game, the gambler wins $1\$1 white probability pp, 0<p<10 < p < 1, or loses $1\$1 with probability q=1pq = 1-p. He will stop if he ever accumulates NN dollars or loses all his money. What is the probability that he will end up with NN dollars? Solution. This is the gambler’s ruin problem. Let PiP_i denote the probability that the gambler’s fortune will reach NN instead of 00 for each initial state 0iN0 \leq i \leq N. Note that P)0=0P)0 = 0 and PN=1P_N = 1. The next after ii is going to be i+i+ with probability pp or i1i-1 with probability qq. Then, Pi=pPi+1+qPi1P_i = pP_{i+1} + qP_{i-1}. As p+q=1p +q =1, we have that

Pi+1Pi=qp(PiPi1)=(qp)2(Pi1Pi2)=(qp)i(P1P0)P_{i+1} - P_i = \frac{q}{p}(P_i - P_{i-1}) = \left(\frac{q}{p}\right)^2(P_{i-1} - P_{i-2}) = \left(\frac{q}{p}\right)^i (P_1 - P_0)

We can then build an expression for PiP_i from the ground up starting from P2P_2:
P1=pP2+qP0P2=1pP1=[1+qp]P1P_1 = pP_2 + qP_0 \to P_2 = \frac{1}{p}P_1 = \left[1 + \frac{q}{p}\right]P_1
P2=pP3+qP1P3=1qP2qpP1=[1+qp+(qp)2]P1P_2 = pP_3 + qP_1 \to P_3 = \frac{1}{q} P_2 - \frac{q}{p}P_1 = \left[1 + \frac{q}{p} + \left(\frac{q}{p}\right)^2\right] P_1
Pi=[1+qp++(qp)i1]P1P_i = \left[1 + \frac{q}{p} + \cdots + (\frac{q}{p})^{i-1}\right]P_1 Note that the terms in the brackets is just a finite geometric sum. Applying this to PNP_N,

PN=1=[1+qp++(qp)N1]P1={1(qp)N1qpP1 if qp1NP1 if qp=1P_N = 1 = \left[1 + \frac{q}{p} + \cdots + \left(\frac{q}{p}\right)^{N-1}\right]P_1 = \begin{cases} \frac{1- (\frac{q}{p})^N}{1 - \frac{q}{p}}P_1& \text{ if } \frac{q}{p} \neq 1 \\ NP_1& \text{ if } \frac{q}{p} = 1 \end{cases}

We can manipulate this to solve for PiP_i through P1P_1:

P1={1qp1(qp)NP1 if qp11N if qp=1 and Pi={1(qp)i1(qp)NP1 if qp12iN if qp=12P_1 = \begin{cases} \frac{1- \frac{q}{p}}{1 - \left(\frac{q}{p}\right)^N}P_1& \text{ if } \frac{q}{p} \neq 1 \\ \frac{1}{N}& \text{ if } \frac{q}{p} = 1 \end{cases} \text{ and } P_i = \begin{cases} \frac{1- \left(\frac{q}{p}\right)^i}{1 - \left(\frac{q}{p}\right)^N}P_1& \text{ if } \frac{q}{p} \neq \frac{1}{2} \\ \frac{i}{N}& \text{ if } \frac{q}{p} = \frac{1}{2} \end{cases}

Given even odds of winning and losing each round, our probability of coming out with NN dollars is proportional to our beginning state. What’s interesting is that even if we decrease the odds of success slightly, say changing it from 12\frac{1}{2} to 3880\frac{38}{80}, there is a drastic decrease in the ability to come out with NN dollars versus losing everything. I hope to include a Markov chain version of this problem with specific constraints and work through that sometime soon.

Problem 4. Suppose you roll a dice and are paid the value that you roll. If you roll a 5,65,6 you can roll again and if you roll 1,2,3,41,2,3,4 the game ends. How much would you pay to play this game? Solution. Let XX be the payoff of playing this game. There is p=23p = \frac{2}{3} that you roll a losing number and your payoff is what you rolled the first round. In this case, our expected value is the average of {1,2,3,4}=52\{1,2,3,4\} = \frac{5}{2}. Also, there is a 13\frac{1}{3} chance where we roll a 55 or a 66 and have the chance to roll again, bringing us back to our initial state. Then, we have

E[X]=2352+13(112+E[X])\mathbb{E}[X] = \frac{2}{3}\cdot \frac{5}{2} + \frac{1}{3}(\frac{11}{2} + \mathbb{E}[X])

Solving this gives us E[X]=214\mathbb{E}[X] = \frac{21}{4}. Then I would pay up to $5.25\$5.25 to play this game.

Problem 5. Your recruiter loads two bullets separated by one chamber into a 6-chamber revolver. He then spins it,points it at his head and shoots but survives since he fired an empty chamber. You’re given the gun and must fire at your head but you may choose to spin the barrel first or take the shot directly. Unfortunately, another bullet will be loaded into the gun if you decide to spin. Do you spin the barrel? Solution. If we spin, we have a 36\frac{3}{6} chance of dying as we have randomized the location of the next shot relative to the chambers. If we don’t there are five chambers left, two of which have bullets. However, these bullets are staggered by one chamber so the number of configurations of the two bullets is limited. Let’s number the chambers in order from 11 through 66. Let’s say that the bullets are in chambers 11 and 33. Given that your recruiter survived, he must have fired from chambers 2,4,52, 4, 5 or 66, which occur equally likely. If he fired chamber 22 or 66, then the next shot will have a bullet and if he fired 44 or 55, then the next shot will be safe. Then you have 50%50\% chance of dying if we shoot immediately, which is equal to the chance of dying if we decided to spin. Then it does not matter whether we spin or not since we have an equal chance of surviving the next round regardles of how we act.

Bonus. You have xx red cards and yy blue cards. I flip them over one at a time. The probability of flipping a particular color is proportional to the amount of those colored cards left. You start with 11 and every flip you can bet some proportion of your money on red or blue. If you win the bet, you gain twice your bet, but if you lose the bet, you gain nothing. What is the strategy that maximizes expectancy and minimizes variance? Solution. I’ll be typing up the solution later!

Week One Review

This week, I covered mostly probability games, Markov chains, and some combinatorial brain teasers. I realized that I still have a lot intution to build on how analytically to approach each problem, which I’ll keep in mind in future weeks. I hope to be posting some more challenging problems as well, since the ones I’m currently working on are not overly difficult. Next week I hope to include some topics on options and market making and reviewing some statistics and algorithms to add some variety to the problems I’ve been doing. I’m also doing readings on game theory so hopefully I’ll be able to include some more nuanced questions on winning strategies and other related topics.

Thanks for tuning in and below are a couple of resources that I used this week that might be helpful: