Under the null, where the first inequality is the Bonferroni inequality, and the second inequality fol- lows from equation (A.8). Since the last term goes to 0 as N → ∞ if lim$_{N}$$_{→∞}$ m/N 1 / 3 = 0, the proof of item 1 is complete. The proof of item 2 is very similar to the proof in Section A.1, the only modification is an additional application of Bonferroni’s inequality under the null: where the first inequality in the last row follows from (A.12). Since m$_{max}$ ( N m$_{max}$ ) is at most O ( N × N$^{√}$ $^{N}$), and since it follows that the last expression goes to zero as N → ∞ . We examined our suggested estimator in the following setup. For m = 15 and N ∈ { 300 , 1000 } sample points drawn from a two–component Gaussian mixture, we 60 D An example of mutual information estimation Pr$^{(}$S π ˆ m × ˆ m ≥ c ′′ ( N ˆ m − 1$^{)}$ ( N − ˆ m + 1) | ⃗x,⃗y$^{)}$ ≤ m$_{max}$ ∑ m =2 Pr$^{(}$S π m × m ≥ c ′′ ( N m − 1$^{)}$ ( N − m + 1) | ⃗x,⃗y$^{)}$ ≤ m$_{max}$ max m ∈{ 2 ,...,m$_{max}$ } ( N m − 1 $^{)}$( m − 1) 2 c ′′ ( N m − 1 $^{)}$( N − m + 1) ≤ m$_{max}$ ( m$_{max}$ − 1) 2 c $^{′′}$( N − m$_{max}$ + 1) , Pr$_{H}$$_{0}$$^{(}$M DDP ˆ m × ˆ m ≥ c ′ 2 ( N − ˆ m + 1)$^{)}$ ≤ m$_{max}$ ∑ m =2 Pr$_{H}$$_{0}$$^{(}$M DDP m × m ≥ c ′ 2 ( N − m + 1)$^{)}$ ≤ m$_{max}$ max m ∈{ 2 ,...,m$_{max}$ } $^{(}$N m$^{)}$ e − ( c ′ 8 ( N − m +1) − ( m − 1) $^{2}$/ 4) ≤ m$_{max}$$^{(}$ N m$_{max}$$^{)}$ e − ( c ′ 8 ( N − m$_{max}$ +1) − ( m$_{max}$ − 1) $^{2}$/ $^{4)}$, e − ( c ′ 8 ( N − m$_{max}$ +1) − ( m$_{max}$ − 1) $^{2}$/ 4) = O ( e − ( c ′ $_{8}$N $^{)}$) ,