Jane Street April 2025 Puzzle

This month's puzzle is:

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 $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.

My interpretation, which I find simpler, is this. Let $x$ be the probability of labelling a node 0, so labelling it 1 has probability $1-x$. The question asks for the value of $x$ that yields a tree with a $50\%$ chance of at least one path whose nodes are all 0, or where only a single node is 1.

A labeled binary tree. The red path traces a route down the tree that passes through at most one node labeled 1, exactly the event we are trying to make happen with probability one half.

To answer this, we can take advantage of the fact that the binary tree is a recursive structure, meaning we can solve a smaller case and extrapolate to the infinite tree.

Consider a trivial, smaller case with 1 root and 2 children. There are two cases:

1. $A$ = a path from the root to a child consisting of only 0s
2. $B$ = a path from the root to a child consisting of only one 1

Case A

For $A$, at least one child has a label of 0, which is the same as neither child being 1.

1. Neither child being 1 is the complement of both children being 1.
2. Both children being 1 is given by $(1-x)^2$.
3. Taking the complement gives $1 - (1-x)^2$.
4. Since the root must also be 0, we get $x \cdot (1 - (1-x)^2)$.

$\therefore \Pr(A) = x \cdot (1 - (1-x)^2)$

Case B

For $B$, there are a few more cases, even in the trivial example.

1. The root could be 0, in which case one of the children needs to be 1.
   1. If the left node is 0 and the right node is 1, we get $x \cdot (1-x)$.
   2. The same holds the other way around, $(1-x) \cdot x$.
   3. Summing these probabilities gives $2x(1-x)$.
   4. Including the root, we get $2x^2(1-x)$.
2. The root could be 1, in which case all of the children must be 0.
   1. When all children must be 0, we can reuse our calculation from $A$.
   2. The complement of both children being 1 is $1 - (1-x)^2$.
   3. Including the root as 1, we get $(1-x) \cdot (1 - (1-x)^2)$.

$\therefore \Pr(B) = 2x^2(1-x) + (1-x) \cdot (1 - (1-x)^2)$

Extrapolating to the infinite tree

Recall the recursive property of a binary tree. Since each child can be treated as a new root, we can extrapolate these two equations to an infinite tree.

For $A$, since the root must be 0, we replace the probability of the child with $A$ itself:

$A = x \cdot (1 - (1-A)^2)$

For $B$, there are multiple cases once again.

1. We have yet to assign a node 1, meaning the previous node was 0 and any following node can be 1.
   1. If the previous node was 0, one of the children must include a path with a node labeled 1. Consider $B$ to be this valid path.
   2. The probability that either child gives this path is the complement of neither giving it.
   3. The probability that neither gives this path is $(1-B)^2$.
   4. The complement is $1 - (1-B)^2$.
   5. But we must still assign the previous node a label of 0, giving $x \cdot (1 - (1-B)^2)$.
2. We have used up our single label of 1, meaning all following nodes must be 0.
   1. This is a repeat of $A$, giving $x \cdot (1 - (1-A)^2)$.
   2. The previous node is no longer 0, and we must assign it a label of 1, giving $(1-x) \cdot (1 - (1-A)^2)$.

$B = x \cdot (1 - (1-B)^2) + (1-x) \cdot (1 - (1-A)^2)$

So our final recursive equations as $n \Rightarrow \infty$, where $n$ is the length of the tree, are:

$A = x \cdot (1 - (1-A)^2)$

$B = x \cdot (1 - (1-B)^2) + (1-x) \cdot (1 - (1-A)^2)$

Solving for x

To solve these equations for $x$, you have a number of choices, but I chose to write a Python script that performs a binary search for $x \in (0.5, 1)$, since all values of $x \leq 0.5$ and $x \geq 1$ are trivially rejected. I would normally reach for C or a functional language for a problem of this kind, but since we are limited to the first 10 decimals, Python's 15-digit float is more than enough.

import numpy as np
 
def F0(p):
    """Probability of an all-0 infinite path, starting at a fresh node."""
    if p <= 0.5:
        return 0.0
    else:
        return (2*p - 1)/p
 
def F1(p):
    """Probability of an infinite path with at most one '1', from a fresh node."""
    if p <= 0.5:
        return 0.0
 
    x = F0(p)  # This is F_0
    # Solve the quadratic: y = p[2y - y^2] + (1-p)[2x - x^2]
    # i.e.  0 = -p*y^2 + (2p-1)*y + (1-p)[2x - x^2]
    a = -p
    b = 2*p - 1
    c = (1-p)*(2*x - x*x)
 
    disc = b*b - 4*a*c
    sqrt_disc = np.sqrt(disc)
    y1 = (-b + sqrt_disc)/(2*a)
    y2 = (-b - sqrt_disc)/(2*a)
    valid = [r for r in (y1, y2) if 0 <= r <= 1]
 
    if not valid:
        return 0.0
    return max(valid)
 
def solve_for_p(target=0.5, tol=1e-14):
    left, right = 0.5, 1.0
    for _ in range(200):
        mid = (left + right)/2
        val = F1(mid)
        if val < target:
            left = mid
        else:
            right = mid
        if abs(right - left) < tol:
            break
    return (left + right)/2
 
p_star = solve_for_p()
print(f"p = {p_star:.10f}")

This program converges at around $x = 0.5306035754$.

So our final answer is $p = 0.5306035754$.