D. E. Shaw interview questions

Coupon Collector's Problem

High-level idea. Decompose the total waiting time into independent geometric stages, then apply linearity of expectation.

Stage decomposition

Let $T$ be the total number of rolls of a fair $N$-sided die needed to observe every face at least once. Define stage $k$ ($k = 1, \ldots, N$) as the period that begins the moment the $(k{-}1)$-th distinct face was first seen and ends when the $k$-th distinct face is first seen. Writing $T_k$ for the number of rolls in stage $k$,

$$T = T_1 + T_2 + \cdots + T_N.$$

Distribution of each stage

At the start of stage $k$, exactly $k-1$ faces have been observed. Each roll independently reveals a previously unseen face with probability

$$p_k = \frac{N-(k-1)}{N} = \frac{N-k+1}{N}.$$

Hence $T_k \sim \operatorname{Geometric}(p_k)$ (number of trials until first success), so

$$E[T_k] = \frac{1}{p_k} = \frac{N}{N-k+1}.$$

Closed-form expected value

By linearity of expectation,

$$E[T] = \sum_{k=1}^{N} \frac{N}{N-k+1}.$$

Reindexing with $j = N-k+1$ (as $k$ runs $1 \to N$, $j$ runs $N \to 1$):

$$E[T] = N \sum_{j=1}^{N} \frac{1}{j} = N \cdot H_N,$$

where $H_N = \displaystyle\sum_{j=1}^{N} \frac{1}{j}$ is the $N$-th harmonic number.

Numerical evaluation for $N = 100$

Using the Euler–Maclaurin asymptotic expansion

$$H_N = \ln N + \gamma + \frac{1}{2N} - \frac{1}{12N^2} + \frac{1}{120N^4} - \cdots,$$

with $\gamma = 0.57721566490153\ldots$ (Euler–Mascheroni constant):

$$\begin{aligned} H_{100} &\approx \underbrace{4.60517018598809}_{\ln 100} + \underbrace{0.57721566490153}_{\gamma} + \underbrace{0.00500000000000}_{1/200} - \underbrace{0.00000833333}_{1/120000} \\ &\approx 5.18737752. \end{aligned}$$

Therefore,

$$E[T]\big|_{N=100} = 100 \times H_{100} \approx 518.74.$$

Rounded to the nearest integer:

$$\boxed{519}.$$

Let $N$ be the number of coin flips until the first heads appears. Since the coin is fair, $N$ follows a geometric distribution with success probability $1/2$: $P(N = n) = (1/2)^n$ for $n = 1, 2, 3, \dots$ (the first $n-1$ flips are tails and the $n$th flip is heads). The payout when $N = n$ is $2^n$ dollars. The expected value of the payout is

$$E[\text{payout}] = \sum_{n=1}^{\infty} 2^n \cdot P(N = n) = \sum_{n=1}^{\infty} 2^n \cdot \left(\frac{1}{2}\right)^n = \sum_{n=1}^{\infty} 1 = \infty.$$

Since the expected value is infinite, the game does not have a finite fair value. Per the problem instructions, output $-1$.

High-level idea

Model the process as a Markov chain with two transient states tracking the current "run" of consecutive 1s. Set up first-step equations and solve the $2\times 2$ linear system.

States and equations

Let $p = \tfrac{1}{6}$ be the probability of rolling a 1. Define:

• $S_0$: start, or the last roll was not a 1.
• $S_1$: the last roll was a 1 (one consecutive 1 in progress).

Let $\mu_0,\mu_1$ be the expected number of additional rolls needed to reach absorption (two consecutive 1s) from each state.

From $S_0$ — one roll is used; with probability $\tfrac{1}{6}$ we move to $S_1$, with probability $\tfrac{5}{6}$ we remain in $S_0$:

$$\mu_0 = 1 + \frac{1}{6}\mu_1 + \frac{5}{6}\mu_0.$$

