We aim to choose the value of \(k\)  such that with probability at least \(1/2\) , at most \(k - 1\)  out of the \(k\)  basis vectors are observed in the random sample \(X_1, \ldots , X_n\)  (i.e., at least one of the basis vectors is not observed). This analysis follows from the coupon collector argument showing that one needs, with probability at least \(1/2\) , a sample of size at least \(ck\log k\)  to observe all \(k\)  vectors where \(c\)  is a numerical constant. Let \(T\)  be a random variable that counts the (random) number of trials needed to observe all \(k\)  basis vectors. A basic result (see, e.g., [1]}) shows that for any \(t > 0\) ,
\(\Pr \left(\left|T - kH_{k}\right| \ge tk \right) \le \frac{\pi ^2}{6t^2},\) 
