Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It doesn't seem straightforward to put this into mathematical notation, but I'll do my best to explain the setup. Consider a harmonic series of the following type. For the sake of argument, say we have a set of 5 elements which are the reciprocals of the first 5 natural numbers:

$\left\{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}\right\}$

Start the series index at k = 1, and define the first element of the series to be 1. Knock 1 out of the set, so we now have:

$\left\{\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}\right\}$

For the second summand in the series, index k = 2, make a uniform random sample from the above set. Say we come up with $\frac{1}{4}$. Our series is now:

$1 + \frac{1}{4}$

Knock $\frac{1}{2}$ out of the set, as its denominator corresponds to the current index k = 2. We now have the set:

$\left\{\frac{1}{3}, \frac{1}{4}, \frac{1}{5}\right\}$

For the third summand in the series, again choose randomly from the above set, and knock out the value associated with the current index afterwards, that is, $\frac{1}{3}$.

For any given number k, i.e. size of both the series and starting size of the set, there should be an expected value associated with the stochastic series; using linearity of expectation it is straightforward to calculate for k = 5 as

$1 + \frac{\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5}}{4} + \frac{\frac{1}{3} + \frac{1}{4} + \frac{1}{5}}{3} + \frac{ \frac{1}{4} + \frac{1}{5}}{2} + \frac{1}{5}.$

I'm interested in what happens in the limit as k goes to infinity in this process. I've done some experiments numerically, and it seems that the expected value for large k converges to a number, $\approx 1.64$. Can it be proved that the expected value converges in the limit $k \to \infty$, and can the exact value be found?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Apart from the $1$ which doesn't follow the rule, in the expected value you seem to have terms $$\dfrac{1}{k+1-j} \sum_{i=j}^k \dfrac{1}{i}$$ for $j$ from $2$ to $k$. I don't know if there's a closed form for the sum of that, but it appears to have generating function $$ G(t) = \left(\frac{\pi^2}{6} + \mathrm{dilog}(t) - \ln(t)\ln(1-t)\right) \frac{t}{1-t} -\frac{\ln(1-t)^2}{2}$$

As for asymptotics, since $\displaystyle\sum_{i=j}^k 1/i \approx \int_{j}^{k+1} ds/s = \ln(k+1)-\ln(j)$, and $$\displaystyle\int_{2}^k \dfrac{\ln(k+1)-\ln(s)}{k+1-s} \ ds = \mathrm{dilog}\left(\frac{2}{k+1}\right) - \mathrm{dilog}\left(\frac{k}{k+1}\right) \to \frac{\pi^2}{6}\ \text{ as } k \to \infty$$ I think the limit is $\pi^2/6$.

share|improve this answer
    
Wow, the stochastic Basel problem! –  Bitrex Jul 11 '13 at 3:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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