Compute probabilities and expectations in random processes

Expect a fast-paced drill on probability and expectation: a run of brief, self-contained puzzles that you work out on a whiteboard. For each one the interviewer wants a tidy formulation, the correct method, and an exact closed-form result — or a precise numeric value when no clean closed form is available — all within a couple of minutes. Every random choice is uniform and independent unless a part says otherwise.

Constraints & Assumptions

• A "fair die" means a six-sided die uniform on $\{1,2,3,4,5,6\}$; a "fair coin" means uniform on $\{H,T\}$.
• A "standard 52-card deck" has 13 ranks with 4 suits apiece; cards are drawn without replacement unless a part explicitly says "with replacement".
• Report exact values (fractions or closed forms) whenever they exist; if they don't, reduce the problem to a finite linear system or DP and give the resulting number.
• No part depends on any other.

Clarifying Questions to Ask

• For "expected sum / product" problems with a stopping rule: do the rolls that trigger the stop count toward the sum or product? (Take it that they do — every roll made is counted.)
• For card draws: does the rank product treat A as 1 and J/Q/K as 11/12/13 rather than 10? (Yes, as each part specifies.)
• For the grid and graph walks: what exactly is the absorbing set, and where does the walk begin? (See the individual parts; on the $10\times10$ grid the "boundary" is the outer ring of cells and the "center" is an interior cell sitting as far from the edge as possible.)
• For "with replacement" sampling: may a single person's draw repeat a value, and does a repeat count as drawn? (Yes.)
• If the closed form is unwieldy, is it acceptable to give a reduced linear-system or DP formulation plus a numeric answer? (Yes — show the setup, then the number.)

Part 1

Distinct digits. Pick an integer uniformly at random from 1 through 10,000 inclusive. What is the probability that every digit in its decimal representation is different (no digit repeats)?

Hint — Count by digit length: Split by how many digits the number has (1, 2, 3, 4 digits, plus the lone value 10,000). Inside each group, count the numbers with distinct digits using the rule that a leading digit cannot be zero — for instance, for 3 digits: $9\cdot 9\cdot 8$.

What This Part Should Cover

• The right case split by digit length, with the no-leading-zero rule applied.
• Not forgetting the endpoint 10,000 and deciding whether it counts.
• Dividing the favorable count by the exact denominator 10,000.

Part 2

Stop when > 4. Keep rolling a fair die until a roll comes up greater than 4 (that is, 5 or 6). What is the expected sum of every roll you made?

Hint — One-step / conditioning: Condition on the opening roll: with probability $1/3$ you halt (the roll is in $\{5,6\}$); with probability $2/3$ you carry on from scratch after having added a value uniform on $\{1,2,3,4\}$. Write $E = \tfrac13\,\mathbb E[\text{roll}\mid\text{stop}] + \tfrac23(\mathbb E[\text{roll}\mid\text{continue}] + E)$.

What This Part Should Cover

• A renewal / first-step split into the "halt" and "carry on" branches.
• The conditional means $\mathbb E[\text{roll}\mid 5,6]$ and $\mathbb E[\text{roll}\mid 1\text{–}4]$ computed correctly.
• Solving the equation that refers to itself for $E$.

Part 3

Three-card rank product. Take 3 cards uniformly without replacement from a standard 52-card deck. Assign ranks $A=1$, the cards $2$–$10$ their own values, $J=11$, $Q=12$, $K=13$. What is the expected value of the product of the three ranks?

Hint — Linearity won't do — use power sums: The product over a without-replacement triple expands through symmetric-function identities. Writing $S_p=\sum_{\text{cards}} r^p$ (each rank value occurs 4 times), the sum of products over ordered distinct triples equals $S_1^3 - 3S_1S_2 + 2S_3$; divide by the ordered count $52\cdot51\cdot50$.

What This Part Should Cover

• Spotting the dependence (no replacement) and reaching for the power sums $S_1,S_2,S_3$.
• The correct Newton-style identity for $\sum_{i\ne j\ne k} r_i r_j r_k$.
• Counting ordered (or unordered) consistently in both numerator and denominator.

Part 4

Cancel H/T pairs. Flip 100 fair coins. Keep removing one Head together with one Tail until no more pairs can be removed; what remains is the count of unmatched flips. What is the expected number of coins left?

Hint — It's an absolute difference: Once pairs are cancelled the leftover is $|H-T|$, where $H\sim\text{Bin}(100,\tfrac12)$. Equivalently it is $|S_{100}|$ for a $\pm1$ simple random walk; apply the standard mean-absolute-displacement identity $\mathbb E|S_{2m}| = 2m\binom{2m}{m}/2^{2m}$.

What This Part Should Cover

• Turning "cancel pairs" into $|H-T|$.
• Knowing or deriving $\mathbb E|S_{2m}|$ for the symmetric walk.
• Arriving at the exact form $100\binom{100}{50}/2^{100}$ together with its numeric value.

Part 5

Stop on two identical in a row (sum). Roll a fair die until two consecutive rolls come up equal for the first time. What is the expected sum of all the rolls?

