# Confidence intervals for collision probabilities

I have some random variable $X$ taking values in $\mathbb{N}$. $X$ has finite support (and so bounded mean, variance, etc) but of unknown size. Beyond that I know very little about its distribution.

Given $N$ values sampled from $X$, I would like to create a confidence interval for the probability $q = P(X_1 = X_2)$, where $X_i$ are independent random variables with the same law as $X$.

I have the following two ideas already:

1. If I knew the distribution of $X$ was $P(X = i) = p_i$ then this could be calculated as $q = \sum p_i^2$. Without that, I can calculate this for the empirical distribution and do a bootstrap estimate, but that won't give me a true confidence interval (unless I've misunderstood the guarantees made by the bootstrap method, which is certainly possible).
2. I can simply pair up the sample (discarding an odd member if necessary) and calculate this as the confidence interval of the parameter of a binomial distribution. This would work but feels like it's throwing away a lot of useful information.

As a result these both seem sub-optimal. Any suggestions?

• Could you elaborate on (a) which bootstrap procedure you are criticizing and (b) why you think it will not work correctly? – whuber Jul 2 '18 at 17:41
• I'm not criticizing anything, I just don't think bootstrap estimators actually produce confidence intervals do they? They only converge to them asymptotically unless I've misunderstood something fundamental. In terms of which one I meant, I just had a simple empirical bootstrap distribution: Do a sample with replacement from the empirical data some large number of times, calculate the function on those empirical distributions, and then report the range for the confidence interval. – DRMacIver Jul 2 '18 at 17:45
• There are better ways. It's likely your estimator is biased, so you will want at least to perform some bias correction. Bootstrapping is good for that. The issue of asymptotic correctness is important, but since you haven't provided any information about the amount of data you have, it's impossible for us to evaluate it. I wonder whether you might perhaps be dismissing a promising approach, so it would be good to have the information needed to evaluate its applicability. – whuber Jul 2 '18 at 17:50
• The amount of data is largely under my control. It can certainly be a few thousands. I'm not really dismissing bootstrap, and it's the solution I'm most likely to go for, I'm just exploring the alternatives! – DRMacIver Jul 2 '18 at 18:04