Manuscript Hawk05-B@1 · Hawk05-B.tex · theorem · f2e5d4f5

Theorem: All-prefix capacity approximation

Derivation of the finite Page curve › A simultaneous leading Page law without resampling · lines 662–726 · proof included or linked

Hawk05-B@1#thm:uniform, Hawk05-B@1#eq:gap, Hawk05-B@1#eq:allprefix, Hawk05-B@1#eq:leadingpage

Back to manuscript

For one sampled $U$ , set

Δ_{k} (U, ψ) = T_{k} - S_{k} (U, ψ) \geq 0.

Then

0 \leq E Δ_{k} \leq lo g_{2} (1 + m_{k} / n_{k}) \leq \frac{s ^{- ∣ N - 2 k ∣}}{ln 2} .

Consequently, with

C_{s} = \frac{s ^{2} + 1}{( s ^{2} - 1 ) ln 2},

for every $z > 0$ ,

P {0 \leq k \leq N max Δ_{k} > z} \leq min {1, C_{s} / z} .

In particular, for fixed $s$ and inputs $ψ_{N}$ independent of $U_{N}$ ,

k max \frac{S _{k} ( U _{N} , ψ _{N} )}{N lo g _{2} s} - min (\frac{k}{N}, 1 - \frac{k}{N}) ⟶ 0 in probability.

Proof. A reduction has rank at most $m_{k}$ , so its entropy is at most $lo g_{2} m_{k}$ . The elementary Rényi bound $S (ρ) \geq - lo g_{2} Tr ρ^{2}$ follows by Jensen's inequality with weights equal to the eigenvalues. Thus

E Δ_{k} \leq lo g_{2} (m_{k} \frac{m _{k} + n _{k}}{m _{k} n _{k} + 1}) \leq lo g_{2} (1 + m_{k} / n_{k}) .

This proves (eq:gap).

For even $N$ , the infinite extension of the sum of $s^{- ∣ N - 2 k ∣}$ is $1 + 2/ (s^{2} - 1)$ . For odd $N$ , it is $2 s / (s^{2} - 1)$ , which is no larger. Therefore

E k \sum Δ_{k} \leq C_{s} .

Markov's inequality and $max_{k} Δ_{k} \leq \sum_{k} Δ_{k}$ prove (eq:allprefix). Take $z = ϵ N lo g_{2} s$ to obtain (eq:leadingpage).

Displayed formulas in this passage

Hawk05-B@1#eq:gap · line 669
$0 \leq E Δ_{k} \leq lo g_{2} (1 + m_{k} / n_{k}) \leq \frac{s ^{- ∣ N - 2 k ∣}}{ln 2} .$
Hawk05-B@1#eq:allprefix · line 680
$P {0 \leq k \leq N max Δ_{k} > z} \leq min {1, C_{s} / z} .$
Hawk05-B@1#eq:leadingpage · line 687
$k max \frac{S _{k} ( U _{N} , ψ _{N} )}{N lo g _{2} s} - min (\frac{k}{N}, 1 - \frac{k}{N}) ⟶ 0 in probability.$
unlabeled · line 665
$Δ_{k} (U, ψ) = T_{k} - S_{k} (U, ψ) \geq 0.$
unlabeled · line 676
$C_{s} = \frac{s ^{2} + 1}{( s ^{2} - 1 ) ln 2},$
unlabeled · line 706
$E Δ_{k} \leq lo g_{2} (m_{k} \frac{m _{k} + n _{k}}{m _{k} n _{k} + 1}) \leq lo g_{2} (1 + m_{k} / n_{k}) .$
unlabeled · line 719
$E k \sum Δ_{k} \leq C_{s} .$

Theorem: All-prefix capacity approximation

Displayed formulas in this passage

Nearby in this section