Tuesday 1 September 2026

The strategy

Every prisoner uses the same rule, keyed to his own number. Prisoner $i$ opens box $i$ first. He reads the slip $\sigma (i)$ inside; if it is his own number $i$ he is done, otherwise he opens box $\sigma (i)$ next, reads $\sigma (\sigma (i))$, opens that box, and so on. He follows the chain $$i\to \sigma (i)\to {\sigma }^2(i)\to \cdots$$ for up to $50$ steps.

The naive alternative — each prisoner opens $50$ boxes at random — gives success probability $(1/2{)}^{100}\approx 8\times {10}^{-31}$, and it is tempting to conclude the situation is hopeless. The whole point is that a fixed random search treats the prisoners' fates as independent, whereas the cycle-following rule couples them to a single global event.

Why cycle-following works

Under this rule the sequence of boxes prisoner $i$ opens is exactly the forward orbit of $i$ under $\sigma$. Since $\sigma$ is a permutation of a finite set, that orbit is the cycle of $\sigma$ containing $i$, and the box holding slip $i$ is the box ${\sigma }^{-1}(i)$ — the element that maps to $i$, i.e. the predecessor of $i$ on its own cycle. Following $i\to \sigma (i)\to \cdots$ eventually returns to $i$, and the step just before returning lands on box ${\sigma }^{-1}(i)$, which contains slip $i$.

Hence prisoner $i$ finds his slip on some step, and he reaches it within $50$ openings iff the cycle containing $i$ has length at most $50$. This is the step a candidate misses: the individual success events, one per prisoner, all reduce to statements about the same object, the cycle lengths of $\sigma$.

Therefore $$\{\text{all freed}\}=\{\sigma \text{ has no cycle of length}>50\}.$$

Exact probability for 100 prisoners

A permutation of $100$ elements can have at most one cycle of length exceeding $50$, since two such would need more than $100$ elements. So the failure event is a disjoint union over $L=51,\dots ,100$ of "$\sigma$ has a cycle of length exactly $L$."

Count permutations of $\{1,\dots ,n\}$ with a distinguished cycle of length $L$: choose the $L$ members in $\left(\genfrac{}{}{0ex}{}{n}{L}\right)$ ways, arrange them in a cycle in $(L-1)!$ ways, and permute the remaining $n-L$ arbitrarily in $(n-L)!$ ways: $$\left(\genfrac{}{}{0ex}{}{n}{L}\right)(L-1)!(n-L)!=\frac{n!}{L}.$$ With $n=100$, the probability of having a cycle of length exactly $L>50$ is ${\displaystyle \frac{n!/L}{n!}}={\displaystyle \frac{1}{L}}$. Summing the disjoint cases, $$\mathbb{P}(\text{fail})=\sum _{L=51}^{100}\frac{1}{L}=H_{100}-H_{50},$$ where $H_n={\sum }_{k=1}^{n}1/k$. Thus $$\mathbb{P}(\text{freed})=1-\sum _{L=51}^{100}\frac{1}{L}=1-(H_{100}-H_{50}).$$ Numerically $H_{100}-H_{50}\approx 0.688172$, so the group survives with probability $$\mathbb{P}(\text{freed})\approx 0.311828.$$

The limit

For $2m$ prisoners each opening $m$ boxes, the same argument gives $$\mathbb{P}(\text{freed})=1-\sum _{L=m+1}^{2m}\frac{1}{L}=1-(H_{2m}-H_m).$$ Since $H_{2m}-H_m={\sum }_{k=m+1}^{2m}\frac{1}{k}\to {\int }_0^1\frac{dx}{1+x}=\ln 2$ (a Riemann sum for $1/(1+x)$), $${lim}_{m\to \infty }\mathbb{P}(\text{freed})=1-\ln 2\approx 0.306853.$$

Remarks. The success probability stays bounded away from $0$ no matter how many prisoners there are — the striking feature of the puzzle. It is also a theorem (Curtin–Warshauer) that no strategy beats the cycle-following one, so $1-(H_{100}-H_{50})$ is the optimal survival probability, not merely one achievable value.

Final answers. (1) Follow the cycle from your own box; the group is freed iff $\sigma$ has no cycle longer than $50$. (2) $1-(H_{100}-H_{50})\approx 0.3118$. (3) $1-\ln 2\approx 0.3069$.

(a) The primal-dual witness and uniqueness