From $S_1$ — one roll is used; with probability $\tfrac{1}{6}$ we finish (0 more rolls), with probability $\tfrac{5}{6}$ we return to $S_0$:

$$\mu_1 = 1 + \frac{5}{6}\mu_0.$$

Solving the system

Rearranging the first equation:

$$\mu_0 - \frac{5}{6}\mu_0 = 1 + \frac{1}{6}\mu_1 \implies \mu_0 = 6 + \mu_1.$$

Substituting $\mu_1 = 1 + \tfrac{5}{6}\mu_0$:

$$\mu_0 = 7 + \frac{5}{6}\mu_0 \implies \frac{1}{6}\mu_0 = 7 \implies \mu_0 = 42.$$

Check: $\mu_1 = 1 + \tfrac{5}{6}(42) = 36$, and $6 + 36 = 42$. ✓

Final answer

The expected number of rolls is $\boxed{42}$.

Idea

Work with the complement: a triple fails the triangle inequality if and only if one side is at least as large as the sum of the other two. The three failure events turn out to be mutually exclusive, so the failure probability is simply $3P(A)$ for any one of them.

Setup

Let $X, Y, Z \overset{\text{iid}}{\sim} \text{Uniform}[0,1]$. Define the failure events

$$A = \{X+Y \le Z\}, \quad B = \{X+Z \le Y\}, \quad C = \{Y+Z \le X\}.$$

Mutual Exclusivity of $A$, $B$, $C$

Suppose $A \cap B$ occurs: $X+Y \le Z$ and $X+Z \le Y$. Adding these inequalities gives $2X + Y + Z \le Y + Z$, hence $X \le 0$. Since $X \ge 0$ a.s., this forces $X = 0$, an event of probability zero. By symmetry, every pairwise intersection has measure zero, so $A$, $B$, $C$ are mutually exclusive a.s. Combined with symmetry of the joint distribution,

$$P(A \cup B \cup C) = P(A) + P(B) + P(C) = 3\,P(A).$$

Computing $P(A)$

Condition on $Z = z$. The event $\{X + Y \le z\}$ within $[0,1]^2$ traces the right triangle $\{x \ge 0,\, y \ge 0,\, x+y \le z\}$, which has area $z^2/2$. Therefore

$$P(A) = \int_0^1 \frac{z^2}{2}\,dz = \frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}.$$

Final Answer

$$P(\text{valid triangle}) = 1 - 3 \cdot \frac{1}{6} = 1 - \frac{1}{2} = \boxed{\dfrac{1}{2}}.$$

We have 8 points on a circle, so there are $\binom{8}{2}=28$ chords in total. Choosing 4 chords uniformly at random gives $\binom{28}{4}$ equally likely outcomes.

For the 4 chords to form a convex quadrilateral, their union must be exactly the boundary of that quadrilateral. Because the points lie on a circle, any 4 distinct points determine a convex quadrilateral whose sides are the chords connecting consecutive points in cyclic order. Thus a favorable set of 4 chords corresponds precisely to choosing 4 of the 8 points and taking the four boundary chords of that set. There are $\binom{8}{4}=70$ ways to choose the points, and each yields exactly one favorable 4‑chord set. No other set of 4 chords can form a convex quadrilateral, since any quadrilateral must have four distinct vertices, and on a circle the only non‑self‑intersecting 4‑cycle on four points is the boundary cycle.

Hence the probability is

$$P = \frac{\binom{8}{4}}{\binom{28}{4}} = \frac{70}{20475} = \frac{14}{4095} = \frac{2}{585}.$$

We have 15 boys and 10 girls, totaling 25 students. The students line up uniformly at random. We want the expected number of adjacent positions where one is a boy and the other is a girl (order BG or GB).

Let $X$ be the number of adjacent boy-girl pairs. For each adjacent pair of positions $(i, i+1)$ with $i = 1,\dots,24$, define an indicator $I_i$ that the two students at those positions are of opposite sexes. Then $X = \sum_{i=1}^{24} I_i$, and by linearity of expectation,

