Sum One, Somewhere — counting paths through an infinite random tree

puzzle

math

python

How I solved Jane Street’s April 2025 puzzle with two recursive equations, one branch choice, and a tidy little cubic.

Author

Victor S HUANG

Published

03 May 2025

Another writeup I owed myself. The April 2025 Jane Street puzzle asked:

For a fixed \(p\), independently label the nodes of an infinite complete binary tree \(0\) with probability \(p\), and \(1\) otherwise. For what \(p\) is there exactly a \(\tfrac{1}{2}\) probability that there exists an infinite path down the tree that sums to at most \(1\) (that is, all nodes visited, with the possible exception of one, will be labeled \(0\)). Find this value of \(p\) accurate to 10 decimal places.

I solved it and want to write it up properly. The puzzle is on the easier end — once you spot the right recursion, the rest is bookkeeping — so I’ll take the chance to spend a few extra paragraphs on why the recursion works and what could go wrong if you set it up carelessly.

What we’re really being asked

The tree is infinite, complete, and binary: every node has exactly two children, forever. Each node is independently labeled \(0\) (probability \(p\)) or \(1\) (probability \(1-p\)). A path down the tree starts at the root and, at each step, picks one of the two children — so a path is an infinite sequence of nodes.

“Sum at most \(1\)” means the labels along the path add up to \(\le 1\). Since labels are \(0\) or \(1\), that’s the same as saying the path uses at most one node labeled \(1\).

Define two events on the subtree rooted at any given node:

\(A\) = “some infinite path down this subtree has sum \(\le 1\)” (at most one \(1\)),
\(B\) = “some infinite path down this subtree has sum \(\le 0\)” (all \(0\)s).

Let \(a = \Pr(A)\) and \(b = \Pr(B)\). Both are well-defined: every node’s subtree is statistically identical to every other node’s subtree, so the probabilities don’t depend on which node you root at. The puzzle asks for the \(p\) that makes \(a = \tfrac{1}{2}\).

Setting up the recursion

The trick is to condition on the root’s label and on the two child subtrees. The two children are independent copies of the whole tree, so their events are independent of each other and of the root.

Equation for \(b\). A subtree contains an all-zero path iff (i) the root is \(0\), and (ii) at least one of the two child subtrees contains an all-zero path.

\[ b = p \cdot \bigl[1 - (1-b)^2\bigr] = p \cdot b(2-b). \]

Equation for \(a\). A subtree contains a “\(\le 1\) ones” path iff:

the root is \(0\) (probability \(p\)), and a child subtree continues with a \(\le 1\) ones path — at least one of the two children must succeed, so probability \(1 - (1-a)^2 = a(2-a)\); or
the root is \(1\) (probability \(1-p\)), in which case the path has already used its one \(1\), and a child subtree must continue with an all-zero path — probability \(b(2-b)\).

\[ a = p \cdot a(2-a) + (1-p) \cdot b(2-b). \]

That’s the whole setup. Now we have to solve.

Picking the right branch

The first equation factors as \(b\bigl[1 - p(2-b)\bigr] = 0\), so

\[ b = 0 \qquad \text{or} \qquad b = 2 - \tfrac{1}{p}. \]

Both are honest fixed points. Which one is the actual probability?

This is a classical Galton–Watson survival question in disguise. Walk down the tree taking only \(0\)-labeled nodes; at each step you have \(0\), \(1\), or \(2\) surviving children, with mean \(2p\). The branching process survives forever with positive probability iff its mean offspring is \(> 1\), i.e. \(p > \tfrac{1}{2}\). Below that threshold the all-zero path dies out almost surely and \(b = 0\). Above it, the survival probability is the non-trivial root, \(b = 2 - 1/p\).

A puzzle with answer “exactly \(\tfrac{1}{2}\)” can’t live in the \(b = 0\) regime (we’ll see why momentarily), so we take

\[ b = 2 - \tfrac{1}{p}, \qquad p > \tfrac{1}{2}. \]

The cubic