Since the objective is convex, $\widehat{\beta }$ is optimal iff there is a subgradient $\widehat{z}\in \partial \Vert \widehat{\beta }{\Vert }_1$ with $$\frac{1}{n}{X}^{\top }(X\widehat{\beta }-y)+\lambda \widehat{z}=0,$$ where ${\widehat{z}}_j=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\widehat{\beta }}_j)$ if ${\widehat{\beta }}_j\ne 0$ and ${\widehat{z}}_j\in [-1,1]$ if ${\widehat{\beta }}_j=0$. Substituting $y=X{\beta }^{*}+w$ and writing $\widehat{\Delta }=\widehat{\beta }-{\beta }^{*}$, stationarity becomes $$\widehat{\Sigma }\widehat{\Delta }-\frac{1}{n}{X}^{\top }w+\lambda \widehat{z}=0.\text{(\$star\$)}$$

The witness. We impose ${\widehat{\beta }}_{S^c}=0$ (so ${\widehat{\Delta }}_{S^c}=0$) and ${\widehat{z}}_S=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\beta }_S^{*})$, then solve $(\star )$ block-wise and finally check that the solution is genuinely feasible. The $S$-block of $(\star )$ gives $${\widehat{\Delta }}_S={\widehat{\Sigma }}_{SS}^{-1}(\frac{1}{n}{X}_S^{\top }w-\lambda {\widehat{z}}_S),$$ which uses invertibility of ${\widehat{\Sigma }}_{SS}$. The $S^c$-block defines the remaining dual coordinates, $${\widehat{z}}_{S^c}=\frac{1}{\lambda }(\frac{1}{n}{X}_{S^c}^{\top }w-{\widehat{\Sigma }}_{S^{c}S}{\widehat{\Delta }}_S).$$ The construction succeeds if (i) $\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\widehat{\beta }}_S)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\beta }_S^{*})$ (so that ${\widehat{z}}_S$ was a valid subgradient) and (ii) $\Vert {\widehat{z}}_{S^c}{\Vert }_{\infty }\le 1$.

The uniqueness step (the one candidates skip). Suppose $\Vert {\widehat{z}}_{S^c}{\Vert }_{\infty }<1$ strictly, and let $\tilde{\beta }$ be any optimum with subgradient $\tilde{z}$. The map $\beta \mapsto \frac{1}{2n}\Vert y-X\beta {\Vert }_2^2$ is strictly convex in the fitted value $X\beta$, and $\Vert ·{\Vert }_1$ is convex; hence over the (convex) optimal set the fitted vector $X\tilde{\beta }$ is constant. Therefore $\frac{1}{n}{X}^{\top }(y-X\tilde{\beta })$ is constant across optima, so by $(\star )$ the subgradient $\lambda \tilde{z}$ is the same for every optimum — in particular $\tilde{z}=\widehat{z}$, our constructed dual vector. Now use complementary slackness: at optimum $⟨\tilde{z},\tilde{\beta }⟩=\Vert \tilde{\beta }{\Vert }_1$, i.e. ${\sum }_j({\tilde{z}}_j{\tilde{\beta }}_j-|{\tilde{\beta }}_j|)=0$. Each summand is $\le 0$, and for $j\in S^c$ we have $|{\tilde{z}}_j|=|{\widehat{z}}_j|<1$, forcing ${\tilde{\beta }}_j=0$. Thus every optimum is supported in $S$. Finally, $X_S{\tilde{\beta }}_S=X_S{\widehat{\beta }}_S$ and $X_S$ has full column rank (again because ${\widehat{\Sigma }}_{SS}\succ 0$), so ${\tilde{\beta }}_S={\widehat{\beta }}_S$. The optimum is unique and equals the witness. $◻$

Thus ${\widehat{\Sigma }}_{SS}\succ 0$ enters twice: once to solve for ${\widehat{\Delta }}_S$, once to pass from equal fitted values to equal coefficients.

(b) Explicit dual vector and the scaling of $\lambda$

Substituting ${\widehat{\Delta }}_S$ into the formula for ${\widehat{z}}_{S^c}$, $${\widehat{z}}_{S^c}=\underset{\text{incoherence term}}{\underbrace{{\widehat{\Sigma }}_{S^{c}S}{\widehat{\Sigma }}_{SS}^{-1}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\beta }_S^{*})}}+\underset{=:\frac{1}{\lambda }\Pi w}{\underbrace{\frac{1}{\lambda }[\frac{1}{n}{X}_{S^c}^{\top }w-{\widehat{\Sigma }}_{S^{c}S}{\widehat{\Sigma }}_{SS}^{-1}\frac{1}{n}{X}_S^{\top }w]}}.$$ The incoherence term is bounded by $1-\gamma$ by hypothesis. So strict feasibility holds provided the noise term satisfies $\Vert \Pi w{\Vert }_{\infty }\le \lambda \gamma$ (then $\Vert {\widehat{z}}_{S^c}{\Vert }_{\infty }\le 1-\gamma +\gamma =1$, and one takes $<\gamma$ for strictness).

