# Asymptotic difference between a function and its “binomial average”

(I posted this question on Math.SE a few weeks ago. I got a few comments, but nothing definite, and so I thought I would try MO.)

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number.

Dividing by $2^n$, we have $$2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = H_n - \sum_{k=1}^n \frac{1}{k 2^k}.$$

The sum on the left can now be interpreted as a weighted average of the harmonic numbers through $H_n$ - where the weights, of course, are the binomial coefficients. Thus the difference between $H_n$ and its "binomial average" (I'm guessing there's no term for this) is $$H_n - 2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$

The sum on the right is known to converge to $\ln 2$ as $n \to \infty$. (Substitute $-\frac{1}{2}$ into the Maclaurin series for $\ln (1+x)$.)

This leads me to my question:

Can we classify nonnegative functions $f(n)$ for which $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right)$$ is finite and nonzero?

It would seem that if $f$ increases sufficiently rapidly, then the limit would be $\infty$. This is the case with both $f(n) = a^n$ and $f(n) = n$. If $f$ decreases or is constant, then the limit is zero. If $f$ has basically logarithmic growth, then it seems the limit would behave as $H_n$. But can this be proved? And what about other sublinear, increasing functions?

The two Math.SE responses were

1. "I agree that logarithmic growth is what you need. The 'binomial average' of $f(n)$ should be about $f(n/2)$." (from Michael Lugo)
2. A reformulation of the problem in terms of exponential generating functions. (from Qiaochu Yuan)
-
Can you evaluate the limit in the case $f(n)=\log n$? –  Gerry Myerson Nov 21 '10 at 0:28
@Gerry Myerson: If we use $\log n = H_n − \gamma +O(\frac{1}{n})$ (and taking $\log 0 = 0$ or just starting the summation at $k=1$) we get that the limit with $f(n)= \log n$ is $\ln 2$ once again. So I guess that proves that if $f$ does have logarithmic growth, then the limit will be finite and nonzero. So now we're just left with the question about functions with other kinds of sublinear growth. –  Mike Spivey Nov 21 '10 at 21:19
There is something called the "binomial transform" of a sequence, which is not exactly what you've got but close enough that maybe some of what's known about it could rub off. –  Gerry Myerson Nov 21 '10 at 23:29
@Gerry Myerson: Thanks. I am familiar with binomial transforms, but unfortunately nothing that I know about them has helped me thus far with this question. –  Mike Spivey Nov 22 '10 at 1:14

The function $f(n)$ must be $\Theta (\log n)$. Update: As Didier Piau points out in the comments, we can say something stronger: $\frac{f(n)}{\log_2 n} \to L$ as $n \to \infty$. See the update at the end of the argument.

Suppose, for some positive $L$ (the negative case is similar), $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right) = L.$$ Thus $$f(n) = L + r(n) + 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k)$$ for some function $r(n)$ such that $r(n) \to 0$ as $n \to \infty$. This gives us a recurrence relation for $f(n)$. Since $r(n) \to 0$, $L + r(n) > 0$ for all sufficiently large $n$. So, for all sufficiently large $n$, there exist positive constants $C$ and $D$ such that $C < L + r(n) < D$. Since the initial terms in the function eventually become negligible in determining the value of $f(n)$ via the recurrence relation, there exist functions $g(n)$ and $h(n)$ such that for all sufficiently large $n$, $g(n) \leq f(n) \leq h(n)$ and $g(n)$ and $h(n)$ satisfy $$g(n) = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} g(k),$$ $$h(n) = D + 2^{-n} \sum_{k=0}^n \binom{n}{k} h(k).$$

So the problem reduces to showing that $g(n)$ and $h(n)$ are $\Theta (\log n)$. The argument is the same for both.

There are some different ways to do this; my favorite is to interpret the $g(n)$ recurrence probabilistically. Suppose we start at time $g(0)$, we flip a set of $n$ coins simultaneously each round, and it takes $C$ time units to do one round of flips. When a coin turns up heads for the first time, we cease flipping it. Let $T(n)$ be the time at which the last coin to achieve its first head does so. To find $E[T(n)]$, condition on the number of coins that achieve heads in the first round of flips. This yields $$E[T(n)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(n-k)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(k)].$$ Thus $g(n) = E[T(n)]$.

