Introduction
The random-access problem in DNA-based storage asks how coding can reduce the number of random reads needed to recover a prescribed information symbol [1 ] . In the noiseless uniform model, k k k n n n
Related work considers several retrieval goals, including reconstructing the entire message [2 ] , [3 ] , recovering requested files [4 ] or sets of information symbols [5 ] , characterizing tradeoffs between individual file retrieval times [6 ] , [7 ] , and recovering a fraction of the message using LT codes [8 ] . Other studies address errors and nonuniform sampling [9 ] –[11 ] , repair of failed storage containers [12 ] , and parallel sampling from multiple containers [13 ] . Further coverage models consider draws that reveal subsets or windows [14 ] , and repeated observations of composite symbols or motif combinations [15 ] –[17 ] .
Here, we focus on recovering a single information symbol under noiseless uniform sampling. For a linear encoding, the requested symbol x i x_i x i e i e_i e i k k k [1 ] , [18 ] . Work on this problem includes combinatorial expressions for recovery expectations [18 ] , geometric constructions [19 ] , asymptotic and distributional analyses [20 ] , and algorithms for evaluating expectations together with improved constructions and bounds [21 ] . Recent work also establishes identities relating coordinate recovery times in a code and its dual [22 ] .
Particularly relevant are the constructions of Boruchovsky et al. [23 ] , which combine repeated systematic columns with columns supported on pairs of information coordinates. Their analysis uses a graph whose edges represent these pair observations. Besides solving the dimension-two problem, they obtained an asymptotic normalized upper bound of π 2 / 12 ≈ 0.8225 \pi^2/12 \approx0.8225 π 2 /12 ≈ 0.8225
Hofmeister, Bitar, and Yaakobi [24 ] studied binary fully symmetric generator matrices, in which all columns of a given weight occur equally often. They connected sampling from these matrices to LT encoding and proved that, for bounded column weights, the asymptotic expected recovery time divided by k k k π / 4 \pi/4 π /4
In this work, we prove that the lower bound of π / 4 \pi/4 π /4 k k k [25 ] with an integral inequality. For singleton–pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit. We also give explicit constructions over every fixed finite field attaining the optimized limit of approximately 0.793933445, and positive-rate block constructions that approximate it arbitrarily closely.
Notation and Problem Formulation
For a positive integer k k k [ k ] = { 1 , … , k } [k]=\{1,\ldots,k\} [ k ] = { 1 , … , k } F \mathbb{F} F σ \sigma σ F ∗ = F ∖ { 0 } \mathbb{F}^{*}=\mathbb{F}\setminus\{0\} F ∗ = F ∖ { 0 } e i ∈ F k e_i\in\mathbb{F}^{k} e i ∈ F k i i i v ∈ F k \mathbf{v}\in\mathbb{F}^{k} v ∈ F k supp ( v ) = { i ∈ [ k ] : v i ≠ 0 } \operatorname{supp}(\mathbf{v})=\{i\in[k]:v_i\ne0\} supp ( v ) = { i ∈ [ k ] : v i = 0 } ∣ supp ( v ) ∣ |\operatorname{supp}(\mathbf{v})| ∣ supp ( v ) ∣ v 1 , … , v n \mathbf{v}_1,\ldots,\mathbf{v}_n v 1 , … , v n ⟨ v 1 , … , v n ⟩ \langle\mathbf{v}_1,\ldots,\mathbf{v}_n\rangle ⟨ v 1 , … , v n ⟩ M M M ⟨ M ⟩ \langle M\rangle ⟨ M ⟩
The observations are generated by independent random columns v 1 , v 2 , … ∈ F k \mathbf{v}_1,\mathbf{v}_2,\ldots\in\mathbb{F}^{k} v 1 , v 2 , … ∈ F k P k P_k P k [ k ] [k] [ k ] degree distribution , and a probability distribution μ \mu μ F ∗ \mathbb{F}^{*} F ∗ v j \mathbf{v}_j v j w w w P k P_k P k S ⊆ [ k ] S \subseteq[k] S ⊆ [ k ] w w w v j \mathbf{v}_j v j S S S μ \mu μ ∣ F ∣ > 2 |\mathbb{F}|>2 ∣ F ∣ > 2
For F = F 2 \mathbb{F}=\mathbb{F}_2 F = F 2 1 1 1 v j \mathbf{v}_j v j [24 ] , a binary k × n k\times n k × n G G G fully symmetric if, for every w ∈ [ k ] w\in[k] w ∈ [ k ] w w w G G G [24 ] , a uniformly sampled column of such a matrix has weight w w w G G G w w w G G G F = F 2 \mathbb{F}=\mathbb{F}_2 F = F 2 P k P_k P k G G G
Let x ∈ F k \mathbf{x}\in\mathbb{F}^k x ∈ F k j j j x T v j \mathbf{x}^{\mathsf{T}}\mathbf{v}_j x T v j n n n x T M k ( n ) \mathbf{x}^{\mathsf{T}}M_k(n) x T M k ( n ) M k ( n ) = [ v 1 ⋯ v n ] M_k(n)=[\mathbf{v}_1\ \cdots\ \mathbf{v}_n] M k ( n ) = [ v 1 ⋯ v n ] k × n k\times n k × n n n n ⟨ M k ( 0 ) ⟩ = { 0 } \langle M_k(0)\rangle=\{\mathbf{0}\} ⟨ M k ( 0 )⟩ = { 0 } x i x_i x i x T M k ( n ) \mathbf{x}^{\mathsf{T}}M_k(n) x T M k ( n ) x ∈ F k \mathbf{x}\in\mathbb{F}^k x ∈ F k e i ∈ ⟨ M k ( n ) ⟩ \mathbf{e}_i\in\langle M_k(n)\rangle e i ∈ ⟨ M k ( n )⟩ e i = M k ( n ) ⋅ a \mathbf{e}_i=M_k(n)\cdot\mathbf{a} e i = M k ( n ) ⋅ a x i = x T ⋅ M k ( n ) ⋅ a x_i=\mathbf{x}^{\mathsf{T}}\cdot M_k(n)\cdot\mathbf{a} x i = x T ⋅ M k ( n ) ⋅ a z ∈ F k \mathbf{z}\in\mathbb{F}^k z ∈ F k z i ≠ 0 z_i\ne0 z i = 0 z T ⋅ M k ( n ) = 0 \mathbf{z}^{\mathsf{T}}\cdot M_k(n)=\mathbf{0} z T ⋅ M k ( n ) = 0 x \mathbf{x} x x + z \mathbf{x}+\mathbf{z} x + z ( x + z ) i = x i + z i ≠ x i (\mathbf{x}+\mathbf{z})_i=x_i+z_i\ne x_i ( x + z ) i = x i + z i = x i recovery time of the i i i
τ i = min { n ≥ 0 : e i ∈ ⟨ M k ( n ) ⟩ } , (1) \tau_i=\min\{n\ge0:\mathbf{e}_i\in\langle M_k(n)\rangle\}, \tag*{(1)} τ i = min { n ≥ 0 : e i ∈ ⟨ M k ( n )⟩} , (1) with min ∅ = ∞ \min\varnothing=\infty min ∅ = ∞
Since the distribution of each column is invariant under permutations of the coordinates, the distribution of τ i \tau_i τ i i i i normalized expected recovery time E [ τ i ] / k \mathbb{E}[\tau_i]/k E [ τ i ] / k α ≥ 0 \alpha\ge0 α ≥ 0
U k ( α ) = P { e i ∉ ⟨ M k ( ⌊ α k ⌋ ) ⟩ } U_k(\alpha)=\mathbb{P}\{\mathbf{e}_i\notin\langle M_k(\lfloor\alpha k\rfloor)\rangle\} U k ( α ) = P { e i ∈ / ⟨ M k (⌊ α k ⌋)⟩} be the probability that the i i i ⌊ α k ⌋ \lfloor\alpha k\rfloor ⌊ α k ⌋ P k P_k P k μ \mu μ τ i \tau_i τ i P { τ i > α k } = P { τ i > ⌊ α k ⌋ } = U k ( α ) \mathbb{P}\{\tau_i>\alpha k\}=\mathbb{P}\{\tau_i>\lfloor\alpha k\rfloor\}=U_k(\alpha) P { τ i > α k } = P { τ i > ⌊ α k ⌋} = U k ( α )
E [ τ i ] k = ∫ 0 ∞ P { τ i > α k } d α = ∫ 0 ∞ U k ( α ) d α . (2) \frac{\mathbb{E}[\tau_i]}{k}=\int_0^\infty\mathbb{P}\{\tau_i>\alpha k\}\,d\alpha=\int_0^\infty U_k(\alpha)\,d\alpha. \tag*{(2)} k E [ τ i ] = ∫ 0 ∞ P { τ i > α k } d α = ∫ 0 ∞ U k ( α ) d α . (2) Theorem 1. Let F \mathbb{F} F μ \mu μ F \mathbb{F} F W W W ( P k ) (P_k) ( P k ) W W W P k ( w ) = 0 P_k(w)=0 P k ( w ) = 0 w > W w>W w > W
lim inf k → ∞ E [ τ i ] k ≥ π 4 . (3) \liminf_{k\to\infty}\frac{\mathbb{E}[\tau_i]}{k}\ge\frac{\pi}{4}. \tag*{(3)} k → ∞ lim inf k E [ τ i ] ≥ 4 π . (3) For F = F 2 \mathbb{F}=\mathbb{F}_2 F = F 2 W W W x i x_i x i [24 ] , which was proved for the peeling decoder.
The proof has two parts. In Section III, we bound U k ( α ) U_k(\alpha) U k ( α ) k → ∞ k\to\infty k → ∞ π / 4 \pi/4 π /4 P = ( p 1 , … , p W ) P=(p_1,\ldots,p_W) P = ( p 1 , … , p W ) [ W ] [W] [ W ] P ( z ) P(z) P ( z ) ( P k ) (P_k) ( P k )
A Lower Bound on the Probability of Non-Recovery
Throughout this section and Section IV, except in the proof of Theorem 1, the degree distribution is fixed. That is, P k = P P_k=P P k = P k ≥ W k\ge W k ≥ W P = ( p 1 , … , p W ) P=(p_1,\ldots,p_W) P = ( p 1 , … , p W ) [ W ] [W] [ W ] P P P
P ( z ) = ∑ w = 1 W p w z w , z ∈ [ 0 , 1 ] , P(z)=\sum_{w=1}^{W}p_w z^w,\qquad z\in[0,1], P ( z ) = w = 1 ∑ W p w z w , z ∈ [ 0 , 1 ] , and denote its derivative by P ′ ( z ) = ∑ w = 1 W w p w z w − 1 P'(z)=\sum_{w=1}^{W}wp_wz^{w-1} P ′ ( z ) = ∑ w = 1 W w p w z w − 1 P ( 0 ) = 0 P(0)=0 P ( 0 ) = 0 P ′ ( 1 ) = 1 P'(1)=1 P ′ ( 1 ) = 1
Our lower bound on U k ( α ) U_k(\alpha) U k ( α ) M k ( ⌊ α k ⌋ ) M_k(\lfloor\alpha k\rfloor) M k (⌊ α k ⌋) α , β ≥ 0 \alpha,\beta\ge0 α , β ≥ 0 N 1 , … , N k N_1,\ldots,N_k N 1 , … , N k β \beta β M k ( ⌊ α k ⌋ ) M_k(\lfloor\alpha k\rfloor) M k (⌊ α k ⌋) S k ( β ) S_k(\beta) S k ( β ) k × ( N 1 + ⋯ + N k ) k\times(N_1+\cdots+N_k) k × ( N 1 + ⋯ + N k ) N j N_j N j e j \mathbf{e}_j e j j ∈ [ k ] j\in[k] j ∈ [ k ] singleton columns , and to M ~ k ( α , β ) = [ M k ( ⌊ α k ⌋ ) S k ( β ) ] \widetilde{M}_k(\alpha,\beta)=[M_k(\lfloor\alpha k\rfloor)\ \ S_k(\beta)] M k ( α , β ) = [ M k (⌊ α k ⌋) S k ( β )] augmented matrix . Define
R k ( α , β ) = 1 k E [ rank M ~ k ( α , β ) ] . R_k(\alpha,\beta)=\frac{1}{k}\mathbb{E}[\operatorname{rank}\widetilde{M}_k(\alpha,\beta)]. R k ( α , β ) = k 1 E [ rank M k ( α , β )] . In particular, R k ( α , 0 ) = 1 k E [ rank M k ( ⌊ α k ⌋ ) ] R_k(\alpha,0)=\frac{1}{k}\mathbb{E}[\operatorname{rank}M_k(\lfloor\alpha k\rfloor)] R k ( α , 0 ) = k 1 E [ rank M k (⌊ α k ⌋)] e j \mathbf{e}_j e j { N j ≥ 1 } \{N_j\ge1\} { N j ≥ 1 } 1 − e − β 1-e^{-\beta} 1 − e − β
Lemma 2. For every α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0
U k ( α ) ≥ R k ( α , β ) − R k ( α , 0 ) 1 − e − β . (4) U_k(\alpha)\ge\frac{R_k(\alpha,\beta)-R_k(\alpha,0)}{1-e^{-\beta}}. \tag*{(4)} U k ( α ) ≥ 1 − e − β R k ( α , β ) − R k ( α , 0 ) . (4) Proof. Write M = M k ( ⌊ α k ⌋ ) M=M_k(\lfloor\alpha k\rfloor) M = M k (⌊ α k ⌋) J = { j ∈ [ k ] : N j ≥ 1 } J=\{j\in[k]:N_j\ge1\} J = { j ∈ [ k ] : N j ≥ 1 } e j \mathbf{e}_j e j e j ∈ ⟨ M ⟩ \mathbf{e}_j\in\langle M\rangle e j ∈ ⟨ M ⟩ M M M ∣ { j ∈ J : e j ∉ ⟨ M ⟩ } ∣ |\{j\in J:\mathbf{e}_j\notin\langle M\rangle\}| ∣ { j ∈ J : e j ∈ / ⟨ M ⟩} ∣ J J J M M M j ∈ [ k ] j\in[k] j ∈ [ k ] J J J 1 − e − β 1-e^{-\beta} 1 − e − β
k ( R k ( α , β ) − R k ( α , 0 ) ) = E [ rank M ~ k ( α , β ) − rank M ] ≤ E [ ∑ j = 1 k 1 { j ∈ J } ⋅ 1 { e j ∉ ⟨ M ⟩ } ] = ∑ j = 1 k P { j ∈ J } ⋅ P { e j ∉ ⟨ M ⟩ } = ( 1 − e − β ) k U k ( α ) . \begin{aligned}
k\bigl(R_k(\alpha,\beta)-R_k(\alpha,0)\bigr)
=\mathbb{E}\bigl[\operatorname{rank}\widetilde{M}_k(\alpha,\beta)-\operatorname{rank}M\bigr] \\
&\le\mathbb{E}\left[\sum_{j=1}^{k}\mathbf{1}_{\{j\in J\}}\cdot\mathbf{1}_{\{\mathbf{e}_j\notin\langle M\rangle\}}\right] \\
&=\sum_{j=1}^{k}\mathbb{P}\{j\in J\}\cdot\mathbb{P}\{\mathbf{e}_j\notin\langle M\rangle\} \\
&=(1-e^{-\beta})\,kU_k(\alpha).
\end{aligned} k ( R k ( α , β ) − R k ( α , 0 ) ) = E [ rank M k ( α , β ) − rank M ] ≤ E [ j = 1 ∑ k 1 { j ∈ J } ⋅ 1 { e j ∈ / ⟨ M ⟩} ] = j = 1 ∑ k P { j ∈ J } ⋅ P { e j ∈ / ⟨ M ⟩} = ( 1 − e − β ) k U k ( α ) . ♀♀♀♀♀♀ For z ∈ [ 0 , 1 ] z \in[0,1] z ∈ [ 0 , 1 ] α , β ≥ 0 \alpha,\beta\ge0 α , β ≥ 0
H ( z ) = 1 − P ( z ) − ( 1 − z ) P ′ ( z ) , (5) H(z)=1-P(z)-(1-z)P'(z), \tag*{(5)} H ( z ) = 1 − P ( z ) − ( 1 − z ) P ′ ( z ) , (5) Φ α , β ( z ) = e − β − α P ′ ( z ) − α H ( z ) , (6) \Phi_{\alpha,\beta}(z)=e^{-\beta-\alpha P'(z)}-\alpha H(z), \tag*{(6)} Φ α , β ( z ) = e − β − α P ′ ( z ) − α H ( z ) , (6) R P ( α , β ) = 1 − max 0 ≤ z ≤ 1 Φ α , β ( z ) . (7) R_P(\alpha,\beta)=1-\max_{0\le z\le1}\Phi_{\alpha,\beta}(z). \tag*{(7)} R P ( α , β ) = 1 − 0 ≤ z ≤ 1 max Φ α , β ( z ) . (7) We show that R k ( α , β ) → R P ( α , β ) R_k(\alpha,\beta)\to R_P(\alpha,\beta) R k ( α , β ) → R P ( α , β ) [25 ] , which holds over every field and for every distribution of the nonzero entries. This formula applies to random sparse matrices whose support is generated differently from our model. In our model, each column chooses its support independently, and the number of nonzero entries in each row is determined by these choices. In [25 ] , one first fixes the number of nonzero entries in every row and every column, and then chooses the support uniformly at random among all patterns with these row and column counts.
Specifically, for α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0 B k B_k B k k × N k\times N k × N F \mathbb{F} F N ∼ Poisson ( ( α + β ) k ) N\sim\operatorname{Poisson}((\alpha+\beta)k) N ∼ Poisson (( α + β ) k ) j ∈ [ N ] j\in[N] j ∈ [ N ] w j w_j w j
P { w j = 1 } = β + α p 1 α + β and P { w j = w } = α p w α + β , (8) \mathbb{P}\{w_j=1\}=\frac{\beta+\alpha p_1}{\alpha+\beta}
\quad\text{and}\quad
\mathbb{P}\{w_j=w\}=\frac{\alpha p_w}{\alpha+\beta}, \tag*{(8)} P { w j = 1 } = α + β β + α p 1 and P { w j = w } = α + β α p w , (8) for any 2 ≤ w ≤ W 2\le w\le W 2 ≤ w ≤ W i ∈ [ k ] i\in[k] i ∈ [ k ] d i d_i d i Poisson ( α P ′ ( 1 ) + β ) \operatorname{Poisson}(\alpha P'(1)+\beta) Poisson ( α P ′ ( 1 ) + β ) d 1 + ⋯ + d k ≠ w 1 + ⋯ + w N d_1+\cdots+d_k\ne w_1+\cdots+w_N d 1 + ⋯ + d k = w 1 + ⋯ + w N k × N k\times N k × N d i d_i d i i i i w j w_j w j j j j i , j i,j i , j B k B_k B k μ \mu μ
Claim 3. For fixed α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0 k → ∞ k\to\infty k → ∞ M k ( α , β ) M_k(\alpha,\beta) M k ( α , β ) Poisson ( α P ′ ( 1 ) + β ) \operatorname{Poisson}(\alpha P'(1)+\beta) Poisson ( α P ′ ( 1 ) + β )
Proof. The number of original columns of weight w w w k k k α p w \alpha p_w α p w k k k β \beta β k k k α + β > 0 \alpha+\beta>0 α + β > 0
Each original column independently has a nonzero entry in a fixed row with probability ∑ w p w w / k = P ′ ( 1 ) / k \sum_w p_w w/k=P'(1)/k ∑ w p w w / k = P ′ ( 1 ) / k ⌊ α k ⌋ \lfloor\alpha k\rfloor ⌊ α k ⌋ P ′ ( 1 ) / k P'(1)/k P ′ ( 1 ) / k Poisson ( α P ′ ( 1 ) ) \operatorname{Poisson}(\alpha P'(1)) Poisson ( α P ′ ( 1 )) Poisson ( β ) \operatorname{Poisson}(\beta) Poisson ( β )
The dependence between row counts and the conditioning in B k B_k B k
Theorem 4 ([25 Theorem 1.1] ). For every field F \mathbb{F} F μ \mu μ F ∗ \mathbb{F}^{*} F ∗ α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0
rank B k k ⟶ R P ( α , β ) in probability as k → ∞ . \frac{\operatorname{rank} B_k}{k}\longrightarrow R_P(\alpha,\beta)\quad\text{in probability as }k\to\infty. k rank B k ⟶ R P ( α , β ) in probability as k → ∞. Theorem 4 is [25 Theorem 1.1] applied to the transpose of B k B_k B k β > 0 \beta>0 β > 0 [25 Section 1.2, footnote 2] .
Lemma 5. For every fixed α , β ≥ 0 \alpha,\beta\ge0 α , β ≥ 0
lim k → ∞ R k ( α , β ) = R P ( α , β ) . (9) \lim_{k\to\infty}R_k(\alpha,\beta)=R_P(\alpha,\beta). \tag*{(9)} k → ∞ lim R k ( α , β ) = R P ( α , β ) . (9) Proof. Assume first that β > 0 \beta>0 β > 0 B k B_k B k M k M_k M k B k B_k B k β = 0 \beta=0 β = 0
First, let M k ′ ( α , β ) M'_k(\alpha,\beta) M k ′ ( α , β ) M k ( α , β ) M_k(\alpha,\beta) M k ( α , β ) M k M_k M k M k M_k M k Poisson ( α k ) \operatorname{Poisson}(\alpha k) Poisson ( α k ) ⌊ α k ⌋ \lfloor\alpha k\rfloor ⌊ α k ⌋ M k ( α , β ) M_k(\alpha,\beta) M k ( α , β ) M k ′ ( α , β ) M'_k(\alpha,\beta) M k ′ ( α , β )
E ∣ X − ⌊ α k ⌋ ∣ ≤ E ∣ X − α k ∣ + 1 ≤ α k + 1 , (10) \mathbb{E}|X-\lfloor\alpha k\rfloor|\le\mathbb{E}|X-\alpha k|+1\le\sqrt{\alpha k}+1, \tag*{(10)} E ∣ X − ⌊ α k ⌋ ∣ ≤ E ∣ X − α k ∣ + 1 ≤ α k + 1 , (10) where the last step follows from Cauchy–Schwarz and Var ( X ) = α k \operatorname{Var}(X)=\alpha k Var ( X ) = α k
Now let A k A_k A k Poisson ( ( α + β ) k ) \operatorname{Poisson}((\alpha+\beta)k) Poisson (( α + β ) k ) μ \mu μ A k A_k A k α / ( α + β ) \alpha/(\alpha+\beta) α / ( α + β ) P P P ( β + α p 1 ) / ( α + β ) (\beta+\alpha p_1)/(\alpha+\beta) ( β + α p 1 ) / ( α + β ) w ≥ 2 w\ge2 w ≥ 2 α p w / ( α + β ) \alpha p_w/(\alpha+\beta) α p w / ( α + β ) A k A_k A k M k ′ ( α , β ) M'_k(\alpha,\beta) M k ′ ( α , β ) μ \mu μ
By the splitting property of the Poisson distribution if a Poisson ( λ ) \operatorname{Poisson}(\lambda) Poisson ( λ ) t t t π t \pi_t π t t t t Poisson ( λ π t ) \operatorname{Poisson}(\lambda\pi_t) Poisson ( λ π t ) A k A_k A k Poisson ( ( α + β ) k ) \operatorname{Poisson}((\alpha+\beta)k) Poisson (( α + β ) k ) α / ( α + β ) \alpha/(\alpha+\beta) α / ( α + β ) j j j β / ( ( α + β ) k ) \beta/((\alpha+\beta)k) β / (( α + β ) k ) j ∈ [ k ] j\in[k] j ∈ [ k ] k + 1 k+1 k + 1 Poisson ( α k ) \operatorname{Poisson}(\alpha k) Poisson ( α k ) j ∈ [ k ] j\in[k] j ∈ [ k ] Poisson ( β ) \operatorname{Poisson}(\beta) Poisson ( β ) A k A_k A k M k ′ ( α , β ) M'_k(\alpha,\beta) M k ′ ( α , β )
∣ R k ( α , β ) − 1 k E [ rank A k ] ∣ ≤ α k + 1 k ⟶ 0. \left|R_k(\alpha,\beta)-\frac{1}{k}\mathbb{E}[\operatorname{rank} A_k]\right|
\le\frac{\sqrt{\alpha k}+1}{k}\longrightarrow0. R k ( α , β ) − k 1 E [ rank A k ] ≤ k α k + 1 ⟶ 0. Therefore, it suffices to show that 1 k E [ rank A k ] → R P ( α , β ) \frac{1}{k}\mathbb{E}[\operatorname{rank} A_k]\to R_P(\alpha,\beta) k 1 E [ rank A k ] → R P ( α , β ) 0 ≤ rank A k / k ≤ 1 0\le\operatorname{rank} A_k/k\le1 0 ≤ rank A k / k ≤ 1 rank A k / k → R P ( α , β ) \operatorname{rank} A_k/k\to R_P(\alpha,\beta) rank A k / k → R P ( α , β )
Second, A k A_k A k B k B_k B k A k A_k A k B k B_k B k degree data . Given the degree data, A k A_k A k B k B_k B k B k B_k B k A k A_k A k ∏ j = 1 N ( k w j ) − 1 \prod_{j=1}^{N}\binom{k}{w_j}^{-1} ∏ j = 1 N ( w j k ) − 1 μ \mu μ rank A k / k → R P ( α , β ) \operatorname{rank} A_k/k\to R_P(\alpha,\beta) rank A k / k → R P ( α , β )
Finally, let β = 0 \beta=0 β = 0 β = 0 \beta=0 β = 0 β ′ > 0 \beta'>0 β ′ > 0 R k R_k R k R P R_P R P β ′ > 0 \beta'>0 β ′ > 0
First, appending the singleton columns does not decrease the rank, and increases it by at most the number of coordinates j j j N j ≥ 1 N_j\ge1 N j ≥ 1 k ( 1 − e − β ′ ) k(1-e^{-\beta'}) k ( 1 − e − β ′ )
0 ≤ R k ( α , β ′ ) − R k ( α , 0 ) ≤ 1 − e − β ′ . 0\le R_k(\alpha,\beta')-R_k(\alpha,0)\le1-e^{-\beta'}. 0 ≤ R k ( α , β ′ ) − R k ( α , 0 ) ≤ 1 − e − β ′ . Second, for every z ∈ [ 0 , 1 ] z\in[0,1] z ∈ [ 0 , 1 ]
Φ α , 0 ( z ) − Φ α , β ′ ( z ) = ( 1 − e − β ′ ) e − α P ′ ( z ) , \Phi_{\alpha,0}(z)-\Phi_{\alpha,\beta'}(z)=(1-e^{-\beta'})e^{-\alpha P'(z)}, Φ α , 0 ( z ) − Φ α , β ′ ( z ) = ( 1 − e − β ′ ) e − α P ′ ( z ) , which lies in [ 0 , 1 − e − β ′ ] [0,1-e^{-\beta'}] [ 0 , 1 − e − β ′ ]
0 ≤ R P ( α , β ′ ) − R P ( α , 0 ) ≤ 1 − e − β ′ . 0\le R_P(\alpha,\beta')-R_P(\alpha,0)\le1-e^{-\beta'}. 0 ≤ R P ( α , β ′ ) − R P ( α , 0 ) ≤ 1 − e − β ′ . Combining these two bounds with the triangle inequality,
∣ R k ( α , 0 ) − R P ( α , 0 ) ∣ ≤ ∣ R k ( α , 0 ) − R k ( α , β ′ ) ∣ + ∣ R k ( α , β ′ ) − R P ( α , β ′ ) ∣ + ∣ R P ( α , β ′ ) − R P ( α , 0 ) ∣ ≤ ∣ R k ( α , β ′ ) − R P ( α , β ′ ) ∣ + 2 ( 1 − e − β ′ ) . \begin{aligned}
|R_k(\alpha,0)-R_P(\alpha,0)|
&\le|R_k(\alpha,0)-R_k(\alpha,\beta')|\\
&\quad+|R_k(\alpha,\beta')-R_P(\alpha,\beta')|\\
&\quad+|R_P(\alpha,\beta')-R_P(\alpha,0)|\\
&\le|R_k(\alpha,\beta')-R_P(\alpha,\beta')|+2(1-e^{-\beta'}).
\end{aligned} ∣ R k ( α , 0 ) − R P ( α , 0 ) ∣ ≤ ∣ R k ( α , 0 ) − R k ( α , β ′ ) ∣ + ∣ R k ( α , β ′ ) − R P ( α , β ′ ) ∣ + ∣ R P ( α , β ′ ) − R P ( α , 0 ) ∣ ≤ ∣ R k ( α , β ′ ) − R P ( α , β ′ ) ∣ + 2 ( 1 − e − β ′ ) . By the case β > 0 \beta>0 β > 0 k → ∞ k\to\infty k → ∞ lim sup k → ∞ ∣ R k ( α , 0 ) − R P ( α , 0 ) ∣ ≤ 2 ( 1 − e − β ′ ) \limsup_{k\to\infty}|R_k(\alpha,0)-R_P(\alpha,0)|\le2(1-e^{-\beta'}) lim sup k → ∞ ∣ R k ( α , 0 ) − R P ( α , 0 ) ∣ ≤ 2 ( 1 − e − β ′ ) β ′ ↓ 0 \beta'\downarrow0 β ′ ↓ 0
Let Φ α = Φ α , 0 \Phi_\alpha=\Phi_{\alpha,0} Φ α = Φ α , 0
A P ( α ) = a r g m a x z ∈ [ 0 , 1 ] Φ α ( z ) , \mathcal{A}_P(\alpha)=\mathop{\rm arg\,max}_{z\in[0,1]}\Phi_\alpha(z), A P ( α ) = arg max z ∈ [ 0 , 1 ] Φ α ( z ) , U P ( α ) = min z ∈ A P ( α ) e − α P ′ ( z ) . (11) \mathcal{U}_P(\alpha)=\min_{z\in\mathcal{A}_P(\alpha)}e^{-\alpha P'(z)}. \tag*{(11)} U P ( α ) = z ∈ A P ( α ) min e − α P ′ ( z ) . (11) Lemma 6. For every fixed α ≥ 0 \alpha\ge0 α ≥ 0
lim inf k → ∞ U k ( α ) ≥ U P ( α ) . (12) \liminf_{k\to\infty}U_k(\alpha)\ge\mathcal{U}_P(\alpha). \tag*{(12)} k → ∞ lim inf U k ( α ) ≥ U P ( α ) . (12) The proof is given in Appendix A. It applies Lemmas 2 and 5 for a fixed β > 0 \beta>0 β > 0 β ↓ 0 \beta\downarrow0 β ↓ 0 Φ α , β \Phi_{\alpha,\beta} Φ α , β Φ α \Phi_\alpha Φ α
The Integral Inequality
By Lemma 6, the limit inferior of U k ( α ) U_k(\alpha) U k ( α ) U P ( α ) . \mathcal{U}_P(\alpha). U P ( α ) . U P \mathcal{U}_P U P π / 4 \pi/4 π /4
Proposition 7. For every degree distribution P P P W W W
∫ 0 ∞ U P ( α ) d α ≥ π 4 . (13) \int_{0}^{\infty}\mathcal{U}_P(\alpha)\,d\alpha\ge\frac{\pi}{4}. \tag*{(13)} ∫ 0 ∞ U P ( α ) d α ≥ 4 π . (13) If p 1 = 1 p_1=1 p 1 = 1 p 1 < 1 p_1<1 p 1 < 1 U P ( α ) \mathcal{U}_P(\alpha) U P ( α ) Φ α \Phi_\alpha Φ α U P \mathcal{U}_P U P α \alpha α α \alpha α p 1 < 1 p_1<1 p 1 < 1
For α > 0 \alpha>0 α > 0
ζ ( α ) = max A P ( α ) \zeta(\alpha)=\max\mathcal{A}_P(\alpha) ζ ( α ) = max A P ( α ) be the largest maximizer of Φ α \Phi_\alpha Φ α [ 0 , 1 ] [0,1] [ 0 , 1 ] A P ( α ) \mathcal{A}_P(\alpha) A P ( α ) Φ α \Phi_\alpha Φ α U P ( α ) \mathcal{U}_P(\alpha) U P ( α ) ζ ( α ) \zeta(\alpha) ζ ( α )
Lemma 8. Let p 1 < 1 p_1<1 p 1 < 1 α > 0 \alpha>0 α > 0 z z z Φ α \Phi_\alpha Φ α z < 1 z<1 z < 1 α P ′ ( z ) = − log ( 1 − z ) \alpha P'(z)=-\log(1-z) α P ′ ( z ) = − log ( 1 − z )
U P ( α ) = 1 − ζ ( α ) . (14) \mathcal{U}_P(\alpha)=1-\zeta(\alpha). \tag*{(14)} U P ( α ) = 1 − ζ ( α ) . (14) Proof sketch. Assume for this sketch that the maximizers lie in ( 0 , 1 ) (0,1) ( 0 , 1 ) H ′ ( z ) = − ( 1 − z ) P ′ ′ ( z ) H'(z)=-(1-z)P''(z) H ′ ( z ) = − ( 1 − z ) P ′′ ( z )
Φ α ′ ( z ) = α P ′ ′ ( z ) ( 1 − z − e − α P ′ ( z ) ) . \Phi_\alpha'(z)=\alpha P''(z)(1-z-e^{-\alpha P'(z)}). Φ α ′ ( z ) = α P ′′ ( z ) ( 1 − z − e − α P ′ ( z ) ) . Because p 1 < 1 p_1<1 p 1 < 1 P ′ ′ ( z ) > 0 P''(z)>0 P ′′ ( z ) > 0 0 < z < 1 0<z<1 0 < z < 1 z ∗ z^* z ∗ Φ α ′ ( z ∗ ) = 0 \Phi_\alpha'(z^*)=0 Φ α ′ ( z ∗ ) = 0
1 − z ∗ = e − α P ′ ( z ∗ ) , α P ′ ( z ∗ ) = − log ( 1 − z ∗ ) . 1-z^*=e^{-\alpha P'(z^*)},\qquad\alpha P'(z^*)=-\log(1-z^*). 1 − z ∗ = e − α P ′ ( z ∗ ) , α P ′ ( z ∗ ) = − log ( 1 − z ∗ ) . Substituting this identity into the definition of U P ( α ) \mathcal{U}_P(\alpha) U P ( α )
U P ( α ) = min z ∈ A P ( α ) e − α P ′ ( z ) = min z ∈ A P ( α ) ( 1 − z ) = 1 − ζ ( α ) , \begin{aligned}
\mathcal{U}_P(\alpha)
&=\min_{z\in\mathcal{A}_P(\alpha)}e^{-\alpha P'(z)}\\
&=\min_{z\in\mathcal{A}_P(\alpha)}(1-z)=1-\zeta(\alpha),
\end{aligned} U P ( α ) = z ∈ A P ( α ) min e − α P ′ ( z ) = z ∈ A P ( α ) min ( 1 − z ) = 1 − ζ ( α ) , since ζ ( α ) \zeta(\alpha) ζ ( α )
By (14), the integral in (13) depends only on the function ζ \zeta ζ ζ \zeta ζ
Lemma 9. Let p 1 < 1 p_1 < 1 p 1 < 1 ζ \zeta ζ ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) ζ ( α ) → 0 \zeta(\alpha) \to0 ζ ( α ) → 0 α ↓ 0 \alpha\downarrow0 α ↓ 0 ζ ( α ) → 1 \zeta(\alpha) \to1 ζ ( α ) → 1 α → ∞ \alpha\to\infty α → ∞
By Lemma 9, ζ \zeta ζ ζ \zeta ζ 0 < z < 1 0 < z < 1 0 < z < 1
σ ( z ) = inf { α > 0 : ζ ( α ) ≥ z } \sigma(z) = \inf\{\alpha> 0 : \zeta(\alpha) \ge z\} σ ( z ) = inf { α > 0 : ζ ( α ) ≥ z } be the generalized inverse of ζ \zeta ζ α \alpha α ζ \zeta ζ z z z σ ( z ) \sigma(z) σ ( z ) z ∈ ( 0 , 1 ) z \in(0,1) z ∈ ( 0 , 1 ) U P U_P U P σ \sigma σ ζ \zeta ζ α P ′ ( z ) = − log ( 1 − z ) \alpha P'(z) = -\log(1-z) α P ′ ( z ) = − log ( 1 − z ) ζ \zeta ζ Φ α \Phi_\alpha Φ α
Lemma 10. Let p 1 < 1 p_1 < 1 p 1 < 1
∫ 0 1 − log ( 1 − z ) σ ( z ) d z = 1. (15) \int_0^1 \frac{-\log(1-z)}{\sigma(z)}\,\mathrm{d}z = 1. \tag*{(15)} ∫ 0 1 σ ( z ) − log ( 1 − z ) d z = 1. (15) The proof of Lemma 10 is given in Appendix B. We can now prove Proposition 7.
Proof of Proposition 7. If p 1 = 1 p_1 = 1 p 1 = 1 P ( z ) = z P(z) = z P ( z ) = z U P ( α ) = e − α U_P(\alpha) = e^{-\alpha} U P ( α ) = e − α
∫ 0 ∞ U P ( α ) d α = ∫ 0 ∞ e − α d α = 1 > π 4 . \int_0^\infty U_P(\alpha)\,\mathrm{d}\alpha= \int_0^\infty e^{-\alpha}\,\mathrm{d}\alpha= 1 > \frac{\pi}{4}. ∫ 0 ∞ U P ( α ) d α = ∫ 0 ∞ e − α d α = 1 > 4 π . Now assume p 1 < 1 p_1 < 1 p 1 < 1 U P U_P U P σ \sigma σ x ∈ [ 0 , 1 ] x \in[0,1] x ∈ [ 0 , 1 ] 1 { x < z } \mathbf{1}\{x < z\} 1 { x < z } z ∈ ( x , 1 ] z \in(x,1] z ∈ ( x , 1 ]
∫ 0 1 1 { x < z } d z = 1 − x . \int_0^1 \mathbf{1}\{x < z\}\,\mathrm{d}z = 1-x. ∫ 0 1 1 { x < z } d z = 1 − x . We apply this with x = ζ ( α ) x = \zeta(\alpha) x = ζ ( α ) ζ \zeta ζ { α > 0 : ζ ( α ) < z } = ( 0 , σ ( z ) ) \{\alpha> 0 : \zeta(\alpha) < z\} = (0,\sigma(z)) { α > 0 : ζ ( α ) < z } = ( 0 , σ ( z )) z ∈ ( 0 , 1 ) z \in(0,1) z ∈ ( 0 , 1 )
∫ 0 ∞ U P ( α ) d α = ∫ 0 1 ∫ 0 ∞ 1 { ζ ( α ) < z } d α d z = ∫ 0 1 σ ( z ) d z . (16) \int_0^\infty U_P(\alpha)\,\mathrm{d}\alpha
= \int_0^1 \int_0^\infty\mathbf{1}\{\zeta(\alpha) < z\}\,\mathrm{d}\alpha\,\mathrm{d}z
= \int_0^1 \sigma(z)\,\mathrm{d}z. \tag*{(16)} ∫ 0 ∞ U P ( α ) d α = ∫ 0 1 ∫ 0 ∞ 1 { ζ ( α ) < z } d α d z = ∫ 0 1 σ ( z ) d z . (16) If ∫ 0 1 σ ( z ) d z = ∞ \int_0^1 \sigma(z)\,\mathrm{d}z = \infty ∫ 0 1 σ ( z ) d z = ∞
− log ( 1 − z ) = σ ( z ) ⋅ − log ( 1 − z ) σ ( z ) \sqrt{-\log(1-z)} = \sqrt{\sigma(z)}\cdot\sqrt{\frac{-\log(1-z)}{\sigma(z)}} − log ( 1 − z ) = σ ( z ) ⋅ σ ( z ) − log ( 1 − z ) and apply the Cauchy–Schwarz inequality together with Lemma 10:
( ∫ 0 1 − log ( 1 − z ) d z ) 2 ≤ ( ∫ 0 1 σ ( z ) d z ) ( ∫ 0 1 − log ( 1 − z ) σ ( z ) d z ) = ∫ 0 1 σ ( z ) d z . \left(\int_0^1 \sqrt{-\log(1-z)}\,\mathrm{d}z\right)^2
\le\left(\int_0^1 \sigma(z)\,\mathrm{d}z\right)
\left(\int_0^1 \frac{-\log(1-z)}{\sigma(z)}\,\mathrm{d}z\right)
= \int_0^1 \sigma(z)\,\mathrm{d}z. ( ∫ 0 1 − log ( 1 − z ) d z ) 2 ≤ ( ∫ 0 1 σ ( z ) d z ) ( ∫ 0 1 σ ( z ) − log ( 1 − z ) d z ) = ∫ 0 1 σ ( z ) d z . Finally, the substitution t = − log ( 1 − z ) t=-\log(1-z) t = − log ( 1 − z ) d z = e − t d t \mathrm{d}z=e^{-t}\,\mathrm{d}t d z = e − t d t z ∈ ( 0 , 1 ) z\in(0,1) z ∈ ( 0 , 1 ) t ∈ ( 0 , ∞ ) t\in(0,\infty) t ∈ ( 0 , ∞ )
∫ 0 1 − log ( 1 − z ) d z = ∫ 0 ∞ t e − t d t = Γ ( 3 2 ) = π 2 , \int_0^1 \sqrt{-\log(1-z)}\,\mathrm{d}z
= \int_0^\infty\sqrt{t}e^{-t}\,\mathrm{d}t
= \Gamma\left(\frac{3}{2}\right)
= \frac{\sqrt{\pi}}{2}, ∫ 0 1 − log ( 1 − z ) d z = ∫ 0 ∞ t e − t d t = Γ ( 2 3 ) = 2 π , where Γ ( s ) = ∫ 0 ∞ t s − 1 e − t d t \Gamma(s)=\int_0^\infty t^{s-1}e^{-t}\,\mathrm{d}t Γ ( s ) = ∫ 0 ∞ t s − 1 e − t d t ∫ 0 ∞ U P ( α ) d α = ∫ 0 1 σ ( z ) d z ≥ π / 4 \int_0^\infty U_P(\alpha)\,\mathrm{d}\alpha=\int_0^1 \sigma(z)\,\mathrm{d}z\ge\pi/4 ∫ 0 ∞ U P ( α ) d α = ∫ 0 1 σ ( z ) d z ≥ π /4
Proof of Theorem 1. We first prove the theorem when the degree distribution does not depend on k k k
Let P k = P P_k=P P k = P k k k
E [ τ i ] k = ∫ 0 ∞ U k ( α ) d α . \frac{\mathbb{E}[\tau_i]}{k} = \int_0^\infty U_k(\alpha)\,\mathrm{d}\alpha. k E [ τ i ] = ∫ 0 ∞ U k ( α ) d α . Since U k ≥ 0 U_k \ge0 U k ≥ 0
lim inf k → ∞ E [ τ i ] k ≥ ∫ 0 ∞ lim inf k → ∞ U k ( α ) d α ≥ ∫ 0 ∞ U P ( α ) d α ≥ π 4 . \liminf_{k\to\infty}\frac{\mathbb{E}[\tau_i]}{k}
\ge\int_0^\infty\liminf_{k\to\infty}U_k(\alpha)\,\mathrm{d}\alpha
\ge\int_0^\infty U_P(\alpha)\,\mathrm{d}\alpha
\ge\frac{\pi}{4}. k → ∞ lim inf k E [ τ i ] ≥ ∫ 0 ∞ k → ∞ lim inf U k ( α ) d α ≥ ∫ 0 ∞ U P ( α ) d α ≥ 4 π . Now let ( P k ) (P_k) ( P k ) W W W L = lim inf k → ∞ E [ τ i ] / k L=\liminf_{k\to\infty}\mathbb{E}[\tau_i]/k L = lim inf k → ∞ E [ τ i ] / k L = ∞ L=\infty L = ∞ L < ∞ L<\infty L < ∞ k 1 < k 2 < ⋯ k_1<k_2<\cdots k 1 < k 2 < ⋯ E [ τ i ] / k j → L \mathbb{E}[\tau_i]/k_j\to L E [ τ i ] / k j → L P k P_k P k [ 0 , 1 ] W [0,1]^W [ 0 , 1 ] W P k j → P P_{k_j}\to P P k j → P P P P [ W ] [W] [ W ] E [ τ i ] / k \mathbb{E}[\tau_i]/k E [ τ i ] / k L L L lim inf U k ( α ) ≥ U P ( α ) \liminf U_k(\alpha)\ge U_P(\alpha) lim inf U k ( α ) ≥ U P ( α ) α ≥ 0 \alpha\ge0 α ≥ 0 L ≥ π / 4 L\ge\pi/4 L ≥ π /4 P P P
For a degree distribution Q Q Q R k ( Q ) ( α , β ) R_k^{(Q)}(\alpha,\beta) R k ( Q ) ( α , β ) R k ( α , β ) R_k(\alpha,\beta) R k ( α , β ) Q k Q_k Q k P k P_k P k P P P d T V ( P k , P ) \mathrm{d}_{\mathrm{TV}}(P_k,P) d TV ( P k , P ) ∣ α k ∣ |\alpha k| ∣ α k ∣ d T V ( P k , P ) \mathrm{d}_{\mathrm{TV}}(P_k,P) d TV ( P k , P )
∣ R k ( P k ) ( α , β ) − R k ( P ) ( α , β ) ∣ ≤ ∣ α k ∣ k d T V ( P k , P ) ≤ α d T V ( P k , P ) ⟶ 0. \left|R_k^{(P_k)}(\alpha,\beta)-R_k^{(P)}(\alpha,\beta)\right|
\le\frac{|\alpha k|}{k}\,\mathrm{d}_{\mathrm{TV}}(P_k,P)
\le\alpha\,\mathrm{d}_{\mathrm{TV}}(P_k,P)\longrightarrow0. R k ( P k ) ( α , β ) − R k ( P ) ( α , β ) ≤ k ∣ α k ∣ d TV ( P k , P ) ≤ α d TV ( P k , P ) ⟶ 0. Together with Lemma 5, applied to the fixed distribution P P P R k ( P k ) ( α , β ) → R P ( α , β ) R_k^{(P_k)}(\alpha,\beta)\to R_P(\alpha,\beta) R k ( P k ) ( α , β ) → R P ( α , β ) α , β ≥ 0 \alpha,\beta\ge0 α , β ≥ 0 k k k lim inf U k ( α ) ≥ U P ( α ) \liminf U_k(\alpha)\ge U_P(\alpha) lim inf U k ( α ) ≥ U P ( α )
The last Cauchy–Schwarz step in the proof of Proposition 7 is the same integral estimate used in [24 Lemma 5] . Here, the additional identity (27) ensures that (15) remains valid across levels skipped by jumps.
A Singleton–Pair Code Construction
Theorem 1 shows that no ensemble with bounded column weights has normalized expected recovery time asymptotically below π / 4 \pi/4 π /4 p 1 = s p_1=s p 1 = s p 2 = 1 − s p_2=1-s p 2 = 1 − s 0 < s < 1 0<s<1 0 < s < 1 P ( z ) = s z + ( 1 − s ) z 2 P(z)=sz+(1-s)z^2 P ( z ) = sz + ( 1 − s ) z 2 [24 ] , where the best choice of s s s
Asymptotic analysis
Throughout this subsection, P ( z ) = s z + ( 1 − s ) z 2 P(z)=sz+(1-s)z^2 P ( z ) = sz + ( 1 − s ) z 2 0 < s < 1 0<s<1 0 < s < 1 F \mathbb{F} F § 2 , and the coefficient distribution μ \mu μ G \mathcal{G} G [ k ] [k] [ k ] u u u v v v u u u v v v u u u u u u
Columns supported in different components of G \mathcal{G} G x i x_i x i i i i G \mathcal{G} G ( 1 , 2 , 0 , … , 0 ) T (1,2,0,\ldots,0)^{\mathsf T} ( 1 , 2 , 0 , … , 0 ) T ( 1 , 1 , 0 , … , 0 ) T (1,1,0,\ldots,0)^{\mathsf T} ( 1 , 1 , 0 , … , 0 ) T e 1 \mathbf e_1 e 1 e 2 \mathbf e_2 e 2 ( 1 , 1 , 0 , … , 0 ) T (1,1,0,\ldots,0)^{\mathsf T} ( 1 , 1 , 0 , … , 0 ) T
Lemma 11. Let H \mathcal H H G \mathcal G G
(i) If H \mathcal H H x i x_i x i i ∈ H i\in\mathcal H i ∈ H
(ii) If H \mathcal H H x i x_i x i i ∈ H i\in\mathcal H i ∈ H
Proof. For (i), let u ∈ H u\in\mathcal H u ∈ H u u u e u \mathbf e_u e u e u \mathbf e_u e u e w \mathbf e_w e w w w w v v v a e w + b e v a\mathbf e_w+b\mathbf e_v a e w + b e v a , b ≠ 0 a,b\ne0 a , b = 0 e v = b − 1 ( a e w − ( a e w + b e v ) ) \mathbf e_v=b^{-1}(a\mathbf e_w-(a\mathbf e_w+b\mathbf e_v)) e v = b − 1 ( a e w − ( a e w + b e v )) H \mathcal H H u u u e v \mathbf e_v e v v ∈ H v\in\mathcal H v ∈ H
For (ii), it suffices to find y ∈ F k \mathbf y\in\mathbb F^k y ∈ F k y T v j = 0 \mathbf y^{\mathsf T}\mathbf v_j=0 y T v j = 0 v j \mathbf v_j v j y i ≠ 0 y_i\ne0 y i = 0 i ∈ H i\in\mathcal H i ∈ H u \mathbf u u y T u = 0 \mathbf y^{\mathsf T}\mathbf u=0 y T u = 0 y T e i = y i ≠ 0 \mathbf y^{\mathsf T}\mathbf e_i=y_i\ne0 y T e i = y i = 0 e i \mathbf e_i e i
Choose a root r ∈ H r\in\mathcal H r ∈ H y r = 1 y_r=1 y r = 1 y v = 0 y_v=0 y v = 0 v ∉ H v\notin\mathcal H v ∈ / H v ∈ H v\in\mathcal H v ∈ H r r r w w w v v v a e w + b e v a\mathbf e_w+b\mathbf e_v a e w + b e v y v = − a y w / b y_v=-ay_w/b y v = − a y w / b a , b ≠ 0 a,b\ne0 a , b = 0 y v y_v y v v ∈ H v\in\mathcal H v ∈ H y T v j = 0 \mathbf y^{\mathsf T}\mathbf v_j=0 y T v j = 0 v j \mathbf v_j v j v j \mathbf v_j v j H \mathcal H H y \mathbf y y H \mathcal H H v j \mathbf v_j v j H \mathcal H H H \mathcal H H v j \mathbf v_j v j H \mathcal H H v j = a e w + b e v \mathbf v_j=a\mathbf e_w+b\mathbf e_v v j = a e w + b e v w w w v v v
y T v j = a y w + b y v = a y w − a y w = 0. \mathbf y^{\mathsf T}\mathbf v_j=ay_w+by_v=ay_w-ay_w=0. y T v j = a y w + b y v = a y w − a y w = 0. Proposition 12. Let P ( z ) = s z + ( 1 − s ) z 2 P(z)=sz+(1-s)z^2 P ( z ) = sz + ( 1 − s ) z 2 0 < s < 1 0<s<1 0 < s < 1 F \mathbb F F § 2 and every distribution μ \mu μ F ∗ \mathbb F^* F ∗
lim k → ∞ E [ τ i ] k = ∫ 0 1 − log u s + 2 ( 1 − s ) ( 1 − u ) d u . (17) \lim_{k\to\infty}\frac{\mathbb E[\tau_i]}{k}=\int_0^1\frac{-\log u}{s+2(1-s)(1-u)}\,du. \tag*{(17)} k → ∞ lim k E [ τ i ] = ∫ 0 1 s + 2 ( 1 − s ) ( 1 − u ) − log u d u . (17) Proof. Let α > 0 \alpha>0 α > 0 z z z Φ α \Phi_\alpha Φ α z < 1 z<1 z < 1 1 − z = e − α P ′ ( z ) 1-z=e^{-\alpha P'(z)} 1 − z = e − α P ′ ( z )
P ′ ( z ) = s + 2 ( 1 − s ) z , P'(z)=s+2(1-s)z, P ′ ( z ) = s + 2 ( 1 − s ) z , the number u = 1 − z u=1-z u = 1 − z
u = exp ( − α P ′ ( 1 − u ) ) = exp ( − α ( s + 2 ( 1 − s ) ( 1 − u ) ) ) . (18) u=\exp(-\alpha P'(1-u))=\exp(-\alpha(s+2(1-s)(1-u))). \tag*{(18)} u = exp ( − α P ′ ( 1 − u )) = exp ( − α ( s + 2 ( 1 − s ) ( 1 − u ))) . (18) Moreover, z ≠ 0 z\ne0 z = 0 z = 0 z=0 z = 0 1 = e − α P ′ ( 0 ) = e − α s < 1 1=e^{-\alpha P'(0)}=e^{-\alpha s}<1 1 = e − α P ′ ( 0 ) = e − α s < 1 u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 )
Taking logarithms, a number u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 ) log u + α ( s + 2 ( 1 − s ) ( 1 − u ) ) = 0 \log u+\alpha(s+2(1-s)(1-u))=0 log u + α ( s + 2 ( 1 − s ) ( 1 − u )) = 0 u u u log u \log u log u u u u − ∞ -\infty − ∞ u ↓ 0 u\downarrow0 u ↓ 0 α s > 0 \alpha s>0 α s > 0 u = 1 u=1 u = 1 u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 ) u u u u = 1 u=1 u = 1 ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) u s ( α ) u_s(\alpha) u s ( α ) z z z Φ α \Phi_\alpha Φ α u = 1 − z u=1-z u = 1 − z ( 0 , 1 ) , (0,1), ( 0 , 1 ) , Φ α \Phi_\alpha Φ α 1 − u s ( α ) 1-u_s(\alpha) 1 − u s ( α ) ζ ( α ) = 1 − u s ( α ) \zeta(\alpha)=1-u_s(\alpha) ζ ( α ) = 1 − u s ( α ) U P ( α ) = 1 − ζ ( α ) = u s ( α ) U_P(\alpha)=1-\zeta(\alpha)=u_s(\alpha) U P ( α ) = 1 − ζ ( α ) = u s ( α )
By (2), E [ τ i ] / k = ∫ 0 ∞ U k ( α ) d α \mathbb E[\tau_i]/k=\int_0^\infty U_k(\alpha)\,d\alpha E [ τ i ] / k = ∫ 0 ∞ U k ( α ) d α U k ≥ 0 U_k\ge0 U k ≥ 0
lim inf k → ∞ E [ τ i ] k ≥ ∫ 0 ∞ lim inf k → ∞ U k ( α ) d α ≥ ∫ 0 ∞ u s ( α ) d α . \liminf_{k\to\infty}\frac{\mathbb E[\tau_i]}{k}\ge\int_0^\infty\liminf_{k\to\infty}U_k(\alpha)\,d\alpha\ge\int_0^\infty u_s(\alpha)\,d\alpha. k → ∞ lim inf k E [ τ i ] ≥ ∫ 0 ∞ k → ∞ lim inf U k ( α ) d α ≥ ∫ 0 ∞ u s ( α ) d α . For the upper bound, we use a different representation of the expectation. For a fixed number of observations, the numbers of columns supported on different coordinates or pairs of coordinates are dependent, since they sum to the number of observations. To make them independent, we consider a Poisson number of observations. For α > 0 \alpha>0 α > 0 N α N_\alpha N α ( α k ) (\alpha k) ( α k ) U ~ k ( α ) \widetilde U_k(\alpha) U k ( α ) x i x_i x i N α N_\alpha N α U ~ k ( α ) = ∑ n ≥ 0 P { N α = n } P { τ i > n } \widetilde{U}_k(\alpha)=\sum_{n\ge0}\mathbb{P}\{N_\alpha=n\}\mathbb{P}\{\tau_i>n\} U k ( α ) = ∑ n ≥ 0 P { N α = n } P { τ i > n } α \alpha α
∫ 0 ∞ U ~ k ( α ) d α = ∑ n ≥ 0 P { τ i > n } ∫ 0 ∞ P { N α = n } d α = ∑ n ≥ 0 P { τ i > n } ∫ 0 ∞ e − α k ( α k ) n n ! d α = 1 k ∑ n ≥ 0 P { τ i > n } = E [ τ i ] k . \begin{aligned}
\int_0^\infty\widetilde{U}_k(\alpha)\,d\alpha
&=\sum_{n\ge0}\mathbb{P}\{\tau_i>n\}\int_0^\infty\mathbb{P}\{N_\alpha=n\}\,d\alpha\\
&=\sum_{n\ge0}\mathbb{P}\{\tau_i>n\}\int_0^\infty e^{-\alpha k}\frac{(\alpha k)^n}{n!}\,d\alpha\\
&=\frac{1}{k}\sum_{n\ge0}\mathbb{P}\{\tau_i>n\}
=\frac{\mathbb{E}[\tau_i]}{k}.
\end{aligned} ∫ 0 ∞ U k ( α ) d α = n ≥ 0 ∑ P { τ i > n } ∫ 0 ∞ P { N α = n } d α = n ≥ 0 ∑ P { τ i > n } ∫ 0 ∞ e − α k n ! ( α k ) n d α = k 1 n ≥ 0 ∑ P { τ i > n } = k E [ τ i ] . In the first step, we exchanged the sum and the integral, which is allowed since all terms are nonnegative, and used that P { τ i > n } \mathbb{P}\{\tau_i>n\} P { τ i > n } α \alpha α x = α k x=\alpha k x = α k ∫ 0 ∞ x n e − x d x = n ! \int_0^\infty x^n e^{-x}\,dx=n! ∫ 0 ∞ x n e − x d x = n !
Fix α > 0 \alpha>0 α > 0 G G G α \alpha α k + ( k 2 ) k+\binom{k}{2} k + ( 2 k ) u u u s / k s/k s / k { u , v } \{u,v\} { u , v } ( 1 − s ) / ( k 2 ) (1-s)/\binom{k}{2} ( 1 − s ) / ( 2 k ) ( α k ) (\alpha k) ( α k ) ( s α ) (s\alpha) ( s α ) ( 2 ( 1 − s ) α / ( k − 1 ) ) (2(1-s)\alpha/(k-1)) ( 2 ( 1 − s ) α / ( k − 1 )) 1 − e − s α 1-e^{-s\alpha} 1 − e − s α 1 − e − 2 ( 1 − s ) α / ( k − 1 ) 1-e^{-2(1-s)\alpha/(k-1)} 1 − e − 2 ( 1 − s ) α / ( k − 1 )
By Lemma 11(i), if x i x_i x i H i H_i H i i i i G G G H i H_i H i e − s α e^{-s\alpha} e − s α L ≥ 1 L\ge1 L ≥ 1
U ~ k ( α ) ≤ E [ e − s α ∣ H i ∣ ] \widetilde{U}_k(\alpha)\le\mathbb{E}\left[e^{-s\alpha|H_i|}\right] U k ( α ) ≤ E [ e − s α ∣ H i ∣ ] = ∑ r = 1 L e − s α r P { ∣ H i ∣ = r } + ∑ r > L e − s α r P { ∣ H i ∣ = r } ≤ ∑ r = 1 L e − s α r P { ∣ H i ∣ = r } + e − s α ( L + 1 ) P { ∣ H i ∣ > L } ≤ ∑ r = 1 L e − s α r P { ∣ H i ∣ = r } + e − s α ( L + 1 ) . \begin{aligned}
&=\sum_{r=1}^{L}e^{-s\alpha r}\mathbb{P}\{|H_i|=r\}+\sum_{r>L}e^{-s\alpha r}\mathbb{P}\{|H_i|=r\}\\
&\le\sum_{r=1}^{L}e^{-s\alpha r}\mathbb{P}\{|H_i|=r\}+e^{-s\alpha(L+1)}\mathbb{P}\{|H_i|>L\}\\
&\le\sum_{r=1}^{L}e^{-s\alpha r}\mathbb{P}\{|H_i|=r\}+e^{-s\alpha(L+1)}.
\end{aligned} = r = 1 ∑ L e − s α r P { ∣ H i ∣ = r } + r > L ∑ e − s α r P { ∣ H i ∣ = r } ≤ r = 1 ∑ L e − s α r P { ∣ H i ∣ = r } + e − s α ( L + 1 ) P { ∣ H i ∣ > L } ≤ r = 1 ∑ L e − s α r P { ∣ H i ∣ = r } + e − s α ( L + 1 ) . If ∣ H i ∣ = r |H_i|=r ∣ H i ∣ = r r r r S S S i ∈ S i\in S i ∈ S S S S S S S S S S ( k − 1 r − 1 ) \binom{k-1}{r-1} ( r − 1 k − 1 ) r r − 2 r^{r-2} r r − 2
P { ∣ H i ∣ = r } ≤ ( k − 1 r − 1 ) r r − 2 ( 1 − e − 2 ( 1 − s ) α k − 1 ) r − 1 e − 2 ( 1 − s ) α r ( k − r ) k − 1 \mathbb{P}\{|H_i|=r\}\le\binom{k-1}{r-1}r^{r-2}\left(1-e^{-\frac{2(1-s)\alpha}{k-1}}\right)^{r-1}e^{-\frac{2(1-s)\alpha r(k-r)}{k-1}} P { ∣ H i ∣ = r } ≤ ( r − 1 k − 1 ) r r − 2 ( 1 − e − k − 1 2 ( 1 − s ) α ) r − 1 e − k − 1 2 ( 1 − s ) α r ( k − r ) ⟶ r r − 1 r ! ( 2 ( 1 − s ) α ) r − 1 e − 2 ( 1 − s ) α r \longrightarrow\frac{r^{r-1}}{r!}\left(2(1-s)\alpha\right)^{r-1}e^{-2(1-s)\alpha r} ⟶ r ! r r − 1 ( 2 ( 1 − s ) α ) r − 1 e − 2 ( 1 − s ) α r as k → ∞ k\to\infty k → ∞ k → ∞ k\to\infty k → ∞ L → ∞ L\to\infty L → ∞ lim sup k → ∞ U ~ k ( α ) ≤ v \limsup_{k\to\infty}\widetilde{U}_k(\alpha)\le v lim sup k → ∞ U k ( α ) ≤ v
v = ∑ r ≥ 1 r r − 1 r ! ( 2 ( 1 − s ) α ) r − 1 e − ( 2 − s ) α r . v=\sum_{r\ge1}\frac{r^{r-1}}{r!}\left(2(1-s)\alpha\right)^{r-1}e^{-(2-s)\alpha r}. v = r ≥ 1 ∑ r ! r r − 1 ( 2 ( 1 − s ) α ) r − 1 e − ( 2 − s ) α r . It remains to show that v = u s ( α ) v=u_s(\alpha) v = u s ( α ) y ( w ) = ∑ r ≥ 1 r r − 1 w r / r ! y(w)=\sum_{r\ge1}r^{r-1}w^r/r! y ( w ) = ∑ r ≥ 1 r r − 1 w r / r ! y ( w ) = w e y ( w ) y(w)=we^{y(w)} y ( w ) = w e y ( w ) 0 ≤ y ( w ) < 1 0\le y(w)<1 0 ≤ y ( w ) < 1 0 ≤ w < 1 / e 0\le w<1/e 0 ≤ w < 1/ e 2 ( 1 − s ) α v = y ( w ) 2(1-s)\alpha v=y(w) 2 ( 1 − s ) α v = y ( w ) w = 2 ( 1 − s ) α e − ( 2 − s ) α < 1 / e w=2(1-s)\alpha e^{-(2-s)\alpha}<1/e w = 2 ( 1 − s ) α e − ( 2 − s ) α < 1/ e v = exp ( − α ( s + 2 ( 1 − s ) ( 1 − v ) ) ) v=\exp(-\alpha(s+2(1-s)(1-v))) v = exp ( − α ( s + 2 ( 1 − s ) ( 1 − v ))) v v v 0 < v < 1 0<v<1 0 < v < 1 y ( w ) < 1 y(w)<1 y ( w ) < 1 y ( w ) e − y ( w ) = w < 2 ( 1 − s ) α e − 2 ( 1 − s ) α y(w)e^{-y(w)}=w<2(1-s)\alpha e^{-2(1-s)\alpha} y ( w ) e − y ( w ) = w < 2 ( 1 − s ) α e − 2 ( 1 − s ) α v = u s ( α ) v=u_s(\alpha) v = u s ( α ) U ~ k ( α ) ≤ e − s α \widetilde{U}_k(\alpha)\le e^{-s\alpha} U k ( α ) ≤ e − s α e − s α − U ~ k ( α ) e^{-s\alpha}-\widetilde{U}_k(\alpha) e − s α − U k ( α ) lim sup k → ∞ E [ τ i ] / k ≤ ∫ 0 ∞ u s ( α ) d α \limsup_{k\to\infty}\mathbb{E}[\tau_i]/k\le\int_0^\infty u_s(\alpha)\,d\alpha lim sup k → ∞ E [ τ i ] / k ≤ ∫ 0 ∞ u s ( α ) d α
Finally, solving (18) for α \alpha α α ( u ) = − log u / ( s + 2 ( 1 − s ) ( 1 − u ) ) \alpha(u)=-\log u/(s+2(1-s)(1-u)) α ( u ) = − log u / ( s + 2 ( 1 − s ) ( 1 − u )) ( 0 , 1 ) (0,1) ( 0 , 1 ) α ( u ) → ∞ \alpha(u)\to\infty α ( u ) → ∞ u ↓ 0 u\downarrow0 u ↓ 0 α ( u ) → 0 \alpha(u)\to0 α ( u ) → 0 u ↑ 1 u\uparrow1 u ↑ 1 ∫ 0 ∞ u s ( α ) d α = ∫ 0 1 α ( u ) d u \int_0^\infty u_s(\alpha)\,d\alpha=\int_0^1\alpha(u)\,du ∫ 0 ∞ u s ( α ) d α = ∫ 0 1 α ( u ) d u □ \square □
The right side of (17) is minimized at s ≈ 0.1554737 s\approx0.1554737 s ≈ 0.1554737 0.793933445 0.793933445 0.793933445 [24 ] . In fact, the peeling decoder recovers exactly the coordinates in marked components, so the upper bound in the proof of Proposition 12 also applies to it. Hence, for this distribution, an optimal decoder has the same asymptotic normalized expected recovery time as the peeling decoder, for every s s s
Finite-field generator matrices
The degree distribution P ( z ) = s z + ( 1 − s ) z 2 P(z)=sz+(1-s)z^2 P ( z ) = sz + ( 1 − s ) z 2 q q q a ≥ 1 a\ge1 a ≥ 1 F q \mathbb{F}_q F q
G k , q ( a ) = [ I k ⋯ I k | D k , q ] , G_{k,q}(a)=\left[I_k\ \cdots\ I_k\ \middle|\ D_{k,q}\right], G k , q ( a ) = [ I k ⋯ I k ∣ D k , q ] , where there are a a a I k I_k I k
where I k I_k I k k × k k\times k k × k D k , q D_{k,q} D k , q e u + λ e v e_u+\lambda e_v e u + λ e v 1 ≤ u < v ≤ k 1\le u<v\le k 1 ≤ u < v ≤ k λ ∈ F q ∗ \lambda\in\mathbb{F}_q^* λ ∈ F q ∗ k k k
a k + ( q − 1 ) ( k 2 ) . ak+(q-1)\binom{k}{2}. ak + ( q − 1 ) ( 2 k ) . Uniform sampling of its columns with replacement produces a weight-one column with probability
s k = a k a k + ( q − 1 ) ( k 2 ) . s_k=\frac{ak}{ak+(q-1)\binom{k}{2}}. s k = ak + ( q − 1 ) ( 2 k ) ak . Otherwise, it produces a column e u + λ e v \mathbf{e}_u+\lambda\mathbf{e}_v e u + λ e v { u , v } \{u,v\} { u , v } λ \lambda λ F q ∗ \mathbb{F}_q^* F q ∗ 0 < s < 1 0<s<1 0 < s < 1 I k I_k I k G k , q ( a ) G_{k,q}(a) G k , q ( a )
a = a k : = ⌈ s ( q − 1 ) ( k − 1 ) 2 ( 1 − s ) ⌉ , (19) a=a_k:=\left\lceil\frac{s(q-1)(k-1)}{2(1-s)}\right\rceil, \tag*{(19)} a = a k := ⌈ 2 ( 1 − s ) s ( q − 1 ) ( k − 1 ) ⌉ , (19) which gives s k → s s_k\to s s k → s k → ∞ k\to\infty k → ∞ q = 2 q=2 q = 2 G k , 2 ( a k ) G_{k,2}(a_k) G k , 2 ( a k ) [24 ] for the peeling decoder with column weights one and two. For larger q q q G k , q ( a ) G_{k,q}(a) G k , q ( a ) [23 ] , which also combines copies of I k I_k I k x x x k k k [24 ] that, with the ratio of weight-one to weight-two columns optimized, the normalized expected recovery time tends to ≈ 0.7939 \approx0.7939 ≈ 0.7939 [24 ] for binary fully symmetric codes with column weights one and two under the peeling decoder. Proposition 14 below establishes this limit for G k , q ( a k ) G_{k,q}(a_k) G k , q ( a k )
Lemma 13. Let v 1 , … , v n \mathbf{v}_1,\ldots,\mathbf{v}_n v 1 , … , v n G k , q ( a ) G_{k,q}(a) G k , q ( a ) H i \mathcal{H}_i H i i i i G G G H i \mathcal{H}_i H i e i ∈ ⟨ M k ( n ) ⟩ \mathbf{e}_i\in\langle M_k(n)\rangle e i ∈ ⟨ M k ( n )⟩ H i \mathcal{H}_i H i m m m
Pr { e i ∉ ⟨ M k ( n ) ⟩ ∣ supports } = ( q − 1 ) − ( m − ∣ H i ∣ + 1 ) . (20) \Pr\{\mathbf{e}_i\notin\langle M_k(n)\rangle\mid\text{supports}\}=(q-1)^{-(m-|\mathcal{H}_i|+1)}. \tag*{(20)} Pr { e i ∈ / ⟨ M k ( n )⟩ ∣ supports } = ( q − 1 ) − ( m − ∣ H i ∣ + 1 ) . (20) Proof. If H i \mathcal{H}_i H i e i ∈ ⟨ M k ( n ) ⟩ \mathbf{e}_i\in\langle M_k(n)\rangle e i ∈ ⟨ M k ( n )⟩ r = ∣ H i ∣ r=|\mathcal{H}_i| r = ∣ H i ∣ H i \mathcal{H}_i H i r − 1 r-1 r − 1 T T T r − 1 r-1 r − 1 r r r H i \mathcal{H}_i H i T T T m − r + 1 m-r+1 m − r + 1 e u + λ e v \mathbf{e}_u+\lambda\mathbf{e}_v e u + λ e v H i \mathcal{H}_i H i T T T T T T r r r e i \mathbf{e}_i e i e i ∉ ⟨ M k ( n ) ⟩ \mathbf{e}_i\notin\langle M_k(n)\rangle e i ∈ / ⟨ M k ( n )⟩ T T T u , v u,v u , v λ ∈ F q ∗ \lambda\in\mathbb{F}_q^* λ ∈ F q ∗ e u + λ e v \mathbf{e}_u+\lambda\mathbf{e}_v e u + λ e v T T T u u u v v v T T T λ \lambda λ F q ∗ \mathbb{F}_q^* F q ∗ ( q − 1 ) − ( m − r + 1 ) (q-1)^{-(m-r+1)} ( q − 1 ) − ( m − r + 1 )
Proposition 14. For every prime power q q q 0 < s < 1 0<s<1 0 < s < 1 G k , q ( a k ) G_{k,q}(a_k) G k , q ( a k ) a k a_k a k
lim k → ∞ E [ τ i ] k = ∫ 0 1 − log u s + 2 ( 1 − s ) ( 1 − u ) d u . (21) \lim_{k\to\infty}\frac{\mathbb{E}[\tau_i]}{k}=\int_0^1\frac{-\log u}{s+2(1-s)(1-u)}\,du. \tag*{(21)} k → ∞ lim k E [ τ i ] = ∫ 0 1 s + 2 ( 1 − s ) ( 1 − u ) − log u d u . (21) Proof. Multiplying a column by a nonzero scalar does not change the span, so it does not change τ i \tau_i τ i G k , q ( a k ) G_{k,q}(a_k) G k , q ( a k ) F q \mathbb{F}_q F q P k ( z ) = s k z 2 + ( 1 − s k ) z P_k(z)=s_k z^2+(1-s_k)z P k ( z ) = s k z 2 + ( 1 − s k ) z μ \mu μ F q ∗ \mathbb{F}_q^* F q ∗ e u \mathbf{e}_u e u u < v u<v u < v a e u + b e v = a ( e u + ( b / a ) e v ) a\mathbf{e}_u+b\mathbf{e}_v=a(\mathbf{e}_u+(b/a)\mathbf{e}_v) a e u + b e v = a ( e u + ( b / a ) e v ) b / a b/a b / a F q ∗ \mathbb{F}_q^* F q ∗ s s s s k → s s_k\to s s k → s P k → P P_k\to P P k → P s s s s k s_k s k s s s
Taking s = 0.1554737 s=0.1554737 s = 0.1554737 0.793933445 … 0.793933445\ldots 0.793933445 … q q q G k , q ( a k ) G_{k,q}(a_k) G k , q ( a k )
a k k + ( q − 1 ) ( k 2 ) ∼ ( q − 1 ) k 2 2 ( 1 − s ) , a_k k+(q-1)\binom{k}{2}\sim\frac{(q-1)k^2}{2(1-s)}, a k k + ( q − 1 ) ( 2 k ) ∼ 2 ( 1 − s ) ( q − 1 ) k 2 , so the rate tends to zero. One may instead fix a block dimension ℓ \ell ℓ t t t G ℓ , q ( a ℓ ) G_{\ell,q}(a_\ell) G ℓ , q ( a ℓ ) 1 / t 1/t 1/ t x i x_i x i i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ]
E [ τ i ( ⨁ j = 1 t G ℓ , q ( a ℓ ) ) ] t ℓ = E [ τ i ( G ℓ , q ( a ℓ ) ) ] ℓ . \frac{\mathbb{E}\left[\tau_i\left(\bigoplus_{j=1}^{t}G_{\ell,q}(a_\ell)\right)\right]}{t\ell}
=\frac{\mathbb{E}\left[\tau_i\left(G_{\ell,q}(a_\ell)\right)\right]}{\ell}. t ℓ E [ τ i ( ⨁ j = 1 t G ℓ , q ( a ℓ ) ) ] = ℓ E [ τ i ( G ℓ , q ( a ℓ ) ) ] . This gives a positive rate for fixed ℓ \ell ℓ ℓ \ell ℓ
Conclusion
We proved that lim inf k → ∞ E [ τ i ] / k ≥ π / 4 \liminf_{k\to\infty}\mathbb{E}[\tau_i]/k\ge\pi/4 lim inf k → ∞ E [ τ i ] / k ≥ π /4
For degree distributions with support size in 1 , 2 1,2 1 , 2 0.793933445 0.793933445 0.793933445
We have also obtained several results for columns with growing support over infinite fields, which we plan to include in an extended version.
AI Statement
OpenAI ChatGPT and Anthropic Claude were used as writing assistants for editing and rephrasing the text, including the presentation of some proofs, and for checking related literature. All results and proofs are due to the authors, who directed and verified all changes
References
Proofs for Section III
Let α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta> 0 β > 0 A k A_k A k B k B_k B k N N N w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N d 1 , … , d k d_1,\ldots,d_k d 1 , … , d k
a = ( N , w 1 , … , w N , d 1 , … , d k ) a=(N,w_1,\ldots,w_N,d_1,\ldots,d_k) a = ( N , w 1 , … , w N , d 1 , … , d k ) for its degree data and T = w 1 + ⋯ + w N T=w_1+\cdots+w_N T = w 1 + ⋯ + w N
Lemma 15. For every δ > 0 \delta>0 δ > 0 C δ C_\delta C δ k δ k_\delta k δ k ≥ k δ k\ge k_\delta k ≥ k δ B \mathcal{B} B
P { A k ∈ B } ≤ C δ P { B k ∈ B } + δ . \mathbb{P}\{A_k\in\mathcal{B}\}\le C_\delta\mathbb{P}\{B_k\in\mathcal{B}\}+\delta. P { A k ∈ B } ≤ C δ P { B k ∈ B } + δ . Proof. Since A k A_k A k B k B_k B k p A ( a ) p_A(a) p A ( a ) p B ( a ) p_B(a) p B ( a ) λ = α P ′ ( 1 ) + β \lambda=\alpha\mathbb{P}'(1)+\beta λ = α P ′ ( 1 ) + β π k ( T ) = P ( Poisson ( λ k ) = T ) \pi_k(T)=\mathbb{P}(\operatorname{Poisson}(\lambda k)=T) π k ( T ) = P ( Poisson ( λk ) = T ) q ( a ) q(a) q ( a ) a a a B k B_k B k Z k Z_k Z k p B ( a ) = q ( a ) / Z k p_B(a)=q(a)/Z_k p B ( a ) = q ( a ) / Z k p B ( a ) > 0 p_B(a)>0 p B ( a ) > 0 k k k ( λ ) (\lambda) ( λ ) ( λ k ) (\lambda k) ( λk )
Z k ≤ P { d 1 + ⋯ + d k = w 1 + ⋯ + w N } = ∑ T P { w 1 + ⋯ + w N = T } π k ( T ) ≤ max T π k ( T ) . Z_k\le\mathbb{P}\{d_1+\cdots+d_k=w_1+\cdots+w_N\}
=\sum_T\mathbb{P}\{w_1+\cdots+w_N=T\}\pi_k(T)
\le\max_T\pi_k(T). Z k ≤ P { d 1 + ⋯ + d k = w 1 + ⋯ + w N } = T ∑ P { w 1 + ⋯ + w N = T } π k ( T ) ≤ T max π k ( T ) . To compute p A ( a ) p_A(a) p A ( a ) w j w_j w j N N N
T ! d 1 ! ⋯ d k ! k − T = 1 π k ( T ) ∏ i = 1 k e − λ λ d i d i ! . \frac{T!}{d_1!\cdots d_k!}k^{-T}=\frac{1}{\pi_k(T)}\prod_{i=1}^k e^{-\lambda}\frac{\lambda^{d_i}}{d_i!}. d 1 ! ⋯ d k ! T ! k − T = π k ( T ) 1 i = 1 ∏ k e − λ d i ! λ d i . The support of A k A_k A k N N N ∏ j ( 1 − w j 2 / ( 2 k ) ) ≥ e − W 2 N / k \prod_j(1-w_j^2/(2k))\ge e^{-W^2N/k} ∏ j ( 1 − w j 2 / ( 2 k )) ≥ e − W 2 N / k k ≥ W 2 k\ge W^2 k ≥ W 2 a a a p A ( a ) > 0 p_A(a)>0 p A ( a ) > 0
p A ( a ) ≤ e W 2 N / k q ( a ) π k ( T ) = e W 2 N / k Z k π k ( T ) p B ( a ) ≤ e W 2 N / k max T ′ π k ( T ′ ) π k ( T ) p B ( a ) . p_A(a)\le e^{W^2N/k}\frac{q(a)}{\pi_k(T)}
=e^{W^2N/k}\frac{Z_k}{\pi_k(T)}p_B(a)
\le e^{W^2N/k}\frac{\max_{T'}\pi_k(T')}{\pi_k(T)}p_B(a). p A ( a ) ≤ e W 2 N / k π k ( T ) q ( a ) = e W 2 N / k π k ( T ) Z k p B ( a ) ≤ e W 2 N / k π k ( T ) max T ′ π k ( T ′ ) p B ( a ) . By Stirling’s formula, there is a constant C t ′ C'_t C t ′ max T ′ π k ( T ′ ) ≤ C t ′ π k ( T ) \max_{T'}\pi_k(T')\le C'_t\pi_k(T) max T ′ π k ( T ′ ) ≤ C t ′ π k ( T ) ∣ T − λ k ∣ ≤ t k |T-\lambda k|\le t\sqrt{k} ∣ T − λk ∣ ≤ t k k k k N ≤ 2 ( α + β ) k N\le2(\alpha+\beta)k N ≤ 2 ( α + β ) k ∣ T − λ k ∣ ≤ t k |T-\lambda k|\le t\sqrt{k} ∣ T − λk ∣ ≤ t k p A ( a ) ≤ C t p B ( a ) p_A(a)\le C_t p_B(a) p A ( a ) ≤ C t p B ( a ) C t = C t ′ e 2 ( α + β ) W 2 C_t=C'_t e^{2(\alpha+\beta)W^2} C t = C t ′ e 2 ( α + β ) W 2
P { A k ∈ B } ≤ C t P { B k ∈ B } + P { N > 2 ( α + β ) k } + P { ∣ T − λ k ∣ > t k } , (22) \mathbb{P}\{A_k\in\mathcal{B}\}\le C_t\mathbb{P}\{B_k\in\mathcal{B}\}+\mathbb{P}\{N>2(\alpha+\beta)k\}
+\mathbb{P}\{|T-\lambda k|>t\sqrt{k}\}, \tag*{(22)} P { A k ∈ B } ≤ C t P { B k ∈ B } + P { N > 2 ( α + β ) k } + P { ∣ T − λk ∣ > t k } , (22) where the last two probabilities refer to A k A_k A k A k A_k A k N N N Poisson ( ( α + β ) k ) \operatorname{Poisson}((\alpha+\beta)k) Poisson (( α + β ) k ) T T T N N N T T T λ k \lambda k λk ( α + β ) k E [ w 2 ] (\alpha+\beta)k\mathbb{E}[w^2] ( α + β ) k E [ w 2 ] 1 / ( ( α + β ) k ) 1/((\alpha+\beta)k) 1/ (( α + β ) k ) ( α + β ) E [ w 2 ] / t 2 (\alpha+\beta)\mathbb{E}[w^2]/t^2 ( α + β ) E [ w 2 ] / t 2 t t t ( α + β ) E [ w 2 ] / t 2 ≤ δ / 2 (\alpha+\beta)\mathbb{E}[w^2]/t^2\leq\delta/2 ( α + β ) E [ w 2 ] / t 2 ≤ δ /2 k k k 1 / ( ( α + β ) k ) ≤ δ / 2 1/((\alpha+\beta)k)\leq\delta/2 1/ (( α + β ) k ) ≤ δ /2 C δ = C t C_\delta=C_t C δ = C t
Corollary 16. For all α ≥ 0 \alpha\geq0 α ≥ 0 β > 0 \beta>0 β > 0 rank A k / k → R P ( α , β ) \operatorname{rank} A_k/k\to R_P(\alpha,\beta) rank A k / k → R P ( α , β ) k → ∞ k\to\infty k → ∞
Proof. Fix ε > 0 \varepsilon>0 ε > 0 B \mathcal{B} B M M M
∣ rank M k − R P ( α , β ) ∣ > ε . \left|\frac{\operatorname{rank}M}{k}-R_P(\alpha,\beta)\right|>\varepsilon. k rank M − R P ( α , β ) > ε . By Theorem 4, P { B k ∈ B } → 0 \mathbb{P}\{B_k\in\mathcal{B}\}\to0 P { B k ∈ B } → 0 δ > 0 \delta>0 δ > 0 k ≥ k δ k\geq k_\delta k ≥ k δ
P { A k ∈ B } ≤ C δ P { B k ∈ B } + δ , \mathbb{P}\{A_k\in\mathcal{B}\}\leq C_\delta\mathbb{P}\{B_k\in\mathcal{B}\}+\delta, P { A k ∈ B } ≤ C δ P { B k ∈ B } + δ , and since C δ C_\delta C δ k k k lim sup k → ∞ P { A k ∈ B } ≤ δ \limsup_{k\to\infty}\mathbb{P}\{A_k\in\mathcal{B}\}\leq\delta lim sup k → ∞ P { A k ∈ B } ≤ δ δ > 0 \delta>0 δ > 0 P { A k ∈ B } → 0 \mathbb{P}\{A_k\in\mathcal{B}\}\to0 P { A k ∈ B } → 0 ε > 0 \varepsilon>0 ε > 0 rank A k / k → R P ( α , β ) \operatorname{rank} A_k/k\to R_P(\alpha,\beta) rank A k / k → R P ( α , β )
Proof of Lemma 6. Let β > 0 \beta>0 β > 0 k k k
U k ( α ) ≥ R k ( α , β ) − R k ( α , 0 ) 1 − e − β . U_k(\alpha)\geq\frac{R_k(\alpha,\beta)-R_k(\alpha,0)}{1-e^{-\beta}}. U k ( α ) ≥ 1 − e − β R k ( α , β ) − R k ( α , 0 ) . By Lemma 5, the right side converges to ( R P ( α , β ) − R P ( α , 0 ) ) / ( 1 − e − β ) (R_P(\alpha,\beta)-R_P(\alpha,0))/(1-e^{-\beta}) ( R P ( α , β ) − R P ( α , 0 )) / ( 1 − e − β ) k → ∞ k\to\infty k → ∞ (7) ,
lim inf k → ∞ U k ( α ) ≥ R P ( α , β ) − R P ( α , 0 ) 1 − e − β = max z ∈ [ 0 , 1 ] Φ α ( z ) − max z ∈ [ 0 , 1 ] Φ α , β ( z ) 1 − e − β . \liminf_{k\to\infty}U_k(\alpha)\geq\frac{R_P(\alpha,\beta)-R_P(\alpha,0)}{1-e^{-\beta}}
=\frac{\max_{z\in[0,1]}\Phi_\alpha(z)-\max_{z\in[0,1]}\Phi_{\alpha,\beta}(z)}{1-e^{-\beta}}. k → ∞ lim inf U k ( α ) ≥ 1 − e − β R P ( α , β ) − R P ( α , 0 ) = 1 − e − β max z ∈ [ 0 , 1 ] Φ α ( z ) − max z ∈ [ 0 , 1 ] Φ α , β ( z ) . By (6) , Φ α , β ( z ) = Φ α ( z ) − ( 1 − e − β ) e − α P ′ ( z ) \Phi_{\alpha,\beta}(z)=\Phi_\alpha(z)-(1-e^{-\beta})e^{-\alpha P'(z)} Φ α , β ( z ) = Φ α ( z ) − ( 1 − e − β ) e − α P ′ ( z ) z β z_\beta z β Φ α , β \Phi_{\alpha,\beta} Φ α , β [ 0 , 1 ] [0,1] [ 0 , 1 ]
max z ∈ [ 0 , 1 ] Φ α , β ( z ) = Φ α ( z β ) − ( 1 − e − β ) e − α P ′ ( z β ) ≤ max z ∈ [ 0 , 1 ] Φ α ( z ) − ( 1 − e − β ) e − α P ′ ( z β ) . \max_{z\in[0,1]}\Phi_{\alpha,\beta}(z)=\Phi_\alpha(z_\beta)-(1-e^{-\beta})e^{-\alpha P'(z_\beta)}
\leq\max_{z\in[0,1]}\Phi_\alpha(z)-(1-e^{-\beta})e^{-\alpha P'(z_\beta)}. z ∈ [ 0 , 1 ] max Φ α , β ( z ) = Φ α ( z β ) − ( 1 − e − β ) e − α P ′ ( z β ) ≤ z ∈ [ 0 , 1 ] max Φ α ( z ) − ( 1 − e − β ) e − α P ′ ( z β ) . Consequently, for every β > 0 \beta>0 β > 0 z β ∈ arg max z ∈ [ 0 , 1 ] Φ α , β ( z ) z_\beta\in\arg\max_{z\in[0,1]}\Phi_{\alpha,\beta}(z) z β ∈ arg max z ∈ [ 0 , 1 ] Φ α , β ( z )
lim inf k → ∞ U k ( α ) ≥ e − α P ′ ( z β ) . \liminf_{k\to\infty}U_k(\alpha)\geq e^{-\alpha P'(z_\beta)}. k → ∞ lim inf U k ( α ) ≥ e − α P ′ ( z β ) . Here z β z_\beta z β Φ α , β \Phi_{\alpha,\beta} Φ α , β Φ α = Φ α , 0 \Phi_\alpha=\Phi_{\alpha,0} Φ α = Φ α , 0 z ∗ ∈ A P ( α ) z^*\in A_P(\alpha) z ∗ ∈ A P ( α )
lim inf k → ∞ U k ( α ) ≥ e − α P ′ ( z ∗ ) ≥ min z ∈ A P ( α ) e − α P ′ ( z ) = U P ( α ) . \liminf_{k\to\infty}U_k(\alpha)\geq e^{-\alpha P'(z^*)}
\geq\min_{z\in A_P(\alpha)}e^{-\alpha P'(z)}=U_P(\alpha). k → ∞ lim inf U k ( α ) ≥ e − α P ′ ( z ∗ ) ≥ z ∈ A P ( α ) min e − α P ′ ( z ) = U P ( α ) . We obtain such a point by letting the perturbation vanish. Set β h = 1 / h \beta_h=1/h β h = 1/ h h h h z h z_h z h Φ α , β h \Phi_{\alpha,\beta_h} Φ α , β h [ 0 , 1 ] [0,1] [ 0 , 1 ] z h i → z ∗ z_{h_i}\to z^* z h i → z ∗ Φ α \Phi_\alpha Φ α z ↦ e − α P ′ ( z ) z\mapsto e^{-\alpha P'(z)} z ↦ e − α P ′ ( z )
Since 0 ≤ Φ α ( z ) − Φ α , β h ( z ) ≤ 1 − e − β h 0\leq\Phi_\alpha(z)-\Phi_{\alpha,\beta_h}(z)\leq1-e^{-\beta_h} 0 ≤ Φ α ( z ) − Φ α , β h ( z ) ≤ 1 − e − β h z ∈ [ 0 , 1 ] z\in[0,1] z ∈ [ 0 , 1 ] 1 − e − β h 1-e^{-\beta_h} 1 − e − β h
Φ α ( z h ) ≥ Φ α , β h ( z h ) = max z ∈ [ 0 , 1 ] Φ α , β h ( z ) ≥ max z ∈ [ 0 , 1 ] Φ α ( z ) − ( 1 − e − β h ) . \Phi_\alpha(z_h)\geq\Phi_{\alpha,\beta_h}(z_h)=\max_{z\in[0,1]}\Phi_{\alpha,\beta_h}(z)
\geq\max_{z\in[0,1]}\Phi_\alpha(z)-(1-e^{-\beta_h}). Φ α ( z h ) ≥ Φ α , β h ( z h ) = z ∈ [ 0 , 1 ] max Φ α , β h ( z ) ≥ z ∈ [ 0 , 1 ] max Φ α ( z ) − ( 1 − e − β h ) . Letting i → ∞ i\to\infty i → ∞ h = h i h=h_i h = h i Φ α \Phi_\alpha Φ α Φ α ( z ∗ ) ≥ max z ∈ [ 0 , 1 ] Φ α ( z ) \Phi_\alpha(z^*)\geq\max_{z\in[0,1]}\Phi_\alpha(z) Φ α ( z ∗ ) ≥ max z ∈ [ 0 , 1 ] Φ α ( z ) z ∗ ∈ A P ( α ) z^*\in A_P(\alpha) z ∗ ∈ A P ( α ) lim inf k → ∞ U k ( α ) ≥ e − α P ′ ( z h ) \liminf_{k\to\infty}U_k(\alpha)\geq e^{-\alpha P'(z_h)} lim inf k → ∞ U k ( α ) ≥ e − α P ′ ( z h ) h h h z ↦ e − α P ′ ( z ) z\mapsto e^{-\alpha P'(z)} z ↦ e − α P ′ ( z )
lim inf k → ∞ U k ( α ) ≥ lim i → ∞ e − α P ′ ( z h i ) = e − α P ′ ( z ∗ ) ≥ min z ∈ A P ( α ) e − α P ′ ( z ) = U P ( α ) , \liminf_{k\to\infty}U_k(\alpha)\geq\lim_{i\to\infty}e^{-\alpha P'(z_{h_i})}
=e^{-\alpha P'(z^*)}
\geq\min_{z\in A_P(\alpha)}e^{-\alpha P'(z)}
=U_P(\alpha), k → ∞ lim inf U k ( α ) ≥ i → ∞ lim e − α P ′ ( z h i ) = e − α P ′ ( z ∗ ) ≥ z ∈ A P ( α ) min e − α P ′ ( z ) = U P ( α ) , which proves (12) .
Appendix B: Proofs for Section IV
Throughout this subsection, p 1 < 1 p_1<1 p 1 < 1 ∑ w = 1 W p w = 1 \sum_{w=1}^{W}p_w=1 ∑ w = 1 W p w = 1 w ′ ≥ 2 w'\geq2 w ′ ≥ 2 p w ′ > 0 p_{w'}>0 p w ′ > 0
P ′ ′ ( z ) = ∑ w = 2 W w ( w − 1 ) p w z w − 2 ≥ w ′ ( w ′ − 1 ) p w ′ z w ′ − 2 > 0 P''(z)=\sum_{w=2}^{W}w(w-1)p_w z^{w-2}\geq w'(w'-1)p_{w'}z^{w'-2}>0 P ′′ ( z ) = w = 2 ∑ W w ( w − 1 ) p w z w − 2 ≥ w ′ ( w ′ − 1 ) p w ′ z w ′ − 2 > 0 for 0 < z ≤ 1 0<z\leq1 0 < z ≤ 1
Proof of Lemma 8. Since P ′ ′ ( z ) > 0 P''(z)>0 P ′′ ( z ) > 0 0 < z ≤ 1 0<z\leq1 0 < z ≤ 1 P ′ ( z ) P'(z) P ′ ( z ) [ 0 , 1 ] [0,1] [ 0 , 1 ] z ↦ e − α P ′ ( z ) z\mapsto e^{-\alpha P'(z)} z ↦ e − α P ′ ( z ) α > 0 \alpha>0 α > 0 U P ( α ) U_P(\alpha) U P ( α ) A P ( α ) A_P(\alpha) A P ( α ) U P ( α ) = e − α P ′ ( ζ ( α ) ) U_P(\alpha)=e^{-\alpha P'(\zeta(\alpha))} U P ( α ) = e − α P ′ ( ζ ( α ))
Let Φ α ′ \Phi'_\alpha Φ α ′ Φ α \Phi_\alpha Φ α z z z
Φ α ′ ( z ) = α P ′ ′ ( z ) ( 1 − z − e − α P ′ ( z ) ) . (23) \Phi'_\alpha(z)=\alpha P''(z)(1-z-e^{-\alpha P'(z)}). \tag*{(23)} Φ α ′ ( z ) = α P ′′ ( z ) ( 1 − z − e − α P ′ ( z ) ) . (23) Next, we show that an interior maximizer satisfies α P ′ ( z ) = − log ( 1 − z ) \alpha P'(z)=-\log(1-z) α P ′ ( z ) = − log ( 1 − z ) α > 0 \alpha>0 α > 0 z ∗ ∈ ( 0 , 1 ) z^*\in(0,1) z ∗ ∈ ( 0 , 1 ) Φ α \Phi_\alpha Φ α Φ α \Phi_\alpha Φ α Φ α ′ ( z ∗ ) = 0 \Phi'_\alpha(z^*)=0 Φ α ′ ( z ∗ ) = 0 α P ′ ′ ( z ∗ ) > 0 \alpha P''(z^*)>0 α P ′′ ( z ∗ ) > 0 (23) gives 1 − z ∗ = e − α P ′ ( z ∗ ) 1-z^*=e^{-\alpha P'(z^*)} 1 − z ∗ = e − α P ′ ( z ∗ ) 1 − z ∗ > 0 1-z^*>0 1 − z ∗ > 0
α P ′ ( z ∗ ) = − log ( 1 − z ∗ ) . \alpha P'(z^*)=-\log(1-z^*). α P ′ ( z ∗ ) = − log ( 1 − z ∗ ) . The endpoint z = 1 z=1 z = 1 Φ α \Phi_\alpha Φ α (23) , Φ α ′ ( 1 ) = − α P ′ ′ ( 1 ) e − α P ′ ( 1 ) < 0 \Phi'_\alpha(1)=-\alpha P''(1)e^{-\alpha P'(1)}<0 Φ α ′ ( 1 ) = − α P ′′ ( 1 ) e − α P ′ ( 1 ) < 0 Φ α ′ \Phi'_\alpha Φ α ′ δ > 0 \delta>0 δ > 0 Φ α ′ < 0 \Phi'_\alpha<0 Φ α ′ < 0 ( 1 − δ , 1 ] (1-\delta,1] ( 1 − δ , 1 ] z ∈ ( 1 − δ , 1 ) z\in(1-\delta,1) z ∈ ( 1 − δ , 1 ) ξ ∈ ( z , 1 ) \xi\in(z,1) ξ ∈ ( z , 1 )
Φ α ( 1 ) − Φ α ( z ) = Φ α ′ ( ξ ) ( 1 − z ) < 0 , \Phi_\alpha(1)-\Phi_\alpha(z)=\Phi'_\alpha(\xi)(1-z)<0, Φ α ( 1 ) − Φ α ( z ) = Φ α ′ ( ξ ) ( 1 − z ) < 0 , since Φ α ′ ( ξ ) < 0 \Phi'_\alpha(\xi)<0 Φ α ′ ( ξ ) < 0 1 − z > 0 1-z>0 1 − z > 0 Φ α ( z ) > Φ α ( 1 ) \Phi_\alpha(z)>\Phi_\alpha(1) Φ α ( z ) > Φ α ( 1 ) Φ α \Phi_\alpha Φ α ( 1 − δ , 1 ] (1-\delta,1] ( 1 − δ , 1 ]
Next, suppose that the endpoint z = 0 z=0 z = 0 Φ α \Phi_\alpha Φ α P ′ ( 0 ) = p 1 = 0 P'(0)=p_1=0 P ′ ( 0 ) = p 1 = 0
lim z ↓ 0 1 − z − e − α P ′ ( z ) = 1 − e − α p 1 > 0 \lim_{z\downarrow0}1-z-e^{-\alpha P'(z)}=1-e^{-\alpha p_1}>0 z ↓ 0 lim 1 − z − e − α P ′ ( z ) = 1 − e − α p 1 > 0 so this factor is positive on [ 0 , δ ) [0,\delta) [ 0 , δ ) δ > 0 \delta>0 δ > 0 P ′ ′ ( z ) > 0 P''(z)>0 P ′′ ( z ) > 0 z > 0 z>0 z > 0 (23) gives Φ α ′ > 0 \Phi'_\alpha>0 Φ α ′ > 0 ( 0 , δ ) (0,\delta) ( 0 , δ ) z ∈ ( 0 , δ ) z\in(0,\delta) z ∈ ( 0 , δ ) ξ ∈ ( 0 , z ) \xi\in(0,z) ξ ∈ ( 0 , z )
Φ α ( z ) − Φ α ( 0 ) = z Φ α ′ ( ξ ) > 0 , \Phi_\alpha(z)-\Phi_\alpha(0)=z\Phi'_\alpha(\xi)>0, Φ α ( z ) − Φ α ( 0 ) = z Φ α ′ ( ξ ) > 0 , and thus Φ α ( z ) > Φ α ( 0 ) \Phi_\alpha(z)>\Phi_\alpha(0) Φ α ( z ) > Φ α ( 0 ) z ∈ ( 0 , δ ) z\in(0,\delta) z ∈ ( 0 , δ ) P ′ ( 0 ) = 0 P'(0)=0 P ′ ( 0 ) = 0 1 − z = e − α P ′ ( z ) 1-z=e^{-\alpha P'(z)} 1 − z = e − α P ′ ( z ) z = 0 z=0 z = 0
Consequently, every maximizer z ∗ z^* z ∗ Φ α \Phi_\alpha Φ α
1 − z ∗ = e − α P ′ ( z ∗ ) . 1-z^*=e^{-\alpha P'(z^*)}. 1 − z ∗ = e − α P ′ ( z ∗ ) . Applying this to z = ζ ( α ) z=\zeta(\alpha) z = ζ ( α ) U P ( α ) = e − α P ′ ( ζ ( α ) ) U_P(\alpha)=e^{-\alpha P'(\zeta(\alpha))} U P ( α ) = e − α P ′ ( ζ ( α ))
U P ( α ) = 1 − ζ ( α ) . U_P(\alpha)=1-\zeta(\alpha). U P ( α ) = 1 − ζ ( α ) . Proof of Lemma 9. We first show that ζ \zeta ζ Φ α \Phi_\alpha Φ α 0 ≤ z 1 < z 2 ≤ 1 0\le z_1<z_2\le1 0 ≤ z 1 < z 2 ≤ 1
Φ α ( z 2 ) − Φ α ( z 1 ) α = H ( z 1 ) − H ( z 2 ) − ∫ P ′ ( z 1 ) P ′ ( z 2 ) e − α u d u . (24) \frac{\Phi_\alpha(z_2)-\Phi_\alpha(z_1)}{\alpha}
=H(z_1)-H(z_2)-\int_{P'(z_1)}^{P'(z_2)}e^{-\alpha u}\,du. \tag*{(24)} α Φ α ( z 2 ) − Φ α ( z 1 ) = H ( z 1 ) − H ( z 2 ) − ∫ P ′ ( z 1 ) P ′ ( z 2 ) e − α u d u . (24) The right side is strictly increasing in α \alpha α Φ α ( z 2 ) ≥ Φ α ( z 1 ) \Phi_\alpha(z_2)\ge\Phi_\alpha(z_1) Φ α ( z 2 ) ≥ Φ α ( z 1 ) α > 0 \alpha>0 α > 0 Φ α ′ ( z 2 ) > Φ α ′ ( z 1 ) \Phi_{\alpha'}(z_2)>\Phi_{\alpha'}(z_1) Φ α ′ ( z 2 ) > Φ α ′ ( z 1 ) α ′ > α \alpha'>\alpha α ′ > α
We now use this to show that ζ \zeta ζ ζ ( α ′ ) < ζ ( α ) \zeta(\alpha')<\zeta(\alpha) ζ ( α ′ ) < ζ ( α ) 0 < α < α ′ 0<\alpha<\alpha' 0 < α < α ′ z 1 = ζ ( α ′ ) z_1=\zeta(\alpha') z 1 = ζ ( α ′ ) z 2 = ζ ( α ) z_2=\zeta(\alpha) z 2 = ζ ( α ) z 2 z_2 z 2 Φ α \Phi_\alpha Φ α Φ α ( z 2 ) ≥ Φ α ( z 1 ) \Phi_\alpha(z_2)\ge\Phi_\alpha(z_1) Φ α ( z 2 ) ≥ Φ α ( z 1 ) Φ α ′ ( z 2 ) > Φ α ′ ( z 1 ) \Phi_{\alpha'}(z_2)>\Phi_{\alpha'}(z_1) Φ α ′ ( z 2 ) > Φ α ′ ( z 1 ) z 1 z_1 z 1 Φ α ′ \Phi_{\alpha'} Φ α ′ ζ \zeta ζ
Next, we show that ζ \zeta ζ α 0 > 0 \alpha_0>0 α 0 > 0 ζ \zeta ζ z + = lim α ↓ α 0 ζ ( α ) z^+=\lim_{\alpha\downarrow\alpha_0}\zeta(\alpha) z + = lim α ↓ α 0 ζ ( α ) z + ≥ ζ ( α 0 ) z^+\ge\zeta(\alpha_0) z + ≥ ζ ( α 0 ) z + ≤ ζ ( α 0 ) z^+\le\zeta(\alpha_0) z + ≤ ζ ( α 0 ) z + z^+ z + Φ α 0 \Phi_{\alpha_0} Φ α 0 y ∈ [ 0 , 1 ] y\in[0,1] y ∈ [ 0 , 1 ] α > α 0 \alpha>\alpha_0 α > α 0 ζ ( α ) \zeta(\alpha) ζ ( α ) Φ α \Phi_\alpha Φ α
Φ α ( ζ ( α ) ) ≥ Φ α ( y ) . \Phi_\alpha(\zeta(\alpha))\ge\Phi_\alpha(y). Φ α ( ζ ( α )) ≥ Φ α ( y ) . Let α ↓ α 0 \alpha\downarrow\alpha_0 α ↓ α 0 y y y Φ α ( y ) = e − α P ′ ( y ) − α H ( y ) \Phi_\alpha(y)=e^{-\alpha P'(y)}-\alpha H(y) Φ α ( y ) = e − α P ′ ( y ) − α H ( y ) α \alpha α Φ α ( y ) → Φ α 0 ( y ) \Phi_\alpha(y)\to\Phi_{\alpha_0}(y) Φ α ( y ) → Φ α 0 ( y ) α \alpha α ζ ( α ) \zeta(\alpha) ζ ( α ) ( α , ζ ( α ) ) → ( α 0 , z + ) (\alpha,\zeta(\alpha))\to(\alpha_0,z^+) ( α , ζ ( α )) → ( α 0 , z + ) P ′ P' P ′ H H H ( α , z ) ↦ e − α P ′ ( z ) − α H ( z ) (\alpha,z)\mapsto e^{-\alpha P'(z)}-\alpha H(z) ( α , z ) ↦ e − α P ′ ( z ) − α H ( z ) Φ α ( ζ ( α ) ) → Φ α 0 ( z + ) \Phi_\alpha(\zeta(\alpha))\to\Phi_{\alpha_0}(z^+) Φ α ( ζ ( α )) → Φ α 0 ( z + ) α > α 0 \alpha>\alpha_0 α > α 0 Φ α 0 ( z + ) ≥ Φ α 0 ( y ) \Phi_{\alpha_0}(z^+)\ge\Phi_{\alpha_0}(y) Φ α 0 ( z + ) ≥ Φ α 0 ( y ) y ∈ [ 0 , 1 ] y\in[0,1] y ∈ [ 0 , 1 ] z + z^+ z + Φ α 0 \Phi_{\alpha_0} Φ α 0 Φ α 0 \Phi_{\alpha_0} Φ α 0 ζ ( α 0 ) \zeta(\alpha_0) ζ ( α 0 ) z + ≤ ζ ( α 0 ) z^+\le\zeta(\alpha_0) z + ≤ ζ ( α 0 ) z + ≥ ζ ( α 0 ) z^+\ge\zeta(\alpha_0) z + ≥ ζ ( α 0 ) lim α ↓ α 0 ζ ( α ) = ζ ( α 0 ) \lim_{\alpha\downarrow\alpha_0}\zeta(\alpha)=\zeta(\alpha_0) lim α ↓ α 0 ζ ( α ) = ζ ( α 0 )
We now show that ζ ( α ) → 0 \zeta(\alpha)\to0 ζ ( α ) → 0 α ↓ 0 \alpha\downarrow0 α ↓ 0 x ≥ 0 x\ge0 x ≥ 0 1 − x ≤ e − x ≤ 1 − x + x 2 / 2 1-x\le e^{-x}\le1-x+x^2/2 1 − x ≤ e − x ≤ 1 − x + x 2 /2 x = α P ′ ( z ) ∈ [ 0 , α P ′ ( 1 ) ] x=\alpha P'(z)\in[0,\alpha P'(1)] x = α P ′ ( z ) ∈ [ 0 , α P ′ ( 1 )]
e − α P ′ ( z ) = 1 − α P ′ ( z ) + r α ( z ) e^{-\alpha P'(z)}=1-\alpha P'(z)+r_\alpha(z) e − α P ′ ( z ) = 1 − α P ′ ( z ) + r α ( z ) with
0 ≤ r α ( z ) ≤ α 2 ( P ′ ( z ) ) 2 2 ≤ α 2 ( P ′ ( 1 ) ) 2 2 0\le r_\alpha(z)\le\frac{\alpha^2(P'(z))^2}{2}\le\frac{\alpha^2(P'(1))^2}{2} 0 ≤ r α ( z ) ≤ 2 α 2 ( P ′ ( z ) ) 2 ≤ 2 α 2 ( P ′ ( 1 ) ) 2 for all z ∈ [ 0 , 1 ] z\in[0,1] z ∈ [ 0 , 1 ] P ′ ( z ) + H ( z ) = 1 − P ( z ) + z P ′ ( z ) P'(z)+H(z)=1-P(z)+zP'(z) P ′ ( z ) + H ( z ) = 1 − P ( z ) + z P ′ ( z )
Φ α ( z ) = 1 − α g ( z ) + r α ( z ) , \Phi_\alpha(z)=1-\alpha g(z)+r_\alpha(z), Φ α ( z ) = 1 − α g ( z ) + r α ( z ) , with
g ( z ) = 1 − P ( z ) + z P ′ ( z ) . g(z)=1-P(z)+zP'(z). g ( z ) = 1 − P ( z ) + z P ′ ( z ) . The function g g g [ 0 , 1 ] [0,1] [ 0 , 1 ] g ′ ( z ) = z P ′ ′ ( z ) > 0 g'(z)=zP''(z)>0 g ′ ( z ) = z P ′′ ( z ) > 0 0 < z ≤ 1 0<z\le1 0 < z ≤ 1 ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) z ≥ ϵ z\ge\epsilon z ≥ ϵ
Φ α ( z ) − Φ α ( 0 ) = − α ( g ( z ) − g ( 0 ) ) + r α ( z ) − r α ( 0 ) ≤ − α ( g ( ϵ ) − g ( 0 ) ) + α 2 ( P ′ ( 1 ) ) 2 2 , \begin{aligned}
\Phi_\alpha(z)-\Phi_\alpha(0)=-\alpha(g(z)-g(0))+r_\alpha(z)-r_\alpha(0) \\
&\le-\alpha(g(\epsilon)-g(0))+\frac{\alpha^2(P'(1))^2}{2},
\end{aligned} Φ α ( z ) − Φ α ( 0 ) = − α ( g ( z ) − g ( 0 )) + r α ( z ) − r α ( 0 ) ≤ − α ( g ( ϵ ) − g ( 0 )) + 2 α 2 ( P ′ ( 1 ) ) 2 , where the inequality uses g ( z ) ≥ g ( ϵ ) g(z)\ge g(\epsilon) g ( z ) ≥ g ( ϵ ) r α ( z ) ≤ α 2 ( P ′ ( 1 ) ) 2 / 2 r_\alpha(z)\le\alpha^2(P'(1))^2/2 r α ( z ) ≤ α 2 ( P ′ ( 1 ) ) 2 /2 r α ( 0 ) ≥ 0 r_\alpha(0)\ge0 r α ( 0 ) ≥ 0 g ( ϵ ) > g ( 0 ) g(\epsilon)>g(0) g ( ϵ ) > g ( 0 )
0 < α < 2 ( g ( ϵ ) − g ( 0 ) ) ( P ′ ( 1 ) ) 2 . 0<\alpha<\frac{2(g(\epsilon)-g(0))}{(P'(1))^2}. 0 < α < ( P ′ ( 1 ) ) 2 2 ( g ( ϵ ) − g ( 0 )) . For such α \alpha α z ≥ ϵ z\ge\epsilon z ≥ ϵ Φ α ( z ) < Φ α ( 0 ) \Phi_\alpha(z)<\Phi_\alpha(0) Φ α ( z ) < Φ α ( 0 ) z ≥ ϵ z\ge\epsilon z ≥ ϵ Φ α \Phi_\alpha Φ α ζ ( α ) < ϵ \zeta(\alpha)<\epsilon ζ ( α ) < ϵ ϵ \epsilon ϵ ζ ( α ) → 0 \zeta(\alpha)\to0 ζ ( α ) → 0 α ↓ 0 \alpha\downarrow0 α ↓ 0
Finally, we show that ζ ( α ) → 1 \zeta(\alpha)\to1 ζ ( α ) → 1 α → ∞ \alpha\to\infty α → ∞ z ∈ [ 0 , 1 ] z\in[0,1] z ∈ [ 0 , 1 ]
Φ α ( z ) α = e − α P ′ ( z ) α − H ( z ) , \frac{\Phi_\alpha(z)}{\alpha}=\frac{e^{-\alpha P'(z)}}{\alpha}-H(z), α Φ α ( z ) = α e − α P ′ ( z ) − H ( z ) , where
0 < e − α P ′ ( z ) α ≤ 1 α , 0<\frac{e^{-\alpha P'(z)}}{\alpha}\le\frac{1}{\alpha}, 0 < α e − α P ′ ( z ) ≤ α 1 , since P ′ ( z ) ≥ 0 P'(z)\ge0 P ′ ( z ) ≥ 0 H ′ ( z ) = − ( 1 − z ) P ′ ′ ( z ) < 0 H'(z)=-(1-z)P''(z)<0 H ′ ( z ) = − ( 1 − z ) P ′′ ( z ) < 0 0 < z < 1 0<z<1 0 < z < 1 H H H [ 0 , 1 ] [0,1] [ 0 , 1 ] H ( 1 ) = 1 − P ( 1 ) = 0 H(1)=1-P(1)=0 H ( 1 ) = 1 − P ( 1 ) = 0 ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) z ≤ 1 − ϵ z\le1-\epsilon z ≤ 1 − ϵ H ( z ) ≥ H ( 1 − ϵ ) H(z)\ge H(1-\epsilon) H ( z ) ≥ H ( 1 − ϵ )
Φ α ( z ) α − Φ α ( 1 ) α = e − α P ′ ( z ) α − H ( z ) − e − α P ′ ( 1 ) α + H ( 1 ) < 1 α − H ( 1 − ϵ ) , \begin{aligned}
\frac{\Phi_\alpha(z)}{\alpha}-\frac{\Phi_\alpha(1)}{\alpha}
=\frac{e^{-\alpha P'(z)}}{\alpha}-H(z)-\frac{e^{-\alpha P'(1)}}{\alpha}+H(1) \\
&<\frac{1}{\alpha}-H(1-\epsilon),
\end{aligned} α Φ α ( z ) − α Φ α ( 1 ) = α e − α P ′ ( z ) − H ( z ) − α e − α P ′ ( 1 ) + H ( 1 ) < α 1 − H ( 1 − ϵ ) , where the inequality uses e − α P ′ ( 1 ) / α > 0 e^{-\alpha P'(1)}/\alpha>0 e − α P ′ ( 1 ) / α > 0 H ( 1 ) = 0 H(1)=0 H ( 1 ) = 0 H ( 1 − ϵ ) > H ( 1 ) = 0 H(1-\epsilon)>H(1)=0 H ( 1 − ϵ ) > H ( 1 ) = 0 α ≥ 1 / H ( 1 − ϵ ) \alpha\ge1/H(1-\epsilon) α ≥ 1/ H ( 1 − ϵ ) α \alpha α z ≤ 1 − ϵ z\le1-\epsilon z ≤ 1 − ϵ Φ α ( z ) < Φ α ( 1 ) \Phi_\alpha(z)<\Phi_\alpha(1) Φ α ( z ) < Φ α ( 1 ) z ≤ 1 − ϵ z\le1-\epsilon z ≤ 1 − ϵ Φ α \Phi_\alpha Φ α ζ ( α ) > 1 − ϵ \zeta(\alpha)>1-\epsilon ζ ( α ) > 1 − ϵ ϵ \epsilon ϵ ζ ( α ) → 1 \zeta(\alpha)\to1 ζ ( α ) → 1 α → ∞ \alpha\to\infty α → ∞ □ \square □
Proof of Lemma 10. To prove (15), we split the levels z ∈ ( 0 , 1 ) z \in(0,1) z ∈ ( 0 , 1 ) ζ \zeta ζ ζ \zeta ζ α 0 \alpha_0 α 0 z − = lim α ↑ α 0 ζ ( α ) z^- = \lim_{\alpha\uparrow\alpha_0} \zeta(\alpha) z − = lim α ↑ α 0 ζ ( α ) ζ \zeta ζ z + = ζ ( α 0 ) z^+ = \zeta(\alpha_0) z + = ζ ( α 0 ) z − < z + z^- < z^+ z − < z + ( z − , z + ) (z^-,z^+) ( z − , z + ) jump interval (note that distinct jump intervals are disjoint since ζ \zeta ζ C C C z ∈ ( 0 , 1 ) z \in(0,1) z ∈ ( 0 , 1 ) ζ \zeta ζ z ∈ C z \in C z ∈ C ζ ( σ ( z ) ) = z \zeta(\sigma(z)) = z ζ ( σ ( z )) = z z = ζ ( α 1 ) z = \zeta(\alpha_1) z = ζ ( α 1 ) α 1 > 0 \alpha_1 > 0 α 1 > 0 σ ( z ) ≤ α 1 \sigma(z) \le\alpha_1 σ ( z ) ≤ α 1 σ ( z ) \sigma(z) σ ( z ) ζ ( σ ( z ) ) ≤ ζ ( α 1 ) = z \zeta(\sigma(z)) \le\zeta(\alpha_1) = z ζ ( σ ( z )) ≤ ζ ( α 1 ) = z ζ \zeta ζ ζ ( σ ( z ) ) ≥ z \zeta(\sigma(z)) \ge z ζ ( σ ( z )) ≥ z z ∈ ( 0 , 1 ) ∖ C z \in(0,1) \setminus C z ∈ ( 0 , 1 ) ∖ C ζ ( σ ( z ) ) ≥ z \zeta(\sigma(z)) \ge z ζ ( σ ( z )) ≥ z ζ ( σ ( z ) ) ≠ z \zeta(\sigma(z)) \ne z ζ ( σ ( z )) = z z z z ζ ( σ ( z ) ) > z \zeta(\sigma(z)) > z ζ ( σ ( z )) > z ζ ( α ) < z \zeta(\alpha) < z ζ ( α ) < z α < σ ( z ) \alpha< \sigma(z) α < σ ( z ) lim α ↑ σ ( z ) ζ ( α ) ≤ z \lim_{\alpha\uparrow\sigma(z)} \zeta(\alpha) \le z lim α ↑ σ ( z ) ζ ( α ) ≤ z σ ( z ) \sigma(z) σ ( z ) z z z [ z − , z + ) [z^-,z^+) [ z − , z + ) ( z − , z + ) (z^-,z^+) ( z − , z + )
Since there are at most countably many discontinuity points, the set of endpoints of jump intervals is countable, so it has measure zero and does not affect the integrals over z z z ζ \zeta ζ C C C ( 0 , 1 ) (0,1) ( 0 , 1 ) C C C
Let z ∈ C z \in C z ∈ C ζ ( α ) \zeta(\alpha) ζ ( α ) Φ α \Phi_\alpha Φ α α > 0 \alpha> 0 α > 0 z = ζ ( σ ( z ) ) z = \zeta(\sigma(z)) z = ζ ( σ ( z )) Φ σ ( z ) \Phi_{\sigma(z)} Φ σ ( z ) 0 < z < 1 0 < z < 1 0 < z < 1 α P ′ ( z ) = − log ( 1 − z ) \alpha P'(z) = -\log(1-z) α P ′ ( z ) = − log ( 1 − z ) α = σ ( z ) > 0 \alpha= \sigma(z) > 0 α = σ ( z ) > 0
σ ( z ) P ′ ( z ) = − log ( 1 − z ) . (25) \sigma(z)P'(z) = -\log(1-z). \tag*{(25)} σ ( z ) P ′ ( z ) = − log ( 1 − z ) . (25) Now consider a jump interval ( z − , z + ) (z^-,z^+) ( z − , z + ) α 0 \alpha_0 α 0 σ ( z ) = α 0 \sigma(z) = \alpha_0 σ ( z ) = α 0 z ∈ ( z − , z + ) z \in(z^-,z^+) z ∈ ( z − , z + ) α < α 0 \alpha< \alpha_0 α < α 0 ζ ( α ) ≤ z − < z \zeta(\alpha) \le z^- < z ζ ( α ) ≤ z − < z ζ ( α 0 ) = z + > z \zeta(\alpha_0) = z^+ > z ζ ( α 0 ) = z + > z α 0 \alpha_0 α 0 α \alpha α ζ ( α ) ≥ z \zeta(\alpha) \ge z ζ ( α ) ≥ z σ ( z ) = α 0 \sigma(z) = \alpha_0 σ ( z ) = α 0
Next, we show that both endpoints maximize Φ α 0 \Phi_{\alpha_0} Φ α 0 z + = ζ ( α 0 ) z^+ = \zeta(\alpha_0) z + = ζ ( α 0 ) Φ α 0 \Phi_{\alpha_0} Φ α 0 z − z^- z − y ∈ [ 0 , 1 ] y \in[0,1] y ∈ [ 0 , 1 ] α < α 0 \alpha< \alpha_0 α < α 0 Φ α ( ζ ( α ) ) ≥ Φ α ( y ) \Phi_\alpha(\zeta(\alpha)) \ge\Phi_\alpha(y) Φ α ( ζ ( α )) ≥ Φ α ( y ) ζ ( α ) \zeta(\alpha) ζ ( α ) Φ α \Phi_\alpha Φ α α ↑ α 0 \alpha\uparrow\alpha_0 α ↑ α 0 Φ α ( z ) \Phi_\alpha(z) Φ α ( z ) ( α , z ) (\alpha,z) ( α , z ) Φ α 0 ( z − ) ≥ Φ α 0 ( y ) \Phi_{\alpha_0}(z^-) \ge\Phi_{\alpha_0}(y) Φ α 0 ( z − ) ≥ Φ α 0 ( y ) z z z Φ α 0 \Phi_{\alpha_0} Φ α 0 z < 1 z < 1 z < 1 1 − z = e − α 0 P ′ ( z ) 1-z = e^{-\alpha_0P'(z)} 1 − z = e − α 0 P ′ ( z )
α 0 P ′ ( z ) = − log ( 1 − z ) , z ∈ { z − , z + } . (26) \alpha_0P'(z) = -\log(1-z), \qquad z \in\{z^-,z^+\}. \tag*{(26)} α 0 P ′ ( z ) = − log ( 1 − z ) , z ∈ { z − , z + } . (26) Finally, we compare the values of Φ α 0 \Phi_{\alpha_0} Φ α 0 z ∈ [ 0 , 1 ) z \in[0,1) z ∈ [ 0 , 1 )
Ψ ( z ) = z + ( 1 − z ) log ( 1 − z ) − α 0 P ( z ) . \Psi(z) = z + (1-z)\log(1-z) - \alpha_0P(z). Ψ ( z ) = z + ( 1 − z ) log ( 1 − z ) − α 0 P ( z ) . At each z ∈ { z − , z + } z \in\{z^-,z^+\} z ∈ { z − , z + } e − α 0 P ′ ( z ) = 1 − z e^{-\alpha_0P'(z)} = 1-z e − α 0 P ′ ( z ) = 1 − z α 0 P ′ ( z ) = − log ( 1 − z ) \alpha_0P'(z) = -\log(1-z) α 0 P ′ ( z ) = − log ( 1 − z ) Φ α 0 \Phi_{\alpha_0} Φ α 0
Φ α 0 ( z ) = e − α 0 P ′ ( z ) − α 0 ( 1 − P ( z ) − ( 1 − z ) P ′ ( z ) ) = ( 1 − z ) − α 0 + α 0 P ( z ) − ( 1 − z ) log ( 1 − z ) = 1 − α 0 − Ψ ( z ) . \begin{aligned}
\Phi_{\alpha_0}(z) &= e^{-\alpha_0P'(z)}-\alpha_0\bigl(1-P(z)-(1-z)P'(z)\bigr)\\
&=(1-z)-\alpha_0+\alpha_0P(z)-(1-z)\log(1-z)\\
&=1-\alpha_0-\Psi(z).
\end{aligned} Φ α 0 ( z ) = e − α 0 P ′ ( z ) − α 0 ( 1 − P ( z ) − ( 1 − z ) P ′ ( z ) ) = ( 1 − z ) − α 0 + α 0 P ( z ) − ( 1 − z ) log ( 1 − z ) = 1 − α 0 − Ψ ( z ) . Since both endpoints maximize Φ α 0 \Phi_{\alpha_0} Φ α 0 Φ α 0 ( z − ) = Φ α 0 ( z + ) \Phi_{\alpha_0}(z^-) = \Phi_{\alpha_0}(z^+) Φ α 0 ( z − ) = Φ α 0 ( z + ) Ψ ( z − ) = Ψ ( z + ) \Psi(z^-) = \Psi(z^+) Ψ ( z − ) = Ψ ( z + )
Moreover,
Ψ ′ ( z ) = − log ( 1 − z ) − α 0 P ′ ( z ) , \Psi'(z)=-\log(1-z)-\alpha_0P'(z), Ψ ′ ( z ) = − log ( 1 − z ) − α 0 P ′ ( z ) , and Ψ \Psi Ψ [ z − , z + ] ⊂ [ 0 , 1 ) [z^-,z^+] \subset[0,1) [ z − , z + ] ⊂ [ 0 , 1 )
0 = Ψ ( z + ) − Ψ ( z − ) = ∫ z − z + Ψ ′ ( z ) d z , 0=\Psi(z^+)-\Psi(z^-)=\int_{z^-}^{z^+}\Psi'(z)\,dz, 0 = Ψ ( z + ) − Ψ ( z − ) = ∫ z − z + Ψ ′ ( z ) d z , that is,
∫ z − z + − log ( 1 − z ) d z = α 0 ∫ z − z + P ′ ( z ) d z . (27) \int_{z^-}^{z^+}-\log(1-z)\,dz=\alpha_0\int_{z^-}^{z^+}P'(z)\,dz. \tag*{(27)} ∫ z − z + − log ( 1 − z ) d z = α 0 ∫ z − z + P ′ ( z ) d z . (27) We now combine (25) and (27). For z ∈ C z \in C z ∈ C − log ( 1 − z ) / σ ( z ) = P ′ ( z ) -\log(1-z)/\sigma(z)=P'(z) − log ( 1 − z ) / σ ( z ) = P ′ ( z ) ( z − , z + ) (z^-,z^+) ( z − , z + ) α 0 \alpha_0 α 0 σ ( z ) = α 0 \sigma(z)=\alpha_0 σ ( z ) = α 0 α 0 \alpha_0 α 0 ∫ z − z + − log ( 1 − z ) / σ ( z ) d z = ∫ z − z + P ′ ( z ) d z \int_{z^-}^{z^+}-\log(1-z)/\sigma(z)\,dz=\int_{z^-}^{z^+}P'(z)\,dz ∫ z − z + − log ( 1 − z ) / σ ( z ) d z = ∫ z − z + P ′ ( z ) d z C C C P ( 0 ) = 0 P(0)=0 P ( 0 ) = 0 P ( 1 ) = 1 P(1)=1 P ( 1 ) = 1
∫ 0 1 − log ( 1 − z ) σ ( z ) d z = ∫ 0 1 P ′ ( z ) d z = P ( 1 ) − P ( 0 ) = 1. \int_0^1\frac{-\log(1-z)}{\sigma(z)}\,dz=\int_0^1P'(z)\,dz=P(1)-P(0)=1. ∫ 0 1 σ ( z ) − log ( 1 − z ) d z = ∫ 0 1 P ′ ( z ) d z = P ( 1 ) − P ( 0 ) = 1. 