$$\mathbb{E}[X] = \sum_{i=1}^{24} \mathbb{E}[I_i] = \sum_{i=1}^{24} \Pr(\text{positions } i \text{ and } i+1 \text{ are opposite sexes}).$$

By symmetry, the probability is the same for every adjacent pair; denote it by $p$. Hence $\mathbb{E}[X] = 24 \cdot p$.

Now compute $p$. There are $25 \times 24$ equally likely ordered assignments of two distinct students to the two positions. Favorable cases are (boy, girl) and (girl, boy). There are $15 \times 10 = 150$ ways to choose a boy then a girl, and $10 \times 15 = 150$ ways to choose a girl then a boy, for a total of $300$ favorable ordered pairs. Thus

$$p = \frac{300}{25 \times 24} = \frac{300}{600} = \frac{1}{2}.$$

Alternatively, $\Pr(\text{boy then girl}) = \frac{15}{25} \cdot \frac{10}{24} = \frac{1}{4}$, and $\Pr(\text{girl then boy}) = \frac{10}{25} \cdot \frac{15}{24} = \frac{1}{4}$, so $p = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$.

Therefore,

$$\mathbb{E}[X] = 24 \cdot \frac{1}{2} = 12.$$

The key insight is that when two ants meet and reverse direction, the system is equivalent to the ants passing through each other without interaction, because the ants are indistinguishable. Under this "pass-through" model, each ant simply continues in its original direction forever. Therefore, the number of ants that reach Priya's end equals the number of ants that were initially moving leftward (toward Priya), and the number that reach Theo's end equals the number initially moving rightward (toward Theo).

Initially, all 40 ants at Priya's end move rightward (toward Theo), and all 80 ants at Theo's end move leftward (toward Priya). Under the pass-through equivalence, the ants that reach Priya are those that started at Theo's end and moved leftward: 80 ants. The ants that reach Theo are those that started at Priya's end and moved rightward: 40 ants. Thus $x = 80$, $y = 40$, and

$$x - y = 80 - 40 = 40.$$

More formally, let $x$ be the number reaching Priya and $y$ the number reaching Theo. Under the pass-through model, each ant's trajectory is a straight line from its start to the opposite end. Since all ants move at the same speed, the number reaching each end is exactly the number that started at the opposite end. Hence $x = 80$, $y = 40$, and the difference is $40$.

Let the statements be numbered $1,2,\dots,100$. Statement $k$ says: "at most $k-1$ of these $100$ statements are true."

Let $T$ be the total number of true statements. For statement $k$ to be true, we must have $T \le k-1$; for it to be false, $T > k-1$. Hence statement $k$ is true exactly when $k \ge T+1$.

Thus the true statements are those with indices $T+1, T+2, \dots, 100$. The number of such statements is $100 - T$. But this number must equal $T$ itself, because $T$ is the total number of true statements. Therefore:

$$T = 100 - T \quad\Longrightarrow\quad 2T = 100 \quad\Longrightarrow\quad T = 50.$$

Check: If $T=50$, then statements $51$ through $100$ are true (50 statements). Statement $51$ says "at most $50$ are true" — true because exactly $50$ are true. Statement $50$ says "at most $49$ are true" — false because $50 > 49$. All statements $1$ through $49$ are false because each claims "at most $k-1$ are true" with $k-1 \le 48$, but $50 > k-1$. All statements $52$ through $100$ are true because each claims "at most $k-1$ are true" with $k-1 \ge 51$, and $50 \le k-1$. Hence exactly $50$ statements are true, consistent with $T=50$.

Thus the answer is $50$.

Let $q_k$ be the probability that the drunkard eventually steps onto the precipice (ruin) when he is currently $k$ paces from the edge ($k\ge 0$). The precipice is at $k=0$, so $q_0=1$. We want the survival probability $1-q_1$.

