# 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?

• Have you tried simulating it? There are some edge cases it seems it can be easy to formulate. – Royi Feb 2 '19 at 11:59
• Did you mean to include values starting at $0$? – J.G. Feb 2 '19 at 11:59
• Woops no that is an error. – fosho Feb 2 '19 at 13:02
• I'd go with $$S=\sum\limits_{i=1}^n \frac{1}{x_n}=\sum\limits_{i=1}^m \frac{n_i}{i}$$ where $n_i \geq0$,$n_i \in\mathbb{N}$ and $\sum\limits_{i=1}^m n_i=n$. Then $$P(S\geq C) = 1 - P(S<C)$$ And check all the possible $(n_i)_{i=1}^m$ for which $S<C$. A small program (e.g.) in Python to check a few values, see if there is a patter. – rtybase Feb 2 '19 at 13:45
• @phdmba7of12 yep, indeed ... the number of all $(n_i)_{i=1}^m$ can be calculated with stars-and-bars. – rtybase Feb 2 '19 at 13:51

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}$$.

• "with a variance of about $\sqrt{\frac nm}$" That should be the standard deviation, no ? – leonbloy Feb 7 '19 at 20:15
• @leonbloy: yes, that is right. Thanks – Ross Millikan Feb 7 '19 at 20:44

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}