A list of common problem-solving patterns for quant problems.
The optimal bet size (given as a proportion of your bankroll) for a series of bets is given by
\[f = \frac{p}{a} - \frac{q}{b}\]where
Proof: The proof is based on maximizing the geometric growth rate of wealth, given by
\[r = (1 + fb)^p(1 - fa)^q\]Taking the log-derivative with respect to $f$ yields
\[\frac{dr}{df} = \frac{pb}{1 + fb} - \frac{aq}{1 - fa}\]and setting to $0$ and solving for $f$ gives the desired result.
The probability of needing $k$ trials before viewing the first success, with probability $p$, is modelled by the geometric distribution
\[\operatorname{Geom}(k; p) = (1 - p)^{k - 1} p\]which has expectation $\mathbb E[k] = \frac{1}{p}$.
When solving problems that require counting the expected number of independent events that occur, it can be useful to define indicator variables for each of the independent events, and using the linearity of expectation to count the total.
Example: Let $S$ be a uniformly distributed randomly-generated 5-digit string. What is the expected number of unique digits in $S$?
Solution: Define indicator variables $I_k$ where $I_k = 1$ if $k$ is present in $S$ and $0$ otherwise. Then the expected number of unique digits $X$ in $S$ is
\[\mathbb E[X] = \mathbb E\left[\sum_{k = 0}^9 I_k\right] = \sum_{k = 0}^9 \mathbb E[I_k] = 10\mathbb E[I_0]\]by linearity of expectation and symmetry of $I_0, \dots, I_9$. It remains to find $I_0$. The probability of not observing $0$ in $S$ is $(9/10)^{5}$ (each digit is one of the 10 digits other than 0). So the probability of observing at least one 0 in $S$ is $1 - (9/10)^{5}$. Thus
\[\mathbb E[X] = 10\mathbb E[I_0] = 10 \cdot \left(1 - \left(\frac{9}{10}\right)^{5}\right) = \frac{40951}{10000}\]Definition: A Markov chain
Definition: A martingale is a stochastic process (a sequence of random variables) $(X_n)$ with finite mean such that
\[\mathbb E[X_n \mid X_1 = x_1, \dots, X_{n - 1} = x_{n - 1}] = x_{n - 1}\]That is, the expectation of any $X_n$ conditioned on all previous RVs is the value of the previous RV.
Intuitively, a martingale is a process whose “change” is expected to be 0 given the information of all the trials that happened before it. As a corollary, the expectation (not conditional) of the martingale is constant.
Proposition: If $(X_n)$ is a martingale, then
\[\mathbb E[X_0] = \mathbb E[X_t]\]for all $t \geq 0$.
Proof: By the Law of Total Probability,
\[\mathbb E[X_{t + 1}] = \mathbb E[\mathbb E[X_{t + 1} \mid \mathcal F_t]] = \mathbb E[X_t]\]where $\mathcal F_t = \sigma(X_0, X_1, \dots, X_t)$ is the $\sigma$-algebra generated by $X_0, \dots, X_t$. The proposition then follows from induction $\blacksquare$
Example: Let $S_n$ be a random integer variable denoting the number of forward steps taken after $n$ steps, where each step has equal probability of being a forward step or a backward step. Then $(S_n)$ is a martingale since
\[\begin{align*} \mathbb E[S_n \mid S_1 = s_1, \dots, S_{n - 1} = s_{n - 1}] &= S_{n - 1} + \frac{1}{2}(1) + \frac{1}{2}(-1) = S_{n - 1} \end{align*}\]Definition: Let $(X_n)$ be an IID stochastic process. A stopping rule for $(X_n)$ is a positive integer-valued random variable $N$ such that $P(N \leq n)$ is independent of $X_{n + 1}, X_{n + 2}, \dots$.
Example: Let $(X_n)$ be a stochastic process where $X_n = 1$ with probability $1/2$ and $0$ otherwise. The RV $N$ with distribution
\[P(N = n) := P\left(\sum_{k = 0}^N X_k = 3\right)\](i.e. the probability of $3$ heads in $n$ coin-flips) is a stopping rule since $P(N \leq n)$ depends only on $X_1, \dots, X_N$.
Theorem (Wald’s Equality): Let $N$ be a stopping rule for IID random variables $X_1, \dots, X_n$ and let $S_N = \sum_{k = 0}^N X_k$. Then
\[\mathbb E[S_n] = \mathbb E[X]\mathbb E[N]\]Example: Suppose a game where you roll a dice until a $6$ appears. You are paid the face value for each roll. We find the expected value of the game, $\mathbb E[S_n]$ where $S_n = \sum_{k = 0}^n X_k$.
The game stops when a 6 is rolled. Our stopping rule $N$ is then defined by
\[P(N = n) = \left(\frac{5}{6}\right)^{n - 1}\left(\frac{1}{6}\right) = \operatorname{Geom}\left(\frac{1}{6}\right)\]The expected value of each roll is $\mathbb E[X] = 3.5$. So by Wald’s Equality,
\[\mathbb E[S_n] = \mathbb E[X]\mathbb E[N] = (3.5)(6) = 21\]Theorem: Let $X \sim \operatorname{Bernoulli}(p)$. The expected number of trials $\mathbb E[T]$ to view a specific sequence of failiures and successes is given by
\[\mathbb E[T] = \sum_{k \in S} \left(\frac{1}{p}\right)^k\]where $S = \lbrace i : X_i \text{ in the sequence is a success} \rbrace$.
Proof:
Proof: To choose $n$ people from a group of $2n$, first split the $2n$ people into 2 groups of size $n$. Then, consider all the ways to choose $k$ people from 1 group and $n - k$ group from the other group, for $k$ from $0$ to $n$. $\blacksquare$
For a general matrix $A$,
\[\det (A - I\lambda) = 0\]and for a $2 \times 2$ matrix $A$,
\[p(\lambda) = \lambda^2 - \operatorname{tr}(A) + \det A\]Proof: From the definition of the eigenvalues/eigenvectors,
\[Ax = \lambda x \implies (A - I\lambda)x = 0 \implies \det (A - I \lambda) = 0\]$\blacksquare$
This is useful since the volume of an $n$-simplex in a cube of side-length $x$ represents the probability of the sum of $n$ independent uniformly randomly distributed variables being less than or equal to $x$.
\[\frac{x^n}{n!}\]where $x$ is the length of the cube.
Proof: Consider the simplex formed by $0 \leq x_1 \leq \dots \leq x_n \leq 1$. Now, consider $X_1, \dots, X_n \sim \operatorname{Uniform}(0, 1)$. The probability of any of the $n!$ orderings of $X_1 = x_1, \dots, X_n = x_n$ is equal, so each ordering must have probability $\frac{1}{n!}$. A linear transformation can transform this simplex to one whose sides are the basis vectors in $\mathbb R^n$. Scaling the unit cube by $x$ scales its volume by $x^n$, giving $\frac{x^n}{n!}$. $\blacksquare$
Example: Consider all decreasing sequences of length $n \geq 1$ of standard uniform random variables $x_1 \geq x_2 \geq \dots \geq x_n$. What is $\mathbb E[x_n]$?
Solution: We consider $\mathbb E[x_n]$ for fixed $n$, after which we will sum across all sequences of length $n$. To have $x_n = x$, we must have selected $n - 1$ standard uniform variables with $x_1, \dots, x_{n - 1} \leq x^{n - 1}$, which occurs with probability $x^n$. The probability of the specific ordering $x_1 \geq x_2 \geq x_3 \geq \dots$ is $\frac{1}{(n - 1)!}$. Thus, $p(x) = \sum_{n = 0}^\infty \frac{x^{n - 1}}{(n - 1)!} = e^x$. So $\mathbb E[x_n] = \int_0^1 xe^x dx =$