10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you tried simulating it? There are some edge cases it seems it can be easy to formulate. $\endgroup$ – Royi Feb 2 '19 at 11:59
  • $\begingroup$ Did you mean to include values starting at $0$? $\endgroup$ – J.G. Feb 2 '19 at 11:59
  • $\begingroup$ Woops no that is an error. $\endgroup$ – fosho Feb 2 '19 at 13:02
  • 1
    $\begingroup$ 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. $\endgroup$ – rtybase Feb 2 '19 at 13:45
  • 1
    $\begingroup$ @phdmba7of12 yep, indeed ... the number of all $(n_i)_{i=1}^m$ can be calculated with stars-and-bars. $\endgroup$ – rtybase Feb 2 '19 at 13:51
2
+50
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.