Adapted from the 10/19 Riddler:

Q:

There are $N$ nodes, connected by edges. There is exactly one path from any node to any other node. Then, something occurs and each node has a probability $p$ of disappearing. What is the maximum for the expected value of the number of connected components that results, and for what value of $p$ is this maximum achieved?

A:

Initially, I thought that, based on the Riddler’s problem, the nodes were all connected in a single line. I constructed a recurrence relation.

Either the first island disappeared with a probability $p$, and we were left with $(N-1)$ nodes, or the other $1-p$ of the time, the first node is intact. If the first node is intact, either the second node disappears with probability p, and we are left with $E[N-2] + 1$ connected components, or the second island remains intact. Thus, we have:

\[ E[N] = pE[N-1] + (1-p) \Biggl[ p(E[N-2] + 1) + (1-p) \Bigl[ p(E[N-3] + 1) + (1 - p)[ \dots ] \Bigr] \Biggr] \]

But, we can also consider $E[N-1]$:

\[ E[N-1] = pE[N-2] + (1-p) \Biggl[ p(E[N-3] + 1) + (1-p) \Bigl[ p(E[N-4] + 1) + (1 - p)[…] \Bigr] \Biggr] \]

And, we see that by adding $p$ to both sides, we have:

\[ E[N-1] + p = p(E[N-2] +1) + (1-p) \Biggl[ p(E[N-3] + 1) + (1-p) \Bigl[ p(E[N-4]) + 1) + (1 - p)[…] \Bigr] \Biggr] \]

And, finally, we perform a substitution to get:

\[ E[N] = pE[N-1] + (1-p)(E[N-1] + p) = pE[N-1] + (1-p)E[N-1] + p - p^2 \]

Or:

\[ E[N] = E[N-1] + p - p^2 \]

This turns out to have an interpretation even in the more general case, when there are N nodes, but they structured in a general tree shape. First, consider a leaf. Any leaf is joined to one other node by a single edge. $(1-p)$ of the time, that leaf doesn’t disappear, and so it contributes $(1-p)$ to the expected value. However, $(1-p)^2$ of the time, the leaf and the node it is attached to both remain, and so we have overcounted by that much. Thus,

\[ E[N] = E[N-1] + (1-p) - (1-p)^2 = E[N-1] + 1 - p - 1 + 2p - p^2 = E[N-1] + p - p^2 \]

Thus, we recover the same recurrence relationship.

Setting $E[1] = p$, we have that:

\[ E[N] = p + N(p - p^2) \]

And we see that, taking derivatives:

\[ 1 + N - 2Np = 0 \]

\[ p = \frac{1 + N}{2N} \]