For $k\ge 1$, condition on the first step:

$$q_k = \frac13 q_{k-1} + \frac23 q_{k+1}.$$

Multiply by $3$ and rearrange to obtain the homogeneous linear recurrence

$$2q_{k+1} - 3q_k + q_{k-1} = 0.$$

The characteristic equation is $2r^2-3r+1=0$, which factors as $(2r-1)(r-1)=0$, giving roots $r=1$ and $r=\frac12$. Hence

$$q_k = A + B\Big(\frac12\Big)^k.$$

Boundary conditions.

• At $k=0$: $q_0 = 1 \implies A + B = 1$.
• As $k\to\infty$, the walk has a positive drift away from the edge (each step has expected change $+\frac13$). Therefore the probability of ever hitting $0$ from far away tends to $0$, i.e. $\lim_{k\to\infty}q_k = 0$. This forces $A=0$, and consequently $B=1$.

Thus $q_k = \big(\frac12\big)^k$. In particular, the ruin probability starting one pace away is $q_1 = \frac12$. The probability that he never goes over the edge is

$$1 - q_1 = \frac12.$$

We determine the outcome by backward induction on the number of tigers, $n$. The key observation is that a tiger will eat the sheep only if doing so guarantees its own survival after it turns into a sheep.

• $n=1$: The lone tiger eats the sheep, becomes a sheep, and faces no remaining tigers. It survives, so the sheep is eaten.
• $n=2$: If a tiger eats the sheep, it becomes a sheep, leaving one tiger and one sheep. By the $n=1$ case, that remaining tiger will eat the new sheep, so the first tiger would die. Since tigers value survival, neither will eat. The sheep survives.
• $n=3$: If a tiger eats, it becomes a sheep, leaving two tigers and one sheep. From $n=2$, the two tigers will not eat the sheep (they would die), so the eating tiger survives. Hence some tiger will eat, and the sheep is eaten.
• $n=4$: Eating leads to the $n=3$ case, where the sheep is eaten, so the eating tiger would die. No tiger eats; the sheep survives.

Continuing this logic, the sheep is eaten if and only if $n$ is odd. For $n=100$ (even), no tiger will eat the sheep.

A correlation matrix must be positive semidefinite (PSD). For three assets with pairwise correlations $\rho_{AB}=0.9$, $\rho_{BC}=0.8$, and a candidate $\rho_{AC}=0.1$, we check whether the $3\times3$ correlation matrix

$$R = \begin{pmatrix} 1 & 0.9 & 0.1 \\ 0.9 & 1 & 0.8 \\ 0.1 & 0.8 & 1 \end{pmatrix}$$

is PSD. A necessary and sufficient condition for a $3\times3$ symmetric matrix with unit diagonal is that all principal minors are nonnegative. The $1\times1$ and $2\times2$ minors are clearly nonnegative, so the key condition is $\det(R) \ge 0$.

The determinant of a $3\times3$ correlation matrix is

$$\det(R) = 1 + 2\rho_{AB}\rho_{BC}\rho_{AC} - \rho_{AB}^2 - \rho_{BC}^2 - \rho_{AC}^2.$$

Substituting the given values:

$$\begin{aligned} \det(R) &= 1 + 2(0.9)(0.8)(0.1) - 0.9^2 - 0.8^2 - 0.1^2 \\ &= 1 + 0.144 - 0.81 - 0.64 - 0.01 \\ &= 1.144 - 1.46 = -0.316 < 0. \end{aligned}$$

Since the determinant is negative, $R$ is not positive semidefinite. Therefore $\rho_{AC}=0.1$ is not possible.

Let $M$, $T$, $W$ be the events that Monday, Tuesday, Wednesday produce a matching pair, respectively. We want

$$P(M^c \cap T^c \cap W) = P(M^c)\,P(T^c \mid M^c)\,P(W \mid M^c \cap T^c).$$