Each coordinate of $\Pi w$ is a mean-zero Gaussian. Its variance is bounded by the variance of $\frac{1}{n}{X}_j^{\top }w$ (projection reduces variance), which is ${\sigma }^2\Vert X_j{\Vert }_2^2/n^2={\sigma }^2/n$ by the normalization. A maximum over $\le p$ Gaussians of variance $\le {\sigma }^2/n$ obeys, with probability $\ge 1-2p^{-1}$, $$\Vert \Pi w{\Vert }_{\infty }\le 2\sigma \sqrt{\frac{\log p}{n}}.$$ Hence it suffices to choose $$\lambda \ge \frac{2\sigma }{\gamma }\sqrt{\frac{\log p}{n}},\text{i.e. }\lambda \asymp \frac{\sigma }{\gamma }\sqrt{\frac{\log p}{n}}.$$ For the signs to be preserved we need ${\widehat{\Delta }}_S={\widehat{\Sigma }}_{SS}^{-1}(\frac{1}{n}{X}_S^{\top }w-\lambda \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\beta }_S^{*}))$ small in sup-norm relative to the signal; a sufficient condition is $${min}_{j\in S}|{\beta }_j^{*}|>\backslash |{\widehat{\Sigma }}_{SS}^{-1}{\backslash |}_{\infty }(\lambda +\frac{1}{n}\Vert X_S^{\top }w{\Vert }_{\infty }),$$ the $\beta$-min condition. Under both, part (a) gives exact sign recovery with probability $\ge 1-2p^{-1}$.

(c) The concrete design

(i) Positive definiteness. Leading minors of $\widehat{\Sigma }$ are $1$, $1$, and $det\widehat{\Sigma }=1(1-c^2)-0+c(0-c)=1-2c^2$. So $\widehat{\Sigma }\succ 0⟺|c|<1/\sqrt{2}$.

(ii) Exact recovery region. Here ${\widehat{\Sigma }}_{SS}=I_2$, so ${\widehat{\Sigma }}_{SS}^{-1}=I_2$, ${\widehat{\Sigma }}_{S^{c}S}=(c,c)$, and $\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({\beta }_S^{*})=(+1,+1)$. Noiseless, so $\Pi w=0$.

• Dual feasibility on $S^c$: ${\widehat{z}}_3=(c,c)(1,1{)}^{\top }=2c$. Strict feasibility $⟺|2c|<1⟺|c|<\frac{1}{2}$.
• Sign preservation on $S$: ${\widehat{\Delta }}_S=-\lambda (1,1{)}^{\top }$, so ${\widehat{\beta }}_S=(3-\lambda ,2-\lambda )$. Both stay positive $⟺\lambda <2$ (the smaller magnitude, $|{\beta }_2^{*}|=2$, is binding).

Both requirements are strict, and $|c|<1/2$ already guarantees $\widehat{\Sigma }\succ 0$. Therefore $$\boxed{\text{exact sign recovery}⟺|c|<\frac{1}{2}\text{ and }0<\lambda <2.}$$ At the boundaries recovery fails: $|c|=\frac{1}{2}$ gives ${\widehat{z}}_3=\pm 1$ (non-strict, solution can be non-unique with a spurious third coordinate), and $\lambda \ge 2$ kills the second coordinate.

(iii) The sign mechanism. With signs $(+,-)$ the incoherence term becomes $${\widehat{z}}_3=(c,c)(1,-1{)}^{\top }=c-c=0,$$ which is strictly feasible for every $c$ in the PD range $|c|<1/\sqrt{2}$. So the same design recovers the support for $|c|<1/\sqrt{2}\approx 0.707$, strictly larger than the $|c|<1/2$ of the $(+,+)$ pattern. The reason: the off-support column $X_3$ correlates equally ($c$) with $X_1$ and $X_2$; when the two active coordinates carry opposite signs their pulls on the dual coordinate cancel, whereas equal signs add. Irrepresentability is genuinely a property of the signed support, not just the support.

Closing note. The textbook mutual-incoherence constant ${max}_{z\in \{\pm 1{\}}^s}\Vert {\widehat{\Sigma }}_{S^{c}S}{\widehat{\Sigma }}_{SS}^{-1}z{\Vert }_{\infty }$ takes the worst case over signs; here that worst case is $2|c|$, giving the pessimistic threshold $|c|<1/2$. The tempting error is to treat that worst-case number as the recovery threshold for a given ${\beta }^{*}$. For a fixed signed support only the actual sign vector matters, and — as $(+,-)$ shows — the true threshold can be much more generous.