Substitute that \(b\) into the equation for \(a\). First simplify \(b(2-b)\):

\[ b(2-b) = \left(2 - \tfrac{1}{p}\right)\!\left(\tfrac{1}{p}\right) = \frac{2p-1}{p^2}. \]

So the \(a\)-equation becomes

\[ a = p \cdot a(2-a) + (1-p) \cdot \frac{2p-1}{p^2}. \]

Setting \(a = \tfrac{1}{2}\) (the puzzle’s condition), so \(a(2-a) = \tfrac{3}{4}\):

\[ \tfrac{1}{2} = \tfrac{3p}{4} + \frac{(1-p)(2p-1)}{p^2}. \]

Multiply through by \(4p^2\):

\[ 2p^2 = 3p^3 + 4(1-p)(2p-1). \]

Expand the last term: \(4(1-p)(2p-1) = 4(2p - 1 - 2p^2 + p) = -8p^2 + 12p - 4\). Collecting,

\[ 2p^2 = 3p^3 - 8p^2 + 12p - 4 \quad\Longrightarrow\quad \boxed{\,3p^3 - 10p^2 + 12p - 4 = 0.\,} \]

A cubic in \(p\). The puzzle says “find \(p\) to 10 decimal places,” so we just need its root in \((\tfrac{1}{2}, 1)\).

Monte Carlo gut-check

Before I trust the cubic, I want to see the recursion match a simulation. Sampling an infinite tree is impossible, but the path either “fails” within the first few dozen levels or it doesn’t — at depth \(D\) around 100, the probability of a \(\le 1\)-ones path of length \(D\) is already indistinguishable from the limit at the precision we care about.

import numpy as np

def survives(p, depth, k, rng):
    """Does some path of length `depth` use at most k ones, under labelling p?"""
    if depth == 0:
        return True
    label = 0 if rng.random() < p else 1
    if label == 1:
        k -= 1
        if k < 0:
            return False
    return (
        survives(p, depth - 1, k, rng)
        or survives(p, depth - 1, k, rng)
    )

import sys
sys.setrecursionlimit(5000)

rng = np.random.default_rng(20250403)
p_star = 0.5306035754
N, depth = 5000, 120
hits = sum(survives(p_star, depth, 1, rng) for _ in range(N))
print(f"Monte Carlo at p = {p_star}: {hits / N:.4f}  (target 0.5)")

Monte Carlo at p = 0.5306035754: 0.5008  (target 0.5)

The simulator does the recursion the same way the math does — try the left subtree, and if that fails, try the right. With 5,000 trials at depth 120 the estimate sits around \(0.5\), exactly as the analytic answer demands.

Solving the cubic exactly

sympy solves it symbolically. Three real roots fall out; only one of them lies in \((\tfrac{1}{2}, 1)\).

from sympy import Rational, solve, sqrt, simplify, cbrt, nsimplify, latex
from sympy.abc import p

cubic = 3*p**3 - 10*p**2 + 12*p - 4
roots = solve(cubic, p)
for r in roots:
    val = complex(r.evalf())
    if abs(val.imag) < 1e-10 and 0.5 < val.real < 1:
        p_root = r
print("Exact root:")
print(p_root)
print()
print(f"Decimal:    {p_root.evalf(15)}")
print(f"Submission: {p_root.evalf(11)}")

Exact root:
-(134/27 + 2*sqrt(57)/3)**(1/3)/3 + 8/(27*(134/27 + 2*sqrt(57)/3)**(1/3)) + 10/9

Decimal:    0.530603575430005
Submission: 0.53060357543

Tidied up, the closed form is

\[ p^{\star} = \frac{10}{9} - \frac{1}{3}\sqrt[3]{\tfrac{134}{27} + \tfrac{2\sqrt{57}}{3}} + \frac{8}{27}\Bigl(\tfrac{134}{27} + \tfrac{2\sqrt{57}}{3}\Bigr)^{-1/3}. \]

That comes out of Cardano’s formula applied to the depressed cubic; it’s not pretty, but it’s exact. To ten decimal places,

