이 정리는 Lemma1의 세 가지 조건 중 첫 번째 조건이 성립함을 보이는 정리이다. 증명에 앞서 각각의 용어들에 대해 정의하자. D ( ϵ n , P n , d ) D ( ϵ n , P n , d ) P n P n ϵ n ϵ n
P n = { f Σ : ∣ s ( Σ , δ n ) ∣ ≤ s n , ζ − 1 ≤ λ m i n ( Σ ) ≤ λ m a x ( Σ ) ≤ ζ , ∣ ∣ Σ ∣ ∣ m a x ≤ L n } P n = { f Σ : ∣ s ( Σ , δ n ) ∣ ≤ s n , ζ − 1 ≤ λ min ( Σ ) ≤ λ ma x ( Σ ) ≤ ζ , ∣∣Σ∣ ∣ ma x ≤ L n }
U ( δ n , s n , L n , ζ ) = { Σ ∈ c p : ∣ s ( Σ , δ n ) ∣ ≤ s n , ζ − 1 ≤ λ m i n ( Σ ) ≤ λ m a x ( Σ ) ≤ ζ , ∣ ∣ Σ ∣ ∣ m a x ≤ L n } U ( δ n , s n , L n , ζ ) = { Σ ∈ c p : ∣ s ( Σ , δ n ) ∣ ≤ s n , ζ − 1 ≤ λ min ( Σ ) ≤ λ ma x ( Σ ) ≤ ζ , ∣∣Σ∣ ∣ ma x ≤ L n }
s 0 s 0
ϵ n { ( p + s 0 ) l n p n } 1 2 ϵ n = def { n ( p + s 0 ) l n p } 2 1
라고 정의하자. 최종적으로는, l n D ( ϵ n , P n , d ) ≤ ( 12 + 1 / β ) c 1 n ϵ n 2 l n D ( ϵ n , P n , d ) ≤ ( 12 + 1/ β ) c 1 n ϵ n 2
[Lemma3](Lemma A.1 in [6])
If P Ω k P Ω k N p ( 0 , Ω k − 1 ) N p ( 0 , Ω k − 1 ) Ω k ∈ μ 0 + Ω k ∈ μ 0 + d i d i A = Σ 1 − 1 / 2 Σ 2 Σ 1 − 1 / 2 A = Σ 1 − 1/2 Σ 2 Σ 1 − 1/2 δ > 0 δ > 0 c o > 0 c o > 0
c 0 − 1 ∣ ∣ Σ 1 − Σ 2 ∣ ∣ 2 2 ≤ ∑ i = 1 p ∣ d i − 1 ∣ 2 ≤ c o ∣ ∣ Σ 1 − Σ 2 ∣ ∣ 2 2 c 0 − 1 ∣∣ Σ 1 − Σ 2 ∣ ∣ 2 2 ≤ ∑ i = 1 p ∣ d i − 1 ∣ 2 ≤ c o ∣∣ Σ 1 − Σ 2 ∣ ∣ 2 2 h ( p Ω 1 , p Ω 2 ) < δ h ( p Ω 1 , p Ω 2 ) < δ max i ∣ d i − 1 ∣ < 1 i max ∣ d i − 1∣ < 1 ∣ ∣ Ω 1 − Ω 2 ∣ ∣ 2 ≤ c o h 2 ( p Ω 1 , p Ω 2 ) ∣∣ Ω 1 − Ω 2 ∣ ∣ 2 ≤ c o h 2 ( p Ω 1 , p Ω 2 ) h 2 ( p Ω 1 , p Ω 2 ) ≤ c o ∣ ∣ Ω 1 − Ω 2 ∣ ∣ 2 2 h 2 ( p Ω 1 , p Ω 2 ) ≤ c o ∣∣ Ω 1 − Ω 2 ∣ ∣ 2 2
여기서, h ( ) h ( ) d ( ) d ( )
따라서, lemma3-(3)에 의해,d ( f Σ 1 , f Σ 2 ) ≤ c ζ ∣ ∣ Ω 1 − Ω 2 ∣ ∣ F d ( f Σ 1 , f Σ 2 ) ≤ c ζ ∣∣ Ω 1 − Ω 2 ∣ ∣ F Ω Ω Σ − 1 Σ − 1
위 lemma3-(3)과 우리 논문의 lemma5를 통해, Ω 1 = Σ 1 − 1 Σ 1 Σ 1 − 1 Ω 1 = Σ 1 − 1 Σ 1 Σ 1 − 1 d ( f Σ 1 , f Σ 2 ) ≤ C ζ 3 ∣ ∣ Σ 1 − Σ 2 ∣ ∣ F d ( f Σ 1 , f Σ 2 ) ≤ C ζ 3 ∣∣ Σ 1 − Σ 2 ∣ ∣ F
ϵ ϵ d ( f Σ i , f Σ j ) ≥ ϵ n d ( f Σ i , f Σ j ) ≥ ϵ n ∣ ∣ Σ 1 − Σ 2 ∣ ∣ F ≥ ϵ n C ζ 3 ∣∣ Σ 1 − Σ 2 ∣ ∣ F ≥ C ζ 3 ϵ n P n P n U ( δ n , s n , L n , ζ ) U ( δ n , s n , L n , ζ )
l n D ( ϵ n , P n , d ) ≤ l n D ( ϵ n C ζ 3 , U ( δ n , s n , L n , ζ ) , ∣ ∣ ⋅ ∣ ∣ F ) ≤ l n { ( L n p + j ϵ n C ζ 3 ) p ∑ j = 1 s n ( p + j 1 2 L n ϵ n C ζ 3 ) j ( p 2 j ) } l n D ( ϵ n , P n , d ) ≤ l n D ( C ζ 3 ϵ n , U ( δ n , s n , L n , ζ ) , ∣∣ ⋅ ∣ ∣ F ) ≤ l n ⎩ ⎨ ⎧ ( C ζ 3 ϵ n L n p + j ) p j = 1 ∑ s n ( C ζ 3 ϵ n p + j 2 1 L n ) j ( j 2 p ) ⎭ ⎬ ⎫
여기서, p + j p + j 1 2 2 1 ( L n p + j ϵ n C ζ 3 ) ( C ζ 3 ϵ n L n p + j ) j ≤ s n ≤ p 2 j ≤ s n ≤ p 2 L n p + j ϵ n C ζ 3 ≤ 2 p ζ 3 L n ϵ n C ζ 3 ϵ n L n p + j ≤ ϵ n 2 p ζ 3 L n
l n { ( L n p + j ϵ n C ζ 3 ) p ∑ j = 1 s n ( p + j 1 2 L n ϵ n C ζ 3 ) j ( p 2 j ) } = l n { ( 2 p C ζ 3 L n ϵ n ) p ∑ j = 1 s n ( 2 C ζ 3 L n p ϵ n ) j ( p 2 j ) } = l n [ ( ( 2 p ) p ( 2 p ) s n ) ( C ζ 3 L n ϵ n ) p ∑ j = 1 s n ( C ζ 3 L n ϵ n ) j ( p 2 j ) ] = p l n 2 + p l n p + s n ( 1 2 l n 2 + l n p ) + p l n ( C L n ζ 3 ϵ n ) + l n ( ∑ j = 1 s n ( 2 C L n ζ 3 ϵ n ) ( p 2 2 ) j ) ≤ p l n 2 + p l n p + s n ( 1 2 l n 2 + l n p ) + p l n ( C L n ζ 3 ϵ n ) + s n l n ( 2 C L n ζ 3 p 2 ϵ n ) ≤ p l n 2 + p l n p + 1 2 s n l n 2 + s n l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n 1 ϵ n + 2 s n l n p l n ⎩ ⎨ ⎧ ( C ζ 3 ϵ n L n p + j ) p j = 1 ∑ s n ( C ζ 3 ϵ n p + j 2 1 L n ) j ( j 2 p ) ⎭ ⎬ ⎫ = l n ⎩ ⎨ ⎧ ( ϵ n 2 pC ζ 3 L n ) p j = 1 ∑ s n ( ϵ n 2 C ζ 3 L n p ) j ( j 2 p ) ⎭ ⎬ ⎫ = l n [ (( 2 p ) p ( 2 p ) s n ) ( ϵ n C ζ 3 L n ) p j = 1 ∑ s n ( ϵ n C ζ 3 L n ) j ( j 2 p ) ] = pl n 2 + pl n p + s n ( 2 1 l n 2 + l n p ) + pl n ( ϵ n C L n ζ 3 ) + l n ( j = 1 ∑ s n ( ϵ n 2 C L n ζ 3 ) ( 2 p 2 ) j ) ≤ pl n 2 + pl n p + s n ( 2 1 l n 2 + l n p ) + pl n ( ϵ n C L n ζ 3 ) + s n l n ( ϵ n 2 C L n ζ 3 p 2 ) ≤ pl n 2 + pl n p + 2 1 s n l n 2 + s n l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n ϵ n 1 + 2 s n l n p
에서 적절한 상수를 곱해주면,
≤ 2 ( p + s n ) l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n 1 ϵ n + 2 s n l n p ≤ 2 ( p + s n ) l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n ϵ n 1 + 2 s n l n p
이다. 먼저, ( p + s n ) l n ( 2 C L n ) ≤ 6 s n l n p ( p + s n ) l n ( 2 C L n ) ≤ 6 s n l n p s n , ϵ n , L n s n , ϵ n , L n s n = c 1 ( p + s 0 ) s n = c 1 ( p + s 0 ) p + s n = ( 1 + c 1 ) p + c 1 s 0 p + s n = ( 1 + c 1 ) p + c 1 s 0 2 C L n = 2 c 2 n ϵ n 2 2 C L n = 2 c 2 n ϵ n 2
( p + s n ) l n ( 2 C L n ) = ( ( c 1 + 1 ) + c 1 s 0 ) l n 2 c 2 n ϵ n 2 = ( ( c 1 + 1 ) p + c 1 s 0 ) l n 2 c 2 ( p + s 0 ) l n p ( p + s n ) l n ( 2 C L n ) = (( c 1 + 1 ) + c 1 s 0 ) l n 2 c 2 n ϵ n 2 = (( c 1 + 1 ) p + c 1 s 0 ) l n 2 c 2 ( p + s 0 ) l n p
이다. c 1 > 1 c 1 > 1
( ( c 1 + 1 ) + c 1 s 0 ) l n 2 c 2 n ϵ n 2 ≤ 2 c 1 ( p + s 0 ) l n ( 2 c 2 ( p + s 0 ) l n p ) (( c 1 + 1 ) + c 1 s 0 ) l n 2 c 2 n ϵ n 2 ≤ 2 c 1 ( p + s 0 ) l n ( 2 c 2 ( p + s 0 ) l n p )
이다. 한편, s 0 s 0 s o ≤ p 2 s o ≤ p 2 p 3 p 3 2 c 2 ( p + s 0 ) l n p < p 3 2 c 2 ( p + s 0 ) l n p < p 3
( p + s n ) l n ( 2 C L n ) ≤ 2 c 1 ( p + s 0 ) l n p 3 = 6 s n l n p ( p + s n ) l n ( 2 C L n ) ≤ 2 c 1 ( p + s 0 ) l n p 3 = 6 s n l n p
부등식을 얻을 수 있다.
2 ( p + s n ) l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n 1 ϵ n + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + ( p + s 0 ) l n ζ 3 + ( p + s n ) l n ( 1 ϵ n ) + 2 s n l n p 2 ( p + s n ) l n p + ( p + s n ) l n ( 2 C L n ) + ( p + s n ) l n ζ 3 + ( p + s n ) l n ϵ n 1 + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + ( p + s 0 ) l n ζ 3 + ( p + s n ) l n ( ϵ n 1 ) + 2 s n l n p
이다. 이제 ( p + s 0 ) l n ζ 3 ≤ 3 4 ( p + s n ) l n p ( p + s 0 ) l n ζ 3 ≤ 4 3 ( p + s n ) l n p
( p + s n ) l n ζ 3 = 3 4 ( p + s n ) l n ζ 4 ( p + s n ) l n ζ 3 = 4 3 ( p + s n ) l n ζ 4
인데, 가정에 의해, ζ 4 ≤ p ζ 4 ≤ p
( p + s n ) l n ζ 3 ≤ 3 4 ( p + s n ) l n p ( p + s n ) l n ζ 3 ≤ 4 3 ( p + s n ) l n p
임을 알 수 있다. 이를 대입하여 정리하면,
≤ 2 ( p + s n ) l n p + 6 s n l n p + ( p + s 0 ) l n ζ 3 + ( p + s n ) l n ( 1 ϵ n ) + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + 3 4 ( p + s n ) l n p + ( p + s n ) l n ( 1 ϵ n ) + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + ( p + s 0 ) l n ζ 3 + ( p + s n ) l n ( ϵ n 1 ) + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + 4 3 ( p + s n ) l n p + ( p + s n ) l n ( ϵ n 1 ) + 2 s n l n p
이다.ϵ n ϵ n
( p + s n ) l n ( 1 ϵ n ) = 1 2 ( p + s n ) l n n ( p + s o ) l n p ( p + s n ) l n ( ϵ n 1 ) = 2 1 ( p + s n ) l n ( p + s o ) l n p n
임을 알 수 있고,
= 1 2 β ( p + s n ) l n ( n ( p + s o ) l n p ) β = 1 2 β ( p + s n ) l n n β − 1 2 ( p + s n ) l n ( p + s 0 ) l n p ≤ 1 2 β ( p + s n ) l n n β = 1 2 β ( p + s n ) l n p = 2 β 1 ( p + s n ) l n ( ( p + s o ) l n p n ) β = 2 β 1 ( p + s n ) l n n β − 2 1 ( p + s n ) l n ( p + s 0 ) l n p ≤ 2 β 1 ( p + s n ) l n n β = 2 β 1 ( p + s n ) l n p
이다.(∵ p ≍ n β ∵ p ≍ n β
≤ 2 ( p + s n ) l n p + 6 s n l n p + 3 4 ( p + s n ) l n p + 1 2 β ( p + s n ) l n p + 2 s n l n p ≤ 2 ( p + s n ) l n p + 6 s n l n p + 4 3 ( p + s n ) l n p + 2 β 1 ( p + s n ) l n p + 2 s n l n p
이다.
≤ 6 s n l n p + 11 4 ( p + s n ) l n p + 1 2 β ( p + s n ) l n p + 2 s n l n p ( 6 + 1 2 β ) ( s n c 1 + s n ) l n p < 1 2 ( 12 + 1 β ) ( c 1 + c 1 ) n ϵ n 2 ( ∵ c 1 > 1 ) = ( 12 + 1 2 β ) c 1 n ϵ n 2 ≤ 6 s n l n p + 4 11 ( p + s n ) l n p + 2 β 1 ( p + s n ) l n p + 2 s n l n p ( 6 + 2 β 1 ) ( c 1 s n + s n ) l n p < 2 1 ( 12 + β 1 ) ( c 1 + c 1 ) n ϵ n 2 ( ∵ c 1 > 1 ) = ( 12 + 2 β 1 ) c 1 n ϵ n 2
이다. 따라서,
l n D ( ϵ n , P n , d ) ≤ ( 12 + 1 β ) c 1 n ϵ n 2 l n D ( ϵ n , P n , d ) ≤ ( 12 + β 1 ) c 1 n ϵ n 2
이 성립해서,
이 Lemma는 논문의 Theorem4 의 증명에서 활용되는 Lemma이다.
Gershgorin circle Thm에 의해, covariance matrix의 eigenvalue 들은 적어도 [ σ j j − ∑ k ≠ j ∣ σ k j ∣ , σ j j + ∑ k ≠ j ∣ σ k j ∣ ] , j ∈ { 1 , 2 , ⋯ , p } [ σ jj − k = j ∑ ∣ σ kj ∣ , σ jj + k = j ∑ ∣ σ kj ∣ ] , j ∈ { 1 , 2 , ⋯ , p }
π u ( Σ ∈ U ( ζ ) ) ≥ π u ( m i n j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) > 0 , ζ − 1 ≤ λ m i n ( Σ ) ≤ λ m a x ( Σ ) ≤ ζ ) π u ( Σ ∈ U ( ζ )) ≥ π u ( mi n j ( σ jj − k = j ∑ ∣ σ kj ∣ ) > 0 , ζ − 1 ≤ λ min ( Σ ) ≤ λ ma x ( Σ ) ≤ ζ )
임을 보이면 된다. 먼저 min j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) > 0 j min ( σ jj − k = j ∑ ∣ σ kj ∣ ) > 0 ∣ ∣ Σ ∣ ∣ 1 = max 1 ≤ j ≤ n ∑ i = 1 m ∣ a i j ∣ ∣∣Σ∣ ∣ 1 = 1 ≤ j ≤ n max i = 1 ∑ m ∣ a ij ∣
λ m a x ( Σ ) ≤ ∣ ∣ Σ ∣ ∣ 1 = max j ( σ j j + ∑ k ≠ j ∣ σ k j ∣ ) ≤ max j 2 σ j j λ ma x ( Σ ) ≤ ∣∣Σ∣ ∣ 1 = j max ( σ jj + k = j ∑ ∣ σ kj ∣ ) ≤ j max 2 σ jj
로 표현할 수 있다. 또한, G.C Thm에 의해,
λ m i n ( Σ ) ≥ min j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) λ min ( Σ ) ≥ j min ( σ jj − k = j ∑ ∣ σ kj ∣ )
로 표현할 수 있다. 따라서,ζ − 1 ≤ λ m i n ( Σ ) ≤ λ m a x ( Σ ) ≤ ζ ζ − 1 ≤ λ min ( Σ ) ≤ λ ma x ( Σ ) ≤ ζ
π u ( Σ ∈ U ( ζ ) ) ≥ π u ( ζ − 1 ≤ min j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) ≤ 2 max j σ j j ≤ ζ ) π u ( Σ ∈ U ( ζ )) ≥ π u ( ζ − 1 ≤ j min ( σ jj − k = j ∑ ∣ σ kj ∣ ) ≤ 2 j max σ jj ≤ ζ )
이고, P ( A ) ≥ P ( A ∩ B ) = P ( A ∣ B ) P ( B ) P ( A ) ≥ P ( A ∩ B ) = P ( A ∣ B ) P ( B )
π u ( ζ − 1 ≤ min j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) ≤ 2 max j σ j j ≤ ζ ) ≥ π u ( ζ − 1 ≤ min j ( σ j j − ∑ k ≠ j ∣ σ k j ∣ ) ≤ 2 max j σ j j ≤ ζ ∣ max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( ζ − 1 ≤ j min ( σ jj − k = j ∑ ∣ σ kj ∣ ) ≤ 2 j max σ jj ≤ ζ ) ≥ π u ( ζ − 1 ≤ j min ( σ jj − k = j ∑ ∣ σ kj ∣ ) ≤ 2 j max σ jj ≤ ζ ∣ k = j max ∣ σ kj ∣ < ( ζp ) − 1 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
인데, 조건부에 의해 다음 부등식이 되고,
≥ π u ( ζ − 1 ≤ min j ( σ j j − ζ − 1 ) ≤ 2 max j σ j j ≤ ζ ∣ max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) ≥ π u ( ζ − 1 ≤ j min ( σ jj − ζ − 1 ) ≤ 2 j max σ jj ≤ ζ ∣ k = j max ∣ σ kj ∣ < ( ζp ) − 1 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
에서, σ j j σ jj σ i j σ ij
= π u ( ζ − 1 ≤ min j ( σ j j − ζ − 1 ) ≤ 2 max j σ j j ≤ ζ ) π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) = π u ( ζ − 1 ≤ j min ( σ jj − ζ − 1 ) ≤ 2 j max σ jj ≤ ζ ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
이다.
π u ( Σ ∈ U ( ζ ) ) ≥ π u ( ζ − 1 ≤ min j ( σ j j − ζ − 1 ) ≤ 2 max j σ j j ≤ ζ ) ‾ ∗ π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) ‾ π u ( Σ ∈ U ( ζ )) ≥ π u ( ζ − 1 ≤ j min ( σ jj − ζ − 1 ) ≤ 2 j max σ jj ≤ ζ ) ∗ π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
먼저 첫 번째 밑줄 확률을 계산해보면,
π u ( ζ − 1 ≤ min j ( σ j j − ζ − 1 ) ≤ 2 max j σ j j ≤ ζ ) ≥ π u ( 2 ζ − 1 ≤ σ j j ≤ ζ 2 , ∀ j ) ≥ ∏ j = 1 p π u ( 2 ζ − 1 ≤ σ j j ≤ ζ 2 ) π u ( ζ − 1 ≤ j min ( σ jj − ζ − 1 ) ≤ 2 j max σ jj ≤ ζ ) ≥ π u ( 2 ζ − 1 ≤ σ jj ≤ 2 ζ , ∀ j ) ≥ j = 1 ∏ p π u ( 2 ζ − 1 ≤ σ jj ≤ 2 ζ )
에서 σ j j σ jj Γ ( 1 , λ 2 ) Γ ( 1 , 2 λ ) f ( σ j j ) = λ 2 e x p ( − λ 2 σ j j ) f ( σ jj ) = 2 λ e x p ( − 2 λ σ jj ) ( 2 ζ , ζ 2 ) ( ζ 2 , 2 ζ ) ( 0 , f ( 2 ζ ) ) ( 0 , f ( ζ 2 ) )
∏ j = 1 p π u ( 2 ζ − 1 ≤ σ j j ≤ ζ 2 ) = { ( ζ 2 − 2 ζ ) λ 2 e x p ( − λ ζ 4 ) } p ≥ { λ ζ 8 e x p ( − λ ζ 4 ) } p j = 1 ∏ p π u ( 2 ζ − 1 ≤ σ jj ≤ 2 ζ ) = { ( 2 ζ − ζ 2 ) 2 λ e x p ( − 4 λ ζ ) } p ≥ { 8 λ ζ e x p ( − 4 λ ζ ) } p
임을 알 수 있다. 이제 두 번째 밑줄 확률인 π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
[lemma 1 in [12]]
The univariate horseshoe density p ( θ ) p ( θ )
( a ) lim θ → 0 p ( θ ) = ∞ ( b ) F o r θ ≠ 0 , K 2 l o g ( 1 + 4 θ 2 ) < p ( θ ) < K l o g ( 1 + 2 θ 2 ) , w h e r e K = 1 2 π 3 ( a ) θ → 0 lim p ( θ ) = ∞ ( b ) F or θ = 0 , 2 K l o g ( 1 + θ 2 4 ) < p ( θ ) < K l o g ( 1 + θ 2 2 ) , w h ere K = 2 π 3 1
따라서, 위의 lemma\ (b) 를 통해, π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
π u ( σ k j ) ≤ 1 τ 2 π 3 l n ( 1 + 2 τ 2 σ k j 2 ) π u ( σ kj ) ≤ τ 2 π 3 1 l n ( 1 + σ kj 2 2 τ 2 )
를 알 수 있다. 한편, ∣ σ k j ∣ ∣ σ kj ∣
π u ( ∣ σ k j ∣ ≥ ( ζ p ) − 1 ) ≤ 1 ζ 2 π 3 ∫ ( ζ p ) − 1 ∞ l n ( 1 + 2 τ 2 x 2 ) d x π u ( ∣ σ kj ∣ ≥ ( ζp ) − 1 ) ≤ ζ 1 π 3 2 ∫ ( ζp ) − 1 ∞ l n ( 1 + x 2 2 τ 2 ) d x
가 되고,
≤ 2 π 3 ∫ ( ζ p ) − 1 ∞ 2 τ 2 x 2 d x ( ∵ l n ( 1 + x ) ≤ x , w h e n x ≥ 0 ) = 2 π 3 ∫ ( ζ p ) − 1 ∞ 2 τ x 2 d x = 2 2 π 3 τ ζ p ≤ π 3 2 ∫ ( ζp ) − 1 ∞ x 2 2 τ 2 d x ( ∵ l n ( 1 + x ) ≤ x , w h e n x ≥ 0 ) = π 3 2 ∫ ( ζp ) − 1 ∞ x 2 2 τ d x = π 3 2 2 τ ζp
임을 알 수 있다. 이를 통해 이제 π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 )
π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) = ∏ k ≠ j { 1 − π u ( ∣ σ k j ∣ ≥ ( ζ p ) − 1 ) } = ( 1 − 2 2 π 3 τ ζ p ) p ( p − 1 ) ≥ ( 1 − 2 2 π 3 τ ζ p ) p 2 ( ∵ 괄호안의 값은확률로 1보다 작으므로 ) ≥ e x p ( − 4 2 π 3 τ ζ p 3 ) ( ∵ l o g ( 1 − x ) ≥ − 2 x , w h e n x ≤ 1 2 ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 ) = k = j ∏ { 1 − π u ( ∣ σ kj ∣ ≥ ( ζp ) − 1 ) } = ( 1 − π 3 2 2 τ ζp ) p ( p − 1 ) ≥ ( 1 − π 3 2 2 τ ζp ) p 2 ( ∵ 괄호안의 값은확률로 1 보다 작으므로 ) ≥ e x p ( − π 3 4 2 τ ζ p 3 ) ( ∵ l o g ( 1 − x ) ≥ − 2 x , w h e n x ≤ 2 1 )
이다. 한편, 주어진 조건에서 τ = O ( 1 p 2 s 0 l n p n ) , s 0 l n p = O ( n ) τ = O ( p 2 1 n s 0 l n p ) , s 0 l n p = O ( n )
τ 1 p 2 s o l n p n ≤ c 1 , s o l n p n ≤ c 2 , c 1 , c 2 > 0 p 2 1 n s o l n p τ ≤ c 1 , n s o l n p ≤ c 2 , c 1 , c 2 > 0
임을 알 수 있다. 이들을 조합하면
⇒ τ p 2 ≤ c 2 c 1 c 3 ⇒ τ p 3 ≤ c 3 p ⇒ − τ p 3 ≥ − c 3 p ⇒ τ p 2 ≤ c 2 c 1 = def c 3 ⇒ τ p 3 ≤ c 3 p ⇒ − τ p 3 ≥ − c 3 p
이다. 이를 위 식 에서 활용하면,
e x p ( − 4 2 π 3 τ ζ p 3 ) ≥ e x p ( − c 3 4 2 π 3 ζ p ) = e x p ( − C p ) e x p ( − π 3 4 2 τ ζ p 3 ) ≥ e x p ( − c 3 π 3 4 2 ζp ) = e x p ( − Cp )
이다. 따라서, 두번째 밑줄 확률의 부등식을 다음과 같이 구할 수 있다.
π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) ≥ e x p ( − C p ) π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 ) ≥ e x p ( − Cp )
이제 첫 번째 밑줄 식과 두 번째 밑줄 식의 결과를 종합하면,
π u ( Σ ∈ U ( ζ ) ) ≥ π u ( ζ − 1 ≤ min j ( σ j j − ζ − 1 ) ≤ 2 max j σ j j ≤ ζ ) ∗ π u ( max k ≠ j ∣ σ k j ∣ < ( ζ p ) − 1 ) ≥ { λ ζ 8 e x p ( − λ ζ 4 ) } p e x p ( − C p ) = { λ ζ 8 e x p ( − λ ζ 4 − C ) } p π u ( Σ ∈ U ( ζ )) ≥ π u ( ζ − 1 ≤ j min ( σ jj − ζ − 1 ) ≤ 2 j max σ jj ≤ ζ ) ∗ π u ( k = j max ∣ σ kj ∣ < ( ζp ) − 1 ) ≥ { 8 λ ζ e x p ( − 4 λ ζ ) } p e x p ( − Cp ) = { 8 λ ζ e x p ( − 4 λ ζ − C ) } p
임을 알 수 있다.