Manuscript Hawk05-C@1 · Hawk05-C.tex · proposition · ba0719f1

Proposition: Explicit capacity deficits

Nonuniform cells: an exact temporal proxy › Finite deficits and single-history control · lines 635–683 · proof included or linked

Hawk05-C@1#prop:deficits, Hawk05-C@1#eq:pagegap, Hawk05-C@1#eq:recordgap, Hawk05-C@1#eq:historymarkov

Back to manuscript

Let $T (r, b) = lo g_{2} m$ . Then

0 \leq T (r, b) - P (r, b) 0 \leq lo g_{2} r - L (r, b) \leq u (r, b) := lo g_{2} (1 + m / n), \leq \frac{1}{b ln 2} .

For a single sampled Haar history and every $z > 0$ ,

P {k max (T (r_{k}, b_{k}) - S (R_{k})) > z} \leq min {1, \frac{\sum _{k} u ( r _{k} , b _{k} )}{z}} .

No independence of cuts is assumed.

Proof. Haar purity is $E Tr ρ_{m}^{2} = (m + n) / (mn + 1)$ , obtained by the two-copy swap test on $E ∣ v ⟩ ⟨ v ∣^{\otimes 2} = (I + F) / (D (D + 1))$ . Since $S (ρ) \geq - lo g_{2} Tr ρ^{2}$ , Jensen's inequality gives

lo g_{2} m - E S (ρ) \leq lo g_{2} (\frac{m ( m + n )}{mn + 1}) \leq u (r, b) .

The upper entropy bound is the rank bound.

The harmonic sum obeys

ln \frac{D + 1}{b + 1} \leq H_{D} - H_{b} \leq ln \frac{D}{b} .

Its difference from $ln r$ is at most $ln (1 + 1/ b) \leq 1/ b$ , proving (eq:recordgap). Finally, every capacity deficit is nonnegative, and its expectation is bounded by (eq:pagegap). Apply Markov's inequality to their sum, which dominates their maximum.

Displayed formulas in this passage

Hawk05-C@1#eq:pagegap · line 638
$0 \leq T (r, b) - P (r, b) 0 \leq lo g_{2} r - L (r, b) \leq u (r, b) := lo g_{2} (1 + m / n), \leq \frac{1}{b ln 2} .$
Hawk05-C@1#eq:recordgap · line 638
$0 \leq T (r, b) - P (r, b) 0 \leq lo g_{2} r - L (r, b) \leq u (r, b) := lo g_{2} (1 + m / n), \leq \frac{1}{b ln 2} .$
Hawk05-C@1#eq:historymarkov · line 647
$P {k max (T (r_{k}, b_{k}) - S (R_{k})) > z} \leq min {1, \frac{\sum _{k} u ( r _{k} , b _{k} )}{z}} .$
unlabeled · line 664
$lo g_{2} m - E S (ρ) \leq lo g_{2} (\frac{m ( m + n )}{mn + 1}) \leq u (r, b) .$
unlabeled · line 673
$ln \frac{D + 1}{b + 1} \leq H_{D} - H_{b} \leq ln \frac{D}{b} .$