Return to Answer

(Edited from previous version, 2014-04-08.)

I believe that the answer is close to $\epsilon_n \to \log(\sqrt{e}) \approx 0.72138...$ where the logarithm is base 2, plus smaller order terms. This matches your simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}

(Edited from previous version, 2014-04-08.)

I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.7213475...$ where the logarithm is base 2. This seems to match simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}

(Edited from previous version, 2014-04-08.)

I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.72138...$ where the logarithm is base 2. This matches your simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}

(Edited from previous version, 2014-04-08.)

I believe that the answer is close to $\epsilon_n \to \log(\sqrt{e}) \approx 0.72138...$ where the logarithm is base 2, plus smaller order terms. This matches your simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}

(Edited from previous version, 2014-04-08.)

I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.72138...$ where the logarithm is base 2. This matches your simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 + \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} + \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} - \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}

(Edited from previous version, 2014-04-08.)

I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.72138...$ where the logarithm is base 2. This matches your simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

The key idea will be that the value we're interested in, $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$ can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

Step 1:

Just plugging in Stirling and doing some cancellation/rearranging, \begin{align} p_{n,k} &:= \frac{{n \choose k}}{2^n} \\ &\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} . \end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms. \begin{align} H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\ &= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) . \end{align}

So, using Sterling's approximation above, the logarithm of a probability term is \begin{align} \log(p_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\ &\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align}

Step 2: \begin{align} \mathbb{E}[H(k/n)] &= \sum_{k=0}^n p_{n,k} H(k/n) \\ &\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\ &= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) . \end{align} Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

Step 3:

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get \begin{align} \delta_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\ &= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) . \end{align}