Asymptotic difference between a function and its "binomial average"

Question

(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)

Answer 1

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.

Answer 2

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