Lemma 5 ([Row counts]). For every fixed ρ,w>0 , with probability 1-(-Ω_ρ,w (n²)) , fewer than ρn rows of A_n^ (p) have a number of positive entries outside [pn-wn,pn+wn] .

Proposition 4 ([Column estimate]). For every fixed L_0≥1 and every sufficiently small fixed e₀>0 , a matrix B in the bit model of size m=N-1 satisfies, for all sufficiently large N , ( B is nonsingular and | S_L₀ (B)|>2^e_0N ) ≤2^…

Lemma 3. Fix an index a₀ and condition on its entire row in A_n^ (p) . There is a symmetric bit matrix M of size N=n-1 with the following properties: the entries on and above its diagonal are independent, and each has success probability …

CredibilityNo verdicts yetView chain graph →

If at least ρn rows fail, at least half fail in the same direction. Choose a set I of k=ρn/3 such rows, for all sufficiently large n ; it suffices to consider ρ<1 . The sum of their positive-entry counts is a sum of independent upper-triangular Bernoulli variables with coefficients one or two. Its mean is pkn , and its coefficients have squared sum at most 2kn . The common-direction deviation is at least kwn . Hoeffding's inequality bounds this probability by 2(-kw^2n) . There are at most 2^n sets I and two directions, giving the assertion.

Comment0

No comments yet. Found a flaw? Be the first to point it out.

Lemma 5 ([Row counts]). For every fixed ρ,w>0 , with probability 1-(-Ωρ,w (n2)) , fewer than ρn rows of An^ (p) have a number of positive entries outside [pn-wn,pn+wn] .

Proposition 4 ([Column estimate]). For every fixed L0≥1 and every sufficiently small fixed e0>0 , a matrix B in the bit model of size m=N-1 satisfies, for all sufficiently large N , ( B is nonsingular and | SL0 (B)|>2e0N ) ≤2…

Lemma 3. Fix an index a0 and condition on its entire row in An^ (p) . There is a symmetric bit matrix M of size N=n-1 with the following properties: the entries on and above its diagonal are independent, and each has success probability …

Comment0

Lemma 5 ([Row counts]). For every fixed ρ,w>0 , with probability 1-(-Ω_ρ,w (n²)) , fewer than ρn rows of A_n^ (p) have a number of positive entries outside [pn-wn,pn+wn] .

Proposition 4 ([Column estimate]). For every fixed L_0≥1 and every sufficiently small fixed e₀>0 , a matrix B in the bit model of size m=N-1 satisfies, for all sufficiently large N , ( B is nonsingular and | S_L₀ (B)|>2^e_0N ) ≤2^…

Lemma 3. Fix an index a₀ and condition on its entire row in A_n^ (p) . There is a symmetric bit matrix M of size N=n-1 with the following properties: the entries on and above its diagonal are independent, and each has success probability …