1. $P(M^c)$. Total ways to choose $2$ socks from $10$: $\binom{10}{2}=45$. Matching pairs: $5$ (one per color). So $P(M)=5/45=1/9$, hence

$$P(M^c)=1-\frac19=\frac89.$$

2. $P(T^c \mid M^c)$. After a non‑matching Monday, two socks of different colors are removed. The remaining $8$ socks consist of $3$ colors with $2$ socks each and $2$ colors with $1$ sock each. Total pairs from $8$: $\binom{8}{2}=28$. Only the three colors with $2$ socks can produce a matching pair, so $3$ matching pairs. Thus $P(T\mid M^c)=3/28$ and

$$P(T^c \mid M^c)=1-\frac{3}{28}=\frac{25}{28}.$$

3. $P(W \mid M^c \cap T^c)$. After Monday and Tuesday are both non‑matching, the composition of the remaining $6$ socks depends on how Tuesday's non‑matching pair was formed. Starting from the Monday state ($3$ colors with $2$ socks, $2$ colors with $1$ sock), Tuesday's non‑matching pair can be of three types:

• Case A: Both socks from the $2$-sock colors. Number of ways: $\binom{3}{2}\cdot2\cdot2 = 12$. Resulting state: $1$ color with $2$ socks, $4$ colors with $1$ sock. Probability of a match on Wednesday: $\frac{1}{\binom{6}{2}} = \frac{1}{15}$.
• Case B: One sock from a $2$-sock color and one from a $1$-sock color. Number of ways: $3\cdot2\cdot2\cdot1 = 12$. Resulting state: $2$ colors with $2$ socks, $2$ colors with $1$ sock, $1$ color with $0$ socks. Probability of a match on Wednesday: $\frac{2}{15}$.
• Case C: Both socks from the two $1$-sock colors. Number of ways: $1$. Resulting state: $3$ colors with $2$ socks, $2$ colors with $0$ socks. Probability of a match on Wednesday: $\frac{3}{15} = \frac15$.

Total non‑matching pairs on Tuesday: $12+12+1 = 25$, so the conditional probabilities of the cases given $T^c$ are $\frac{12}{25},\frac{12}{25},\frac{1}{25}$. Hence

$$P(W \mid M^c \cap T^c) = \frac{12}{25}\cdot\frac{1}{15} + \frac{12}{25}\cdot\frac{2}{15} + \frac{1}{25}\cdot\frac{3}{15} = \frac{12+24+3}{375} = \frac{39}{375} = \frac{13}{125}.$$

4. Multiply.

$$P(M^c \cap T^c \cap W) = \frac{8}{9} \cdot \frac{25}{28} \cdot \frac{13}{125} = \frac{8\cdot25\cdot13}{9\cdot28\cdot125} = \frac{2600}{31500} = \frac{26}{315}.$$

Thus the desired probability is $\boxed{\frac{26}{315}}$.

(One can verify by counting all sequences: total sequences $\binom{10}{2}\binom{8}{2}\binom{6}{2}=18900$, favorable sequences $5\cdot24\cdot13=1560$, giving the same fraction.)

High-level idea

In the Black–Scholes model, the price of a European call depends only on the risk‑free rate and volatility, not on the real‑world drift. Hence two assets with the same current price, volatility, strike, maturity, and risk‑free rate have identical European call prices, regardless of their real‑world drifts.

When one asset is also subject to random downward jumps, the comparison changes — but not in the direction naive intuition suggests. Under the risk‑neutral measure the jumps must be compensated by extra drift between jumps so that the forward price is unchanged. The compensated jumps therefore act as a mean‑preserving spread of the terminal price, and the call payoff is convex, so by Jensen's inequality the call on the jump‑exposed asset is more expensive than the call on the pure‑diffusion asset.

---

Derivation

1. Pure diffusion (no jumps)

