Probability, Combinatorics, And Expected Value

What's being tested

Candidates must demonstrate precise probabilistic reasoning and combinatorial counting under constraints, plus the ability to translate those analyses into numerically robust algorithms. Interviewers probe whether you can model discrete stochastic processes (binomial/random walk), apply counting identities (factorials, Catalan/Ballot), and pick pragmatic computation strategies (exact combinatorics vs. approximations). For a Software Engineer at a trading firm, this shows you can reason about discrete event outcomes, manage numeric limits, and clearly state assumptions under time pressure.

Core knowledge

• Linearity of expectation: $E[\sum_i X_i]=\sum_i E[X_i]$ regardless of independence; use to compute expected gains quickly without full distributional work.

• Variance basics: $\mathrm{Var}(X)=E[X^2]-E[X]^2$ and $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$ only when independent; flag dependence explicitly.

• Binomial distribution: $P(X=k)={n\choose k}p^k(1-p)^{n-k}$; sums of binomial tails give probabilities for counts of up/down steps. Use cumulative sums or log-sum-exp for numerical stability.

• Normal approximation: For large $n$, use $X\approx N(np,np(1-p))$ with continuity correction; quantify error (rule-of-thumb $np(1-p)\gtrsim 10$).

• Random-walk framing: Model price after $n$ steps as $S_n = S_0 + \sum_{i=1}^n X_i$ with $X_i\in\{\pm1\}$ or general increments; map event constraints to binomial inequalities.

• Permutations with repeats: Number of distinct orderings of multiset with counts $n_1,\dots,n_k$ is $\frac{N!}{\prod_i n_i!}$; compute with logs or big-integer factorial to avoid overflow.

• Nonnegative-paths / Catalan: Sequences that never drop below zero when steps are $\pm1$ map to Dyck paths; for equal up/down count $n$, count is $C_n=\frac{1}{n+1}{2n\choose n}$.

• Ballot theorem / reflection principle: For unequal counts, the count/probability that one side always leads can be computed via $\frac{a-b}{a+b}{a+b\choose a}$ or reflection arguments; useful for “never negative” constraints.

• Computation scale & precision: Factorials blow up; 64-bit safe roughly to $20!$; use BigInteger, prime-mod arithmetic, or log-gamma (lgamma) for larger $n$, and prefer exact combinatorics for $n\le 1000$ only with big-int or modular arithmetic.

• Dynamic programming: For constrained counts (e.g., prefix nonnegativity), use DP over steps and state (current height) in $O(n\cdot H)$ time and $O(H)$ space, where $H$ is max height (bounded by $n$).

• Conditional probability / Bayes: Use $P(A|B)=P(A\cap B)/P(B)$ when conditioning on path events; ensure denominators nonzero and state what information is observed.

• Numerical tactics: Use log-space for products of combinations, iterative multiplicative binomial coefficients to avoid computing full factorials, and precompute Pascal rows for repeated queries.

Worked example — Compute negative-price probability after n steps

First 30 seconds: ask whether steps are symmetric (±1) and independent, initial price $S_0$, and whether "negative" means strictly below zero at time $n$ or hitting negative at any time before $n$. Skeleton answer: (1) model $S_n=S_0+\sum X_i$ with $X_i\in\{\pm1\}$ and reduce to counting number of down steps, (2) express probability as binomial tail $\sum_{k: S_0+(n-2k)<0}{n\choose k}p^k(1-p)^{n-k}$, (3) choose computation: exact binomial sum for small $n$, or normal approximation with continuity correction for large $n$, (4) discuss edge cases like $p\neq 0.5$, non-integer thresholds, or absorbing boundaries. A tradeoff to call out: exact combinatorial sum is simple and correct but numerically unstable for large $n$ — prefer log-domain or use normal approx when $np(1-p)\gtrsim 10$. Close by saying: if I had more time I'd compute the hitting-time probability (ever negative before $n$) via the reflection principle or run Monte Carlo to validate approximation errors.

A second angle — Count nonnegative buy/sell sequences

Reframe: buys=+1, sells=−1; constraint that cumulative sum never negative maps to Dyck/ballot constraints. If buys and sells are equal, use Catalan numbers for exact count. If counts differ, apply the Ballot theorem to get the number or probability that buys always lead. Algorithmically, a strong answer presents a closed-form combinatorial identity, then a DP implementation for arbitrary counts or when you must return sequences themselves. Practical tradeoffs: closed-form is $O(1)$ arithmetic with big-int; DP is $O(n\cdot H)$ and easier to extend to extra constraints (e.g., limited capacity). Explain how to handle large outputs (return counts modulo a prime, or stream-generation of sequences).

Common pitfalls

Pitfall: Treating independence as given. Many candidates sum variances without asking whether increments are independent; explicitly state or test independence before using additivity.

Pitfall: Not stating model assumptions. Failing to ask whether steps are ±1, biased ($p\neq0.5$), or whether "negative" is transient vs. terminal will lead to wrong formulas; say your assumptions up front.

Pitfall: Overusing approximations without error checks. Quoting a normal approximation without continuity correction or bounds on approximation error is tempting but will anger an interviewer; quantify when approximation is acceptable or fallback to exact/log-space sums.

Connections

Interviewers may pivot to Markov chains and hitting-time distributions, generating functions for counting constrained sequences, or numeric topics like stable computation of large combinatorials using lgamma/Stirling approximations. These are natural next steps to extend a correct discrete analysis.

Further reading

• [Feller — An Introduction to Probability Theory and Its Applications (Vol. 1)](William Feller citation) — classic reference for random walks, reflection principle, and ballot results.

• [Graham, Knuth, Patashnik — Concrete Mathematics](book citation) — practical combinatorial identities and counting techniques useful for constrained sequence problems.