Hint — Decouple count from per-roll mean: Past the first roll, every later roll repeats its predecessor with probability $1/6$, so the number of rolls is $1+\text{Geom}(1/6)$. Argue that conditioning on the repeat happening does not pull the per-roll mean away from $3.5$ (every face is equally likely to be the one repeated), hence $\mathbb E[\text{sum}]=\mathbb E[\#\text{rolls}]\cdot 3.5$ — or confirm it with a 6-state linear system keyed on the previous face.

What This Part Should Cover

• Deriving $\mathbb E[\#\text{rolls}]$ from the geometric stopping rule.
• Arguing that the stopping rule leaves the per-roll mean at $3.5$ (symmetry over faces).
• Multiplying the two together for the expected sum.

Part 6

Run of 3 in 8 flips. Flip a fair coin 8 times (order counts). What is the probability that the sequence contains at least one run of 3 consecutive identical outcomes (HHH or TTT, anywhere)?

Hint — Count the complement with a DP: Count the sequences with no run of length $\ge 3$ using a small DP over states (current symbol, current run length in $\{1,2\}$); subtract from $2^8=256$.

What This Part Should Cover

• Working with the complement (no run of 3).
• A correct run-length DP or recurrence (Tribonacci-style transitions).
• The final probability as $1-(\text{valid})/256$, reduced.

Part 7

1D walk with die-based steps. Begin at position 0. On each step roll a die: a roll of $1,2,3$ moves you right by that many units; a roll of $4,5,6$ moves you left by $(\text{roll}-3)$ (so $-1,-2,-3$). What is the expected number of steps until $|\text{position}|\ge 10$?

Hint — First-step + symmetry: The step distribution is symmetric ($\pm1,\pm2,\pm3$ each with probability $1/6$, mean 0). Let $E(x)$ be the expected steps to absorption; $E(x)=0$ for $|x|\ge10$, otherwise $E(x)=1+\tfrac16\sum_{s} E(x+s)$. Because $E(x)=E(-x)$ only 10 unknowns remain; solve the linear system. Hint — Wald-style sanity check: $\mathbb E[\Delta^2]=\tfrac{1}{6}(1+4+9+1+4+9)=\tfrac{14}{3}$. Since $X_n^2-\tfrac{14}{3}n$ is a martingale, $\mathbb E[\tau]=\mathbb E[X_\tau^2]/(14/3)$, which gives a range you can use to check the linear-system answer.

What This Part Should Cover

• Writing the absorbing first-step recurrence with overshoot handled (terms where $|\cdot|\ge10$ vanish).
• Using the $x\leftrightarrow -x$ symmetry to shrink the system.
• Optionally the martingale bound as a cross-check.

Part 8

Two 3-digit numbers, two-digit difference. Choose two integers independently and uniformly from 100 to 999. What is the probability that their absolute difference is a two-digit number (from 10 to 99 inclusive)?

Hint — Count pairs by gap size: With $N=900$ values, the number of ordered pairs separated by exactly $d\ge1$ is $2(N-d)$. Sum over $d=10,\dots,99$ and divide by $N^2$.

What This Part Should Cover

• Counting ordered pairs at a fixed absolute gap $d$.
• Summing the arithmetic series over $d\in[10,99]$.
• Reducing over $N^2=810{,}000$.

Part 9

Two particles on an octagon. On a cycle with 8 vertices, put two particles at opposite vertices (4 apart). Every second each particle independently moves one step clockwise or counterclockwise (fair coin). What is the expected number of seconds until they land on the same vertex?

Hint — Track the gap, not both particles: The (signed) gap shifts by the difference of two $\pm1$ steps: $0$ with probability $1/2$, $+2$ with probability $1/4$, $-2$ with probability $1/4$. The parity of the gap never changes, so the even-distance states $\{0,2,4,6\}$ form the chain; meeting means gap $\equiv 0 \pmod 8$. Set $E_0=0$, use $E_2=E_6$ by symmetry, and solve.

What This Part Should Cover

• Collapsing two walkers into a single gap chain on $\{0,2,4,6\}$.
• The correct transition probabilities $\tfrac12/\tfrac14/\tfrac14$ for the gap.
• Using $E_2=E_6$ by symmetry and solving for $E_4$.

Part 10

Per-face running sums to 100. Roll a fair die over and over. For each face $i\in\{1,\dots,6\}$ keep track of $S_i = i\times(\text{count of }i)$. Stop the moment any $S_i\ge 100$. At that stopping time $\tau$, what is the expected number of even rolls (2, 4, 6) that were seen?

Hint — Even-count is half the roll-count: Whether a roll is even (probability $\tfrac12$) is independent of its value, and the stopping rule looks only at values. $M_n=(\#\text{evens in }n)-\tfrac{n}{2}$ is a martingale, so optional stopping gives $\mathbb E[\#\text{evens}]=\tfrac12\mathbb E[\tau]$. The real work is finding $\mathbb E[\tau]$. Hint — Get E[τ] by a tail sum: $\tau$ stops when count $i$ first reaches $m_i=\lceil 100/i\rceil$ (so $m=100,50,34,25,20,17$ for $i=1..6$). Use $\mathbb E[\tau]=\sum_{n\ge0}\mathbb P(\tau>n)$, where $\mathbb P(\tau>n)=\dfrac{n!}{6^n}[x^n]\prod_{i=1}^{6}\Big(\sum_{k=0}^{m_i-1}\tfrac{x^k}{k!}\Big)$ — that is, all six counts stay under their thresholds.

What This Part Should Cover

• The independence/martingale argument tying even-count to $\tfrac12\mathbb E[\tau]$.
• Converting the $S_i\ge100$ rule into count thresholds $m_i=\lceil100/i\rceil$.
• A correct multinomial tail-sum (or absorbing DP) for $\mathbb E[\tau]$ plus a numeric value.

Part 11

Thirteen cards, no aces. Draw 13 cards uniformly without replacement from a standard deck. What is the probability the hand holds no aces?

Hint — Hypergeometric: Take all 13 from the 48 non-aces: $\binom{48}{13}/\binom{52}{13}$.

What This Part Should Cover

• Recognizing the hypergeometric "everything from the safe pile" count.
• The correct ratio of binomials.

Part 12

2D walk to the boundary of a $10\times10$ grid. A particle begins at the center of a $10\times10$ grid (interior cells; the outer ring is an absorbing boundary). Each second, flip two fair coins: HH = North, TT = South, HT = West, TH = East (one step each, all four directions equally likely). What is the expected time to reach the boundary?

Hint — Discrete Poisson / Dirichlet problem: Let $E(x,y)$ be the expected time; $E=0$ on the boundary ring, and for interior cells $E(x,y)=1+\tfrac14\sum_{\text{4 neighbors}}E$. Solve the linear system (the grid's two-axis symmetry cuts down the unknowns), then read off the value at the center.

What This Part Should Cover

• Noticing the four directions are equiprobable ($\tfrac14$ each) and writing the harmonic recurrence with $E=0$ on the boundary.
• Using reflective symmetry to reduce the system.
• A numeric expected hitting time from the center.

Part 13

$\mathbb E[2^{X_1+X_2+X_3}]$. Roll 3 fair dice. Compute $\mathbb E\!\left[2^{X_1+X_2+X_3}\right]$.

Hint — Factor over independence: $2^{X_1+X_2+X_3}=\prod_k 2^{X_k}$, and independence turns this into $\big(\mathbb E[2^{X}]\big)^3$ with $\mathbb E[2^X]=\tfrac16(2+4+8+16+32+64)$.

What This Part Should Cover

• Factoring the MGF-like quantity across independent dice.
• Computing $\mathbb E[2^X]$ and cubing it.

Part 14

Stop on two identical in a row (product). Roll a fair die until two consecutive results come up equal for the first time. What is the expected product of all the rolls?

Hint — Compare growth vs. stopping decay: Write the conditional-expectation system $M_f=\tfrac16 f+\sum_{g\ne f}\tfrac16\,g\,M_g$ (expected product still to come, given the last face was $f$). Check whether it admits a finite nonnegative solution — that is, compare the spectral radius of the multiplicative operator $B_{f,g}=\tfrac{g}{6}\,[g\ne f]$ against 1.

What This Part Should Cover

• Seeing that this is not the "expected sum" case — the product can grow geometrically while the stopping probability only decays geometrically.
• Formalizing it through the linear system / operator spectral radius (which is greater than 1).
• Concluding that the expectation diverges.

Part 15

Bankruptcy in 10 rolls. You begin with $10. Roll a fair die exactly 10 times. An even roll adds its face value to your money; an odd roll subtracts it. What is the probability you are bankrupt (money $\le 0$) at any point during the 10 rolls?

Hint — Absorbing first-passage DP: The increments are $+2,+4,+6,-1,-3,-5$, each with probability $1/6$. Let $p(t,w)$ be the probability of ever reaching $\le0$ within $t$ rolls remaining starting from wealth $w$; then $p(t,w)=1$ for $w\le0$, $p(0,w)=0$ for $w>0$, and $p(t,w)=\tfrac16\sum_\Delta p(t-1,w+\Delta)$. The answer is $p(10,10)$.

What This Part Should Cover

• Listing the six signed increments correctly.
• A first-passage DP over (rolls remaining, wealth) — ruin at any step, not merely at the end.
• The numeric ruin probability $p(10,10)$.

Part 16

No overlap in two length-3 samples from $\{1,\dots,10\}$. You and a friend each independently draw 3 numbers from $\{1,\dots,10\}$ with replacement. What is the probability that none of your numbers shows up among your friend's three draws?

Hint — Condition on how many distinct values you drew: Let $K$ be the number of distinct values among your 3 draws ($K\in\{1,2,3\}$). Compute $\mathbb P(K=k)$, then note the friend dodges all $k$ values with probability $((10-k)/10)^3$; sum over $k$.

What This Part Should Cover

• Obtaining the distribution of the distinct-value count $K$ (surjection / Stirling-style counts).
• The conditional avoidance probability $((10-k)/10)^3$.
• Combining them by total probability.

Part 17

Last roll is 2 when the sum first exceeds 100.