Under the risk‑neutral measure $\mathbb{Q}$ the asset follows

$$\frac{dS_t}{S_t} = r\,dt + \sigma\,dW_t^{\mathbb{Q}},$$

so that

$$S_T = S_0 \exp\!\Bigl(\bigl(r - \tfrac{\sigma^{2}}{2}\bigr)T + \sigma\sqrt{T}\,Z\Bigr), \qquad Z \sim \mathcal{N}(0,1).$$

The European call price is

$$C = e^{-rT}\,\mathbb{E}^{\mathbb{Q}}\bigl[(S_T - K)^{+}\bigr] = S_0 N(d_1) - K e^{-rT} N(d_2),$$

with

$$d_{1,2} = \frac{\ln(S_0/K) + (r \pm \tfrac{\sigma^2}{2})T}{\sigma\sqrt{T}}.$$

The formula contains $r$ and $\sigma$ but no real‑world drift $\mu$. Therefore, if two assets share the same $S_0$, $\sigma$, $K$, $T$, and $r$, their European call prices are identical — distinct real‑world drifts are irrelevant.

2. Adding random downward jumps to one asset

Now let one asset follow a jump‑diffusion (Merton 1976). Under a suitable risk‑neutral measure its dynamics are

$$\frac{dS_t}{S_{t-}} = (r - \lambda\kappa)\,dt + \sigma\,dW_t^{\mathbb{Q}} + (Y_t - 1)\,dN_t,$$

where $N_t$ is a Poisson process with intensity $\lambda$, $Y_t < 1$ is the downward jump multiplier, and $\kappa = \mathbb{E}^{\mathbb{Q}}[Y_t - 1]$ is the compensator that keeps the expected instantaneous return equal to $r$. For downward jumps $\kappa < 0$, so the drift between jumps is raised above $r$: the compensation exactly offsets the jumps and preserves the forward, $\mathbb{E}^{\mathbb{Q}}[S_T] = S_0 e^{rT}$ for both assets.

Solving the SDE, the terminal price factorizes as

$$S_T^{\text{jump}} = S_T^{\text{diff}} \cdot J, \qquad J = e^{-\lambda\kappa T}\prod_{i=1}^{N_T} Y_i,$$

where $S_T^{\text{diff}}$ is the pure‑diffusion terminal price and $J$ is an independent jump factor with $\mathbb{E}^{\mathbb{Q}}[J] = 1$. Conditioning on $S_T^{\text{diff}}$ and applying Jensen's inequality to the convex payoff $x \mapsto (x - K)^{+}$,

$$\mathbb{E}^{\mathbb{Q}}\bigl[(S_T^{\text{diff}}\,J - K)^{+} \,\big|\, S_T^{\text{diff}}\bigr] \;\ge\; \bigl(S_T^{\text{diff}}\,\mathbb{E}^{\mathbb{Q}}[J] - K\bigr)^{+} = \bigl(S_T^{\text{diff}} - K\bigr)^{+}.$$