Another way to view $T(n)$ is that it is $g(0) + C M_n$, where $M_n = \max\{X_1, X_2, \ldots, X_n\}$ and the $X_i$'s are independent and identically distributed geometric $(1/2)$ random variables. (Each geometric random variable models the first time a head appears.) Thus $g(n) = g(0) + C E[M_n]$. It is known that $\frac{H_n}{\log 2} \leq E[M_n] \leq \frac{H_n}{\log 2} + 1$ and, more precisely, that $E[M_n]$ is logarithmically summable to $\frac{H_n}{\log 2} + \frac{1}{2}$. (See, for example, Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables," Statistics and Probability Letters 78 (2008) 135-143. See also this MO question, "What is the Expected Maximum out of a Sample (size $n$) from a Geometric Distribution?")

Thus $g(n) = \frac{C}{\log 2} \log n + O(1)$, which means that $h(n) = \frac{D}{\log 2} \log n + O(1)$ and $f(n) = \Theta (\log n)$.

Update: Given $\epsilon > 0$, if we take take $C > 0$ such that $L - \epsilon \leq C < L$ and $D = L + \epsilon$, this argument shows that $$L - \epsilon + O\left(\frac{1}{\log n}\right) \leq \frac{f(n)}{\log_2 n} \leq L + \epsilon + O\left(\frac{1}{\log n}\right).$$

Thus, as $n \to \infty$, $\frac{f(n)}{\log_2 n} \to L.$

For some other ideas that pertain to this result, including what are effectively some alternative derivations, see Pradipta's recent MO question, "Coin Flipping and a Recurrence Relation". In fact, reading Pradipta's question and some of its answers gave me the ideas needed to construct this argument! So, thanks go to Pradipta, Didier Piau, Emil Jeřábek, and Louigi Addario-Berry.

-
@Mike: Bravo! It seems the hypothesis $L\ne0$ is irrelevant. More importantly, do you think that in fact $f(n)/\log_2(n)\to L$? If really the initial terms of the sequence $(f(n))$ eventually become negligible, this should be true. Dunno... –  Did Feb 18 '11 at 0:20
@Didier: Thanks! It was very satisfying when I realized your post and the answers and comments from the others were what I needed to answer my own question. :) The hypothesis $L \neq 0$ is needed for the logarithmic growth. For example, any constant $f(n)$ will have $L = 0$. Your other question is a good one. I'll have to think about it... –  Mike Spivey Feb 18 '11 at 0:43
@Mike: 0. Yes, MO does provide some satisfying experiences... 1. About the $L=0$ case, you are right of course, I forgot you want $\Theta(\log(n))$ and not only $O(\log(n))$. Sorry about the noise. 2. Rereading your post, it seems that what you did is to bound the limsup and liminf of $f(n)/\log_2(n)$ by the limsup and liminf of the sequence $f-\mathrm{Bin}(f)$ (the one that you assume converges to $L$). .../... –  Did Feb 18 '11 at 7:07
.../... Another, more scary, way of saying that is that, if your proof works, it does show that $f(n)/\log_2(n)$ converges as soon as $f-\mathrm{Bin}(f)$ converges (since you say that one can take $C$ and $D$ as close to $L$ as one wants). Mmmm... –  Did Feb 18 '11 at 7:07
@Didier: 1. I wouldn't call it noise. If you allow $L = 0$ then the proof goes through more easily with the $h(n)$ function and you get $O(\log n)$, which is still interesting. 2. I think you're right. If you replace $C$ and $D$ with $L - \epsilon$ and $L + \epsilon$ and follow the proof through you get that $f(n)/\log_2 n$ is bounded by $L \pm \epsilon + O(1/\log_2 n)$. –  Mike Spivey Feb 18 '11 at 18:59
show 1 more comment

I also agree that logarithmic growth looks like the right thing. There is lots of freedom, one can make the sequence of differences whatever one wishes. In case we want the sequence to start with a and from then on to have that difference always be exactly L one gets a sequence starting a, 2L+a, (8/3)L+a, (22/7)L+a, (368/105)L+a, (2470/651)L+a, (7880/1953)L+a, (150266/35433)L+a which appears to involve A158466 in the OEIS, an interesting sequence.

