Comment on coupon collector

1 files changed, 5 insertions, 0 deletions

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