Taking expectations and discounting shows the jump‑exposed call is worth at least as much for every strike — and strictly more whenever the jumps are genuinely random. Equivalently: at the same forward, the jumps add total risk‑neutral variance, and extra dispersion always benefits a convex payoff (a mean‑preserving spread raises the value of a convex function's expectation).

The tempting argument that "downward jumps create negative skew and therefore depress the call" is wrong because it ignores the compensator: between jumps the asset drifts upward faster than $r$, and through the convexity of the payoff this more than makes up for the heavier left tail.

As a numerical check, with $S_0 = K = 100$, $r = 0.02$, $\sigma = 0.2$, $T = 1$, $\lambda = 1$, and jump multiplier $Y = 0.8$, Monte Carlo gives a jump‑diffusion call price of about $12.45$ versus a Black–Scholes price of about $8.92$.

Consequently, the call on the asset with random downward jumps is more expensive than the call on the pure‑diffusion asset.

---

Final answer

Without jumps the two European calls have the same price. When one asset is also subject to random downward jumps (compensated under the risk‑neutral measure so the forward is unchanged), its call becomes more expensive than the call on the pure‑diffusion asset: the jumps act as a mean‑preserving spread of the terminal price, and the call payoff is convex.

We start from the Ornstein–Uhlenbeck SDE

$$dX_t = \theta(\mu - X_t)\, dt + \sigma\, dW_t, \qquad X_0 = x_0.$$

Step 1. Solve the SDE exactly. Define $Y_t = e^{\theta t} X_t$. By Itô’s lemma,

$$dY_t = e^{\theta t}\, dX_t + \theta e^{\theta t} X_t\, dt.$$

Substituting $dX_t$,

$$\begin{aligned} dY_t &= e^{\theta t}\bigl[\theta(\mu - X_t)\, dt + \sigma\, dW_t\bigr] + \theta e^{\theta t} X_t\, dt \\ &= \theta\mu e^{\theta t}\, dt + \sigma e^{\theta t}\, dW_t. \end{aligned}$$

The terms containing $X_t$ cancel. Integrate from $0$ to $t$,

$$Y_t - Y_0 = \theta\mu\int_0^t e^{\theta s}\, ds + \sigma\int_0^t e^{\theta s}\, dW_s,$$

with $Y_0 = X_0$. Since $\int_0^t \theta e^{\theta s}\, ds = e^{\theta t} - 1$, we obtain

$$X_t = e^{-\theta t} Y_t = X_0 e^{-\theta t} + \mu\bigl(1 - e^{-\theta t}\bigr) + \sigma\int_0^t e^{-\theta(t-s)}\, dW_s. \tag{1}$$

Step 2. Expected value. The Itô integral in (1) is a martingale starting at zero; its expectation is zero. Hence

$$\mathbb{E}[X_t] = X_0 e^{-\theta t} + \mu\bigl(1 - e^{-\theta t}\bigr). \tag{2}$$

Step 3. Variance. Only the stochastic term in (1) contributes to the variance. Using Itô isometry,

$$\begin{aligned} \operatorname{Var}(X_t) &= \mathbb{E}\!\left[\left(\sigma\int_0^t e^{-\theta(t-s)}\, dW_s\right)^{\!2}\right] = \sigma^2 \int_0^t e^{-2\theta(t-s)}\, ds \\ &= \sigma^2 \int_0^t e^{-2\theta u}\, du = \sigma^2\,\frac{1 - e^{-2\theta t}}{2\theta} \\ &= \frac{\sigma^2}{2\theta}\bigl(1 - e^{-2\theta t}\bigr). \tag{3} \end{aligned}$$

Equations (2) and (3) are the required expressions.

Idea

Track the game state as the longest suffix of the flip sequence that is a prefix of either target pattern. This yields a small Markov chain whose first-step equations determine the win probability exactly.

States and Transitions

Target patterns: Player 1 wins on $HTH$; Player 2 wins on $HHT$.

The transient states are $\{\varepsilon,\, H,\, HH,\, HT\}$, where $\varepsilon$ denotes no useful suffix (start, or after a progress-resetting tail).

State	Flip $H$	Flip $T$
$\varepsilon$	$H$	$\varepsilon$
$H$	$HH$	$HT$
$HH$	$HH$	P2 wins
$HT$	P1 wins	$\varepsilon$

Remark on $HH \xrightarrow{H} HH$: after any run of heads, the longest suffix that prefixes a target is still $HH$ (the length-2 prefix of $HHT$).

System of Equations

Let $p_s$ denote the probability that Player 1 wins from state $s$.

$$p_{\varepsilon} = \tfrac{1}{2}p_H + \tfrac{1}{2}p_{\varepsilon} \implies p_{\varepsilon} = p_H \tag{1}$$ $$p_H = \tfrac{1}{2}p_{HH} + \tfrac{1}{2}p_{HT} \tag{2}$$ $$p_{HH} = \tfrac{1}{2}p_{HH} + \tfrac{1}{2}\cdot 0 \implies p_{HH} = 0 \tag{3}$$ $$p_{HT} = \tfrac{1}{2}\cdot 1 + \tfrac{1}{2}\,p_{\varepsilon} \tag{4}$$

Equation (3) reflects that $HH$ is a trap: every additional $H$ keeps the game in $HH$, and the inevitable first $T$ completes $HHT$, so Player 1 cannot win from $HH$.

Solution

Substituting $(3)$ into $(2)$:

$$p_H = \tfrac{1}{2}p_{HT}.$$

Combined with $(1)$, we have $p_{\varepsilon} = p_H = \tfrac{1}{2}p_{HT}$. Substituting into $(4)$:

$$p_{HT} = \frac{1}{2} + \frac{1}{2}\cdot\frac{1}{2}p_{HT} = \frac{1}{2} + \frac{1}{4}p_{HT}.$$ $$\frac{3}{4}p_{HT} = \frac{1}{2} \implies p_{HT} = \frac{2}{3}.$$ $$p_{\varepsilon} = \frac{1}{2}\cdot\frac{2}{3} = \boxed{\dfrac{1}{3}}.$$

The game begins in state $\varepsilon$, so Player 1 wins with probability $\dfrac{1}{3}$.

This is a classic "jeep problem" (desert crossing) variant. The tanker starts with $3000$ gallons at Port A, must travel $1000$ miles to Port B, loses $1$ gallon per mile, and has capacity $1000$ gallons. The goal is to maximize delivered oil.

Key insight: The optimal strategy uses intermediate depots and shuttles oil forward in stages, each stage moving a certain amount of oil a certain distance while consuming fuel for round trips. The number of trips decreases by one each stage.

Let $D = 1000$ miles, capacity $C = 1000$ gallons, initial fuel $F = 3000$ gallons. Consumption is $1$ gallon per mile.

General principle: To move $n$ full loads (i.e., $n \times 1000$ gallons) a distance $d$, you make $n$ forward trips and $n-1$ return trips, consuming $(2n-1)d$ gallons. The amount delivered forward is $nC - (2n-1)d$.

Stage 1: Start with $3000$ gallons at A, i.e., $n_1 = 3$ loads. Move forward distance $d_1$ such that after shuttling we have exactly $n_2 = 2$ loads ($2000$ gallons) at the next depot. Fuel consumed: $(2\cdot3-1)d_1 = 5d_1$. Remaining: $3000 - 5d_1 = 2000 \Rightarrow d_1 = 200$ miles.

Stage 2: At mile $200$, we have $2000$ gallons ($n_2 = 2$ loads). Move forward distance $d_2$ to reduce to $1$ load ($1000$ gallons). Fuel consumed: $(2\cdot2-1)d_2 = 3d_2$. Remaining: $2000 - 3d_2 = 1000 \Rightarrow d_2 = 333\frac{1}{3}$ miles.

Stage 3: At mile $200 + 333\frac{1}{3} = 533\frac{1}{3}$, we have $1000$ gallons ($n_3 = 1$ load). Drive directly to B, which is $1000 - 533\frac{1}{3} = 466\frac{2}{3}$ miles away. Fuel consumed: $466\frac{2}{3}$ gallons. Delivered: $1000 - 466\frac{2}{3} = 533\frac{1}{3}$ gallons.

Thus the maximum deliverable is $533\frac{1}{3}$ gallons, which rounds to $533$ gallons.

Verification: Total fuel consumed = $5\times200 + 3\times333\frac{1}{3} + 1\times466\frac{2}{3} = 1000 + 1000 + 466\frac{2}{3} = 2466\frac{2}{3}$ gallons, matching $3000 - 533\frac{1}{3}$. Total distance traveled = same sum, confirming consumption rate.