Why recovery balance survives duality

Let C be a linear code with n ≥ 1 coordinates, dimension k, and orthogonal dual C^⊥. Let E be the set of coordinate indices. We read indices independently and uniformly, with replacement: a repeated read still costs one read. Write a_i(C) for the expected number of reads needed to recover coordinate i.

The proof connects two questions: what a set of coordinates tells us, and how long random reads take to collect that information. A coordinate that is always zero is known before any read.

1. Express failure to recover as one missing dimension

   Choose a generator matrix with columns g_j. Define r_C(S) as the dimension of the span of the columns indexed by S. Observing S determines coordinate i exactly when g_i lies in that span.

   Adding one column increases the dimension by either zero or one. Therefore the following difference is 0 if recovery succeeds and 1 if it fails:

   $d_C(i,S)=r_C(S\cup \{i\left\}\right)-r_C\left(S\right)$

   The same rank is the dimension of the projection of the code onto S, so it does not depend on which generator matrix we chose.

2. Derive the rank formula for the dual code

   Fix a set A and let B = E ∖ A. Project C^⊥ onto A. The vectors lost by this projection are precisely the dual vectors supported entirely on B.

   Such vectors are orthogonal to the projection of C onto B, so their space has dimension |B| − r_C(B). The whole dual code has dimension n − k. Subtracting the dimension of the kernel from the dimension of the domain gives the dimension of the image:

   r_C^⊥(A) = (n − k) − (|B| − r_C(B)).

   Since |B| = n − |A|, this simplifies to:

   $r_{C^{\perp }}\left(A\right)=\left|A\right|-k+r_C(E\setminus A)$

3. Apply that formula to complementary observations

   Keep target i aside. Split the other coordinates into S and U = E ∖ (S ∪ {i}). Apply the dual-rank formula first to U ∪ {i} and then to U:

   r_C^⊥(U ∪ {i}) = |U| + 1 − k + r_C(S),

   r_C^⊥(U) = |U| − k + r_C(S ∪ {i}).

   Subtract the second line from the first. The common terms cancel, leaving:

   $d_{C^{\perp }}(i,U)=1-d_C(i,S)$

   Thus exactly one succeeds: recovery from S in C, or recovery from U in C^⊥. This is the algebraic reason for the complementary outcomes.

4. Account for the waiting time, including repeated reads

   Imagine continuing to sample even after recovery. Let S_s be the set of the first s distinct indices seen, and W_s the number of further reads until the next new index. Repeated indices add no information, so recovery cannot change during those repeats.

   After s distinct indices, each read has probability (n − s)/n of finding a new one. Conditional on the entire history so far, the mean waiting time is n/(n − s).

   The recovery time T_i is the sum of W_s over precisely those stages at which recovery still fails. Equivalently:

   T_i = ∑_{s=0,…,n−1} d_C(i,S_s) W_s.

   For sets already containing i, the failure indicator is zero. The argument uses the conditional waiting-time mean; it does not assume independence between the failure indicator and the waiting time. The first read of i itself has mean n and always suffices, so the expected recovery time is finite.

5. Convert the random process into a finite weighted sum

   By symmetry, S_s is uniform among all subsets of E of size s. A particular set therefore contributes its failure indicator times the weight

   $\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{s}\right)}·\frac{n}{n-s}=\frac{1}{\left(\genfrac{}{}{0ex}{}{n-1}{s}\right)}$

   Sets containing the target contribute zero. Taking expectations in the stage decomposition gives:

   $a_i\left(C\right)=\sum _{S:i\notin S}\frac{d_C(i,S)}{\left(\genfrac{}{}{0ex}{}{n-1}{\left|S\right|}\right)}$

   The weight includes all repeated reads through the factor n/(n − s).

6. Pair complementary sets and evaluate the total

   The map S ↦ U pairs every subset not containing i with its complement among the other n − 1 coordinates. Both sets have the same weight, because choosing s indices gives as many subsets as choosing n − 1 − s.

   Add the weighted sums for the code and its dual. Each paired numerator is d_C(i,S) + d_C^⊥(i,U) = 1, by the algebraic calculation above. For each size s, the number of subsets cancels the denominator of their weight, contributing exactly 1. There are n sizes, from 0 to n − 1:

   $a_i\left(C\right)+a_i\left(C^{\perp }\right)=n$

The conjecture follows: a code is recovery balanced when all coordinates have the same expected recovery time. Every dual expectation equals n minus the original one. Hence the original profile is constant exactly when the dual profile is constant: C is recovery balanced if and only if C^⊥ is.