\[ p^{\star} = 0.5306035754. \]

A picture of the bifurcation

The reason picking the right branch matters is best seen as a graph. Plot \(a\) and \(b\) as functions of \(p\):

For \(p \le \tfrac{1}{2}\), the branching process dies. Both \(a\) and \(b\) are \(0\).
For \(p > \tfrac{1}{2}\), the non-trivial fixed points kick in and rise smoothly toward \(1\) as \(p \to 1\).

The puzzle’s answer is the \(p\) at which the red curve crosses \(\tfrac{1}{2}\).

import numpy as np
import matplotlib.pyplot as plt

ps = np.linspace(0, 1, 600)
b = np.where(ps > 0.5, 2 - 1/np.where(ps > 0, ps, 1), 0.0)
b = np.clip(b, 0, 1)

# a satisfies a = p a(2-a) + (1-p) b(2-b); solve the quadratic in a per p.
def a_of(p, b):
    if p <= 0.5:
        return 0.0
    # p a^2 - (2p - 1) a + (1-p) b (2-b) wait — rearrange:
    # a = p a (2 - a) + (1-p) b (2-b)
    # a - 2p a + p a^2 = (1-p) b (2 - b)
    # p a^2 - (2p - 1) a - (1-p) b (2-b) = 0
    A, B, C = p, -(2*p - 1), -(1 - p) * b * (2 - b)
    disc = B*B - 4*A*C
    r1 = (-B - np.sqrt(disc)) / (2*A)
    r2 = (-B + np.sqrt(disc)) / (2*A)
    # Pick the root in (0, 1] — the one that grows continuously from 0 at p = 0.5.
    return r1 if 0 <= r1 <= 1 else r2

a = np.array([a_of(pp, bb) for pp, bb in zip(ps, b)])
p_star = 0.5306035754

fig, ax = plt.subplots(figsize=(7, 5))
ax.plot(ps, a, color="#d62728", lw=2, label=r"$\Pr(A)$ — at most one 1")
ax.plot(ps, b, color="#1f77b4", lw=2, label=r"$\Pr(B)$ — all zeros")
ax.axhline(0.5, color="black", lw=0.8, ls="--", alpha=0.6)
ax.axvline(p_star, color="black", lw=0.8, ls="--", alpha=0.6)
ax.plot([p_star], [0.5], "ko", ms=6)
ax.annotate(
    f"$p^\\star \\approx {p_star}$",
    xy=(p_star, 0.5), xytext=(p_star + 0.04, 0.42),
    arrowprops=dict(arrowstyle="->", color="black", lw=0.8),
)
ax.set_xlabel("$p$ (probability a node is labelled 0)")
ax.set_ylabel("survival probability")
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.set_aspect("equal")
ax.grid(True, alpha=0.3)
ax.legend(loc="upper left")
plt.savefig("thumbnail.png", dpi=110, bbox_inches="tight")
plt.show()

Figure 1: Survival probabilities vs \(p\). Below \(p = 1/2\) both events have probability \(0\); above it, the non-trivial branch is active. The puzzle asks for the \(p\) where \(\Pr(A) = 1/2\).

What made it nice

Two ideas carried the whole solution. First, fixing on the right event — “the subtree rooted here contains a good path” — turned an infinite-tree question into a recursion of one variable per event. Second, recognising the all-zero path as a Galton–Watson process picked the right branch of the quadratic without any hand-waving, and gave a clean threshold at \(p = \tfrac{1}{2}\).

The puzzle is a nice miniature for a more general technique: whenever you have a self-similar random structure, write down the probability of an event in terms of its restriction to the children, solve the resulting fixed-point equation, and use a separate principle (here, sub-/super-criticality) to pick the physically meaningful root. The same recipe handles “is there an infinite open path?” in percolation on a tree — the puzzle’s \(b\) is exactly the percolation probability with parameter \(p\).

The official Jane Street solution follows the same path and lands on the same cubic and the same root, \(0.5306035754\).