Probability that sum of integer reciprocals is larger than a fixed number.

Suppose $n$ numbers are drawn independently from the list of $m$ integers $\{1,2,3,\ldots ,m\}$ uniformly at random. Denote these $n$ picks as $x_1,x_2,\ldots x_n$. Note that $n\geq m$ is possible. Fix a positive integer $C$. I am trying to determine the probability that $$\sum_{i = 1}^{n} \frac{1}{x_n}\geq C.$$

However I am not really sure where to start as I have not done much work with probability before.

Is there some way to get such a probability?

Solution 1:

I don't think there is anything except counting cases or simulation for small $n$. For large $n$ you can use the normal approximation, but I suspect $n$ has to be pretty large for that to work. The average reciprocal is $\frac {H_m}m\approx \frac {\log m + \gamma}m$. The problem is that the variance of your numbers is large. The sum will be dominated by how many times you pick $1$ and $2$ because the reciprocals of all the high numbers are about the same and small. The expected number of $1$s is $\frac nm$ with a standard deviation of about $\sqrt{\frac nm}$.

Solution 2:

This is actually more of a consideration than an answer, but wishfully it may be of some help.

We have $n$ discrete uniform i.i.d. random variables $X_k$, ranging from $1$ to $m$, and we want to find the distribution of the sum of their inverse.

To the scope of finding an approximation for high values of $m$ and $n$, we should go through the Characteristic Function of each variable $1/X_k$, exploiting the fact that the CF of the sum will be the $n$-th power of the single CF. And after getting the global CF we can invert it to get the sought pdf.

The single CF is given by $$ \eqalign{ & \varphi _{1/X} (t) = E\left[ {e^{\,i\,t/X} } \right] = {1 \over m}\sum\limits_{k = 1}^m {e^{\,i\,t/k} } = \cr & = e^{\,i\,t} {1 \over m}\sum\limits_{k = 1}^m {e^{\, - i\,t\left( {k - 1} \right)/k} } \cr} $$ and the matter comes to find a suitable approximation for the sum, or rather for its logarithm.

It might help to approximate each variable with a continuous uniform one ranging, from $1/2$ to $m+1/2$ and with probability density of $1/m$.
Geometrically that means to approximate a discrete hystogram of $m$ bars of height $1/m$ with $m$ vertical bands (rectangles) of width $1$ and height $1/m$, centered around each integral point.

Then the Characteristic Function of each continuous variable $1/X_k$ would be $$ \eqalign{ & \varphi _{1/X} (t) = E\left[ {e^{\,i\,t/X} } \right] = {1 \over m}\int_{\;x = 1}^{\,m} {e^{\,i\,t/x} dx} = \cr & = {1 \over m}\left( {\int_{\;x = 1}^{\,m} {\cos \left( {{t \over x}} \right)dx} + i\int_{\;x = 1}^{\,m} {\sin \left( {{t \over x}} \right)dx} } \right) \cr} $$