From 3c091fa90c6a4251777f8eea4fbe3751e76a785f Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 18 Mar 2015 18:33:57 -0400
Subject: Comment on coupon collector

---
 results.tex | 5 +++++
 1 file changed, 5 insertions(+)

(limited to 'results.tex')

diff --git a/results.tex b/results.tex
index 2a21586..a9e79e1 100644
--- a/results.tex
+++ b/results.tex
@@ -51,6 +51,11 @@ It follows that for any vector $x \in \mathbb{R}^n$, $|\frac{1}{N}\|A x\|^2_2 -\
 
 Note that this is clearly not optimal. For example, note that for $k=1$, the solution to the coupon collector problem states that only ${\cal O}(n\log n)$ rows are sufficient before the matrix $A$ has full row rank with high probability, and not ${\cal O}(n^2)$ as stated by Corollary~\ref{cor:number_of_rows_needed}.
 
+\paragraph{Note:} $\Theta(n\log n)$ is in expectation for the coupon collector
+problem. If one want an exponentially small probability of failure, then
+I think results on the coupon collector problem also imply that a quadratic
+number of rows are required.
+
 \subsection{More Direct Approach}
 
 Here we work on $\mathbb{F}_2$. An $n\times n$ binary matrix can be seen as
-- 
cgit v1.2.3-70-g09d2

