Suppose I have a uniform multinomial distribution with $B$ trials and $Q$ equiprobable outcomes. Let the $i^{\text{th}}$ element of $\boldsymbol{r}=(r_1,\dots,r_Q)$ denote the number of times $i^{\text{th}}$ outcome is observed. Suppose I repeat those multinomial trials $n$ times to get $n$-many of these vectors $\boldsymbol{r}^{(1)},\dots,\boldsymbol{r}^{(n)}$.
The probability that $\boldsymbol{r}^{(1)}$ is repeated in one of the $n-1$ trials is bounded by
$(n-1)\binom{B}{\boldsymbol{r}^{(1)}}Q^{-B}$ where $\binom{B}{\boldsymbol{r}^{(1)}}$ is the multinomial number.
However, this bound is also random. I am looking for a way to bound this upper bound with an upper bound in terms of $n$,$B$ and $Q$, where $n$ and $B$ grows to infinity. I have tried the entropy upper bound on the multinomial term, and then upperbounding the entropy by $\log Q$, but this only gave me the trivial upper bound 1.
Best Answer
Following your method, the probability that the first outcome is repeated is at most
$$(n-1)\sum_{x_1+\ldots+x_Q=B}\binom{B}{x_1,\ldots,x_Q}^2Q^{-2B}.$$
Plugging in the asymptotics as $B\to\infty$ of the sum of squared multinomial coefficients of this paper, you get that this upper bound is
$$(n-1)Q^{Q/2}(4\pi B)^{(1-Q)/2}(1+o_B(1)).$$