# Probability as Counting Success & Combinatorics
Most brainteasers ask you to calculate probability or expected value of something. That's because finance people care about prices of things, and prices look random. The better they can predict future prices, the more money they make. Probability helps you reason about future / uncertain events, so finance people use it.
---
## Probability Basics
Here's all you need to know for most brainteasers.
**Probability** is sort of a weight of how likely a certain outcome is. You measure it as:
$$P(\text{outcome}) = \frac{\text{Number of successful outcomes}}{\text{Number of all possible outcomes}}$$
So if you toss a coin, probability of getting heads is $\frac{1}{2}$. That's because there's 1 successful outcome (tossing a heads) out of 2 possible outcomes (tossing heads or tails).
**When to Use?** A lot of questions simply ask for probability / chance of some outcome. Simply count successful outcomes and divide by all possible outcomes.
**Expected value** is the best guess of an outcome. It's a sum of all possible outcomes weighted by their probabilities:
$$E(X)=\sum P(X) \cdot X $$
So if you toss a coin and get €1 for heads and €0 for tails, my best guess payoff of this game is $$\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0=\frac{1}{2}$$.
**When to Use?** Some questions literally ask for expected value of some game / process. Others ask you for fair price of a game. Same thing - if you're paying a price to play a game, you should pay however much you expect to win. Otherwise the game is not fair to either you or the person selling you the game. So fair price of a game = expected value / payoff of a game. Also, sometimes they'll ask 'would you pay X to play this game?'. That's your cue to calculate expected value. You should only pay if you expect to make $\geq X$ from the game.
## Grouping
Often you'll be asked for probability of some outcome, which itself is a subset of the possible outcomes. So e.g. what's the chance you roll an even number on a 6-sided die? The possible outcomes are anything 1-6, and the *success outcome* are rolls 2, 4 and 6 - a subset of all the outcomes. You have 3 outcomes in this subset, and 6 possible outcomes $\Rightarrow$ probability is $\frac{3}{6}=0.5$. Let's see this in action, in a real-life interview question asked by Jane Street:
<div style="display: flex; justify-content: space-between; align-items: baseline; width: 100%;">
<h2>Interview Question</h2>
<span style="font-size: var(--font-s); font-style: italic; color: #333;">Goldman Sachs</span>
</div>
---
You roll two 6-sided die, and get paid the maximum of the two face values. What's the fair price of this game?
<div>
<button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button>
<div class="solution">
As we said, fair price of a game = expected value we'd receive from playing it. We calculate this as the sum of possible maximum values (1-6) times their probabilites. 6 is the max if first die is 6 and second die is anything 1-5 (5 outcomes); if first die is anything 1-5 and second is 6 (5 outcomes); and if both are 6 (1 outcome). 11 in total: two symmetric cases where one die is the maximum value and other is strictly smaller, and one case where they both have the max value. Similarly, 5 is max in 9 cases; 4 in 7 cases and so on. The pattern is: n is the maximum of the two in 2n-1 ways. Each combination is equally likely, and there are 36 of them in total (6 possibilities for first die $\cdot$ 6 possibilities for the second).<br><br>Summing up all the outcomes multiplied with their probabilities, we get $EV = \sum_{n=1}^6 \frac{1}{36}\cdot (2n-1)=\frac{161}{36}$.
</div>
</div>
## Probability Trees
Often in brainteasers you have multiple iterations of some process. So e.g. you flip a coin a number of times, or you roll a few dice, or you draw a number of cards. To handle such problems, we need to know how to combine probabilities of multiple events.
For intuition, picture two events A and B as sets, and their probability as their surface.
<img src="/static/images/probability_geometric.png" alt="probability_geometric">
Then:
$$P(\text{A or B})=P(A) + P(B) - P(\text{A and B})$$
Or if A and B can't occur at the same time, then P(A and B)=0. Also, we have probability of two events happening simultaneously:
$$P(\text{A and B}) = P(A|B) P(B) = P(B|A)P(A)$$
Or if A and B are independent - i.e. one happening doesn't affect the chance of other happening - then $P(A|B)=P(A)$ and $P(B|A)=P(B)$.
Why is this useful? Because often you're asked for probability of an outcome that can happen in multiple ways. Like in the question above - 6 could be a maximum of two dice in 11 different ways. And all these ways are mutually exclusive - they can't happen at the same time. You *either* rolled 1 and 6 *or* 2 and 6 - not both. So if outcome A happens in multiple ways (e.g. B, C and D), which are mutually exclusive, we can find its probability using formulae from above:
$$P(A) = P(A|B) \cdot P(B) + P(A|C) \cdot P(C) + P(A|D) \cdot P(D)$$
This is the **law of total probability**. We use it *a lot*. Best way to visualise it is to draw a probability tree:
<img src="/static/images/total_probability_tree.png" alt="Probability Tree" style="max-width: 100%;">
Every branch is the transition from one event to another, and it has some probability. So this tree could describe the toss of two coins: two possible outcomes for the first toss and two for the second. Probability of any branch is 0.5 - as tails and heads have even chance. To get probability of a branch from start to finish, just multiply the probabilities of composing branches. This gives you one full possible scenario. So e.g. probability of rolling H on first and T on second is $0.5 \cdot 0.5=0.25$. Then, if multiple branches end up at same event, you can find the total probability by summing the branches - as they can't happen at the same time. So e.g. event of having the same face on both tosses can happen if you got HH or TT. So you'd find probability as $P(HH) + P(TT) = P(H)\cdot P(H) + P(T)\cdot P(T)=0.25 + 0.25=0.5$.
Make sure you understand what we just did, as this will be one of your first tools to throw a lot of brainteasers. It lets you see the problem's structure and will guide you to the next step.
**When to Use?** It's most useful when the game / experiment has a small, finite number of iterations (e.g. 3 coin tosses, 4 dice flips, 5 cards drawn etc.)
<div style="display: flex; justify-content: space-between; align-items: baseline;">
<h2>Interview Question</h2>
<span style="font-size: var(--font-s); font-style: italic; color: #333;">Optiver</span>
</div>
---
You go flipping a coin and as you do this you keep track of the number of heads and tails you get. You can think of this as a race between heads and tails. For example, if there are 9 flips and you have landed on heads 7 times and tails 2 times, then heads is winning the race by 5. We now flip a coin 3 times. What is the probability that the side you flip first will be losing the race?
<div>
<button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button>
<div class="solution">
Let's draw a tree of all that can happen. You flip 3 times.<br><br><img src="/static/images/heads_tails_race.png" alt="img" style="width: 100%; max-width: 800px;"><br><br>As you see each path corresponds to one possible outcome scenario - e.g. HTT or THT. No two paths can occur at the same time. Only the two paths in bold lead to desired outcome: either you flip H first and then get two T, or flip T first and get two H. Recall the law of total probability: $$P(\text{first flip loses}) = P(\text{first flip loses | H first}) P(\text{H first}) + \\P(\text{first flip loses | T first})P(\text{T first})$$ Notice that branches are all independent, with probability $\frac{1}{2}$, so you get $\left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3=\frac{1}{4}$. You can also see this as counting 'successful paths' out of all possible paths, because the paths are independent and all with equal probability ($\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2}$). So we have 2 successful paths out of 8 possible ones $\Rightarrow$ probability is $\frac{2}{8}=\frac{1}{4}$.
</div>
</div>
## Combinatorics
Often it's not this easy to count the successful outcomes. E.g. in scenarios where there's many ways for successful outcome to occur, too many to count. This is where combinatorics comes in.
There's really 5 things to know here, so learn them:
The number of ways to order $n$ elements from first to last is:
$$n! = n\cdot (n-1) \cdot (n-2)... 1$$
The number of ways to pick $r$ elements out of a group of $n$, if we *do* care about the order of picking is:
$$\frac{n!}{(n-r)!}$$
The number of ways to pick $r$ elements out of a group of $n$, if we *don't* care about the order of picking, is:
$$\binom{n}{r}=\frac{n!}{r! (n-r)!}$$
The number of $n$-long sequences where for each element you can choose between $r$ options is:
$$r^n$$
The number of ways to sort $n$ balls into $r$ boxes of size $n_1$, $n_2$, ..., $n_r$ is:
$$\frac{n!}{n_1!\cdot n_2!...n_r!}$$
**When to Use?** Use these when your game / experiment has finite iterations, but there's too many outcomes to draw on a small diagram.
Now let's see them all in action:
<div style="display: flex; justify-content: space-between; align-items: baseline;">
<h2>Interview Question</h2>
<span style="font-size: var(--font-s); font-style: italic; color: #333;">Optiver</span>
</div>
---
At a dinner party, seven guests with different wealth levels randomly sit at a circular table. What's the probability they'll end up seated in order of increasing wealth (clockwise or counterclockwise)?
<div>
<button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button>
<div class="solution">
To determine the probability that seven people, each with a unique wealth level, sit around a circular table in increasing order of wealth, we start by fixing one person - the one with the lowest wealth - in a specific seat. This fixed position serves as our reference point and eliminates any rotation ambiguity.<br><br>Now, with this individual fixed, there are 6 other people left to arrange in the remaining seats. The total number of ways to arrange these six individuals is 6!, or 720. We use this as we're arranging all 6 people, and the order matters.<br><br>Out of these 720 arrangements, only two will result in everyone sitting in increasing order of wealth: one arrangement will be in a clockwise direction, and the other in a counter-clockwise direction.<br><br>Therefore, the probability of the individuals sitting in increasing wealth order is given by the ratio of these two favorable arrangements to the total arrangements: $\frac{2}{720}$. Simplifying this, we get a $\frac{1}{360}$.
</div>
</div>
<div style="display: flex; justify-content: space-between; align-items: baseline;">
<h2>Interview Question</h2>
<span style="font-size: var(--font-s); font-style: italic; color: #333;">Jane Street</span>
</div>
---
You have 4 fair coins, and you flip them all. What's the chance of getting an even number of heads?
<div>
<button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button>
<div class="solution">
Let's simply count the number of outcomes where we get an even number of heads, as all outcomes are equally likely. To have an even number of heads, we need either 0, 2 or 4 heads. In how many ways can we have 0 heads? One only, as $\binom{4}{0}=1$. We use this because we don't care about the order in which the heads occur, just that a set number of them appears.<br><br>We can also have 2 heads in $\binom{4}{2}=6$ or 4 heads in $\binom{4}{4}=1$ ways. In total, 8 outcomes where we have an even number of heads. How many total outcomes? Well we have 4 coins, so 4 letter sequence built out of H or T - two options. Recall the formula: there's $2^4=16$ possible sequences. Probability is then successful outcomes by all possible outcomes: $\frac{8}{16}$.<br><br>Notice another way to view this is via the probability tree: we've counted 8 successful paths, each of which is composed of 4 branches. Each branch has probabiltiy $\frac{1}{2}$ - since each coin lands tails or heads with chance $\frac{1}{2}$. Therefore a path has probability $\frac{1}{2^4}$. These paths can't occur at the same time - they are different scenarios, so law of total probability applies. The sum of successful paths gives us: $8\cdot \frac{1}{2^4}$.
</div>
</div>
<div style="display: flex; justify-content: space-between; align-items: baseline;">
<h2>Interview Question</h2>
<span style="font-size: var(--font-s); font-style: italic; color: #333;">Goldman Sachs</span>
</div>
---
If two teams play max 6 basketball games, the team that wins 4 games first is the winner. It can also happen that each team gets 3 points, in which case a 7th deciding game is played. I offer you a bet for 0.35 EUR where you receive 1 EUR if it comes to the 7th game (i.e. you pay me 0.35 EUR to take the bet). Would you take it?
<div>
<button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button>
<div class="solution">
When you're asked whether you'd buy some bet/game, the question is asking you for fair price of the game, i.e. the expected value. You get 1 EUR when it comes to 7th game and 0 otherwise, so the fair value of the game is: $$EV = p\cdot 1 + (1-p)\cdot 0 $$ where $p$ is the probability it gets to the 7th game, which we must now find.<br><br>It comes to the 7th game only if the outcome by the 6th game is 3-3. In how many ways can this happen? Essentially we're asking in how many ways can we distribute 6 balls (games) into 2 boxes (teams) of 3 each (each team wins 3 games). We have the formula for the job. This happens in $\frac{6!}{3!\cdot 3!}=20$ different ways.<br><br>How probable is each of these outcomes? Well each game has $\frac{1}{2}$ chance of being won by either team, so any 3-3 combination has probability $(\frac{1}{2})^6$. Thus, the total probability of a 3-3 score is $20\cdot (\frac{1}{2})^6$, which is 0.3125.<br><br>Recall we are being offered to play the game for 0.35 EUR, but expected winnings from playing it are only 0.3125. Therefore, we shouldn't buy the bet.
</div>
</div>
## Executive Summary
- **Probability** is $\frac{\text{number of successful outcomes}}{\text{number of total outcomes}}$. Use whenever asked for probability of an event.
- **Expected value** is the sum of possible outcomes weighted by their probabilities. Use when asked for expected value, fair value of the game, fair price of something, or whether you would buy a game for X amount.
- **Total Probability Law** says that if event $E$ can occur in multiple scenarios $S_i$, its probability is $P(E)=\sum_i P(E|S_i)P(S_i)$. Use this along with a probability tree, when the game / experiment has a small number of outcomes that you can draw.
- **Grouping** - most of the time, successful outcome is really a combination / group of a bunch of different outcomes. Trying to identify which ones will demystify a number of problems asking you for esoteric stuff (e.g. expected value of a maximum of two dice rolls).
- **Counting Tricks** - use these when you have too many outcomes to easily draw. The most important tricks are:
- Number of ways to order $n$ elements is $n! = n\cdot (n-1) \cdot (n-2)... 1$.
- Number of ways to pick $r$ elements from a group of $n$, if *order matters* is $\frac{n!}{(n-r)!}$.
- Number of $n$-long sequences where for each element you can chose between $r$ options is $r^n$
- Number of ways to sort $n$ balls into $r$ boxes is $\frac{n!}{n_1!\cdot n_2!...n_r!}$
- Number of ways to sort $n$ balls into $r$ boxes of size $n_1$, $n_2$, ..., $n_r$ is $\frac{n!}{n_1!\cdot n_2!...n_r!}$