2 added 1610 characters in body

I have

OK, here is the argument.

For n 2, f(n, 2) is equal to runthe average value over all subsets S of {1, .Does .., n} of f(|S|, 2) (including S = {1, ..., n}). So we may imagine a process where we start with {1, ..., n} and at each step we pick a subset uniformly at random of our current subset. f(n, 2) is the probability that look anything like the computational results?last time before we hit the empty set, our set contained just one element.

Consider what happens to each element of {1, ..., n} in this process. At each stage, if it is still in our subset, we keep it with probability 1/2 and throw it out with probability 1/2. So, the probability that it remains after r steps is 2-r. Thus we have n independent variables X1, ..., Xn, each with this exponential distribution, and what we seek is the probability that among them there is a unique maximum.

We may express this probability as a sum over the value of this maximum r. The probability of this occurring for any given r is

$$n(2^{-r} - 2^{-(r+1)})(1 - 2^{-r})^n = \frac 12 n 2^{-r} (1 - 2^{-r})^n.$$

So, $$f(n,2) = \sum_{r \ge 0} \frac 12 n 2^{-r} (1 - 2^{-r})^n.$$

Write $r = \log_2 n + u$. Then the rth summand becomes

$$\frac 12 2^{-u} (1 - 2^{-u}/n)^n.$$

From here the derivation is not entirely rigorous, but as $n$ increases, this value is roughly

$$\frac 12 2^{-u} e^{-2^{-u}}.$$

Now u is varying over values of the form $r - \log_2 n$ for $r$ a nonnegative integer, so -u ranges over values of the form $k + s$, s = the fractional part of $\log_2 n$, for $-\infty < k \le \lfloor \log_2 n \rfloor$ an integer. As n goes to ∞, we obtain the entire sum shown at the top.

1

If my computation is correct, then f(n, 2) should be roughly

$$\frac12 \sum_{k \in \mathbb{Z}} 2^{k+s} e^{-2^{k+s}}$$

where s = the fractional part of $\log_2 n$. (Note the terms of the sum decay rapidly both as $k \to \infty$ and $k \to -\infty$.)

I have to run. Does that look anything like the computational results?