It is well-known that in the classic coupon collecting problem (CCP), the expected waiting time is \begin{equation*} T_n(x_1,\ldots,x_n) = \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \le n}\frac{1}{x_{i_1}+\cdots+x_{i_k}}, \end{equation*} where $x_1,\ldots,x_n>0$ are the sampling probabilities. Using a Laplace-transform representation, it is easy to directly show (i.e., without thinking of it as a waiting time) that $T_n$ is positive [1].

Problem setup

A couple of years ago I considered a certain "quantum" generalization to CCP. Here we take symmetric positive definite matrices $X_1,\ldots,X_n \in \mathbf{S}_{++}^d$, and consider the sum \begin{equation*} Q_n(X_1,\ldots,X_n) := \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \le n}\left(X_{i_1}+\cdots+X_{i_k}\right)^{-1}. \end{equation*}

I am still wondering if the following conjecture holds?

Conjecture. For $n\ge 1$, and $X_1,\ldots,X_n \in \mathbf{S}_{++}^d$, we have $Q_n(X_1,\ldots,X_n)\succ 0$.

Note. The cases $n=1,2,3$ are trivially true. I've tried $n=4$ numerically, and it seems to hold. (Also, by CCP, positivity immediately holds for a tuple of simultaneously diagonalizable matrices.)


[1]. P. Flajolet, D. Gardy, L. Thimonier (1992). Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Applied Mathematics, 39(3), 1992.

  • $\begingroup$ can you define the 'quantum generalization'? $\endgroup$ – Brout Mar 5 '17 at 23:30
  • $\begingroup$ That is just nomenclature because it involves positive definite matrices, which is why I put the word "quantum" in double quotes (so that it should not be taken too strictly). $\endgroup$ – Suvrit Mar 5 '17 at 23:31
  • $\begingroup$ Can you explain why this is trivially true if n = 2,3? Is it a trivial (but not necessarily "obvious/one line") calculation, or is it trivial in the sense that the answer can be seen with no calculation/real effort? $\endgroup$ – Nathaniel Johnston Mar 6 '17 at 19:01
  • $\begingroup$ Since $x^{-1} > (x+y)^{-1}$ for psd $x,y$, the case $n=2,3$ is "obvious." $\endgroup$ – Suvrit Mar 6 '17 at 19:09

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.