later From a sequence $\mathbf{f}=(f_1,\cdots)$ (with an intial term $f_0$) one obtains a sequence $\mathbf{d}=(d_1,\cdots)$ of harmonic differences (the difference $d_0$ is defined but will always be 0). This is a linear transformation whose kernel is the constant sequences. We will thus assume that all terms have been shifted so that $f_0=0$. This, of course, does not change the growth rate . Then the transformation is invertible. View the sequences as column vectors and let $M$ be the infinite lower-triangular non-negative matrix with $M_{nk}=2^{-n}\binom{n}{k}$ for $n,k \ge 1$. Then $(I-M)\mathbf{f}=\mathbf{d}$. The question is:

$\bullet$ What can be infered about $\mathbf{f}$ given that $\lim_{n \to \infty} d_n=\ell$ exists and is finite?

Independent of the limit existing or not, $\mathbf{f}=(I-M)^{-1}\mathbf{d}$. Furthermore, $$(I-M)^{-1}=I+M+M^2+M^3+\cdots$$ In this sum the terms are all non-negative matrices. At this stage I run out of easy theoretical observations. Numerically many things seem apparent, some of which I can easily prove and others which I can't but others surely can (if they are true).Let $N=(I-M)^{-1}$. The diagonal entries are $N_{kk}=\frac{2^k}{2^k-1}$ while $N_{k,k-1}=k\frac{2^{k-1}}{(2^k-1)(2^{k-1}-1)}$ and $N_{k,k-2}=\binom{k}{2}\frac{(2^{k-1}+1)2^{k-2}}{(2^k-1)(2^{k-1}-1)(2^{k-2}-1)}$. The typical row (not too close to the top) seems to start approximately $[1.44,0.721,0.480,0.361..$ so very nearly $q[1,1/2,1/3,1/4...$ for some constant $q$ I don't recognize. It would appear that the entries$N_{nk}$ for $k$ about $\sqrt{n}$ on either side of $n/2$ sum to about 1. There are other rather smaller bulges maybe centered on $n/4$, $n/8$ etc.

So (roughly speaking) given a row not too near the top, the entries start with 1.44 and drop off quickly, the final nonzero entries are very small until a 1 on the diagonal. The entries in between are relatively small and the most signifigant ones are in the middle and have a constant sum. Succesive rows are very nearly equal in all entries except the diagonal. More precise quantitative versions of this might suffice to show that if $\lim_{n \to \infty} d_n=0$ then (and only then?) $\mathbf{f}=N\mathbf{d}$ has a finite limit $\lim_{n \to \infty} f_n=L$. This would seem enough because then if $\lim_{n \to \infty} d_n=\ell$ the $\mathbf{f}$ corresponding to it has $f_n-\frac{\ell}{\log 2}H_n$ going to some finite limit depending on the initial terms of $\mathbf{d}$.

-
Thanks, Aaron. That's a particularly interesting connection with the sequence about probabilistic skip lists! I'll have to look into that further. –  Mike Spivey Nov 21 '10 at 21:20
I don't feel like writing code right now to test this myself, but your $q \approx 1.44$ might be $1/\log 2$. –  Michael Lugo Nov 22 '10 at 16:26
Good call. That must be right. Curiously (to me) the entries do not go monotonically. The local extremes for rows 15 to 200 for column 1 are as follows, the last figure is the discrepancy from 1/ln(2). (sorry that I can't get columns) 19, 1.442587273, -0.000107768 // 28, 1.442753899, 0.000058858 // 40, 1.442656109, -0.000038932 // 57, 1.442724038, 0.000028997 // 81, 1.442671499, -0.000023542 // 115, 1.442715361, 0.000020320 // 163, 1.442676728, -0.000018313 –  Aaron Meyerowitz Nov 23 '10 at 0:00
The places where the values in the first column are at a local extreme are 2,4,8,13,19,28,40,57,81,115,163,231,328,464 looks like (the differences) might be related to the Graham Pollak sequence..... –  Aaron Meyerowitz Nov 23 '10 at 1:47
@Aaron, @Michael: You were right about $1/\log 2$ showing up. See my answer. –  Mike Spivey Feb 18 '11 at 0:44