2
$\begingroup$

The quantity I'm interested in is expressed as follows:

$$ I = \mathbb{E}_{k\sim \text{Binom}(n,p)} \left[\ln \frac{\text{Beta}(p;a+k,b+n-k)}{\text{Beta}(p;a,b)}\right] $$

The term inside the expectation can be interpreted as the log ratio between the posterior and the prior of the Beta distribution evaluated at $p$ after observing $n$ Bernoulli($p$) coin flips with $k$ heads. As $n$ grows, I suspect that this expectation should grow no slower than $\ln(n)$ regardless of the choice for $a,b>0$ and $p\in[0,1]$. In short, I want to show that $I=\Omega(\ln(n))$.

My attempt

Recall the p.d.f of the Beta distribution at $p$ is:

$$ \begin{align} \text{Beta}(p;a,b)&=p^{a-1}(1-p)^{b-1} B(a,b)^{-1}\\ &=p^{a-1}(1-p)^{b-1} \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} \end{align} $$

We rewrite the quantity of interest $I$ as: $$ \begin{align} I &= \mathbb{E}_{k\sim \text{Binom}(n,p)} \left[\ln \frac{p^k(1-p)^{n-k}\Gamma(a+b+n)\Gamma(a)\Gamma(b)}{\Gamma(a+k)\Gamma(b+n-k)\Gamma(a+b)}\right]\\ &= np\ln(p)+n(1-p)\ln(1-p) + \mathbb{E}_{k\sim \text{Binom}(n,p)} \left[\ln \frac{\Gamma(a+b+n)\Gamma(a)\Gamma(b)}{\Gamma(a+k)\Gamma(b+n-k)\Gamma(a+b)}\right] \end{align} $$

At this point, I'm not sure how to move forward with the expectation of the Gamma terms.

$\endgroup$
2
  • $\begingroup$ Are $a,b,p$ fixed? $\endgroup$ Commented May 28 at 13:47
  • $\begingroup$ @IosifPinelis Yes they are fixed parameters. $\endgroup$
    – entropy07
    Commented May 28 at 13:48

1 Answer 1

3
$\begingroup$

Your conjecture is true.

Indeed, by Stirling's formula with an error bound for the gamma function, \begin{equation*} I\ge J-C; \tag{10}\label{10} \end{equation*} here and in what follows, $C$ stands for various positive real numbers (possibly different even within one expression) depending only on $a,b,p$ and \begin{equation*} J:=\frac12\ln n + n\big(h(p)+h(1-p)\big) \\ -nE\big(h(p_n+a/n) +h(1-p_n+b/n)\big)+\frac12 Er_n , \tag{20}\label{20} \end{equation*} where $h(u):=u\ln u$ for $u>0$ (with $h(0):=0$), $np_n$ is a random variable with the binomial distribution with parameters $n,p$, and \begin{equation*} r_n:=\ln\frac{(p_n+a/n)(1-p_n+b/n)}{2(1+(a+b)/n)}. \end{equation*} Also, \begin{equation*} r_n\ge\ln\frac{\min(a,b)/n}{2(1+(a+b)/n)}\ge-\ln n-C. \end{equation*}

Let $t:=\min(p,1-p)/2$. By Chebyshev's inequality, \begin{equation*} P(|p_n-p|\ge t)\le\frac1{nt^2}. \tag{30}\label{30} \end{equation*} So,
\begin{equation*} Er_n\,1(|p_n-p|\ge t)\ge-\frac{\ln n+C}{nt^2}\ge-C. \tag{40}\label{40} \end{equation*} Next, if $|p_n-p|<t$, then $r_n\ge\ln\frac{t(1-t)}{2(1+(a+b)/n)}\ge-C$, so that \begin{equation*} Er_n\,1(|p_n-p|<t)\ge-C. \end{equation*} So, \begin{equation*} Er_n\ge-C. \tag{50}\label{50} \end{equation*}

Using again \eqref{30} and noting that $0\le p_n\le1$ and that the function $h$ is locally bounded, similarly to \eqref{40} we conclude that \begin{equation*} nE\big(h(p_n+a/n)+h(1-p_n+b/n)\big)\,1(|p_n-p|\ge t) \\ \le nC E1(|p_n-p|\ge t)\le C. \tag{60}\label{60} \end{equation*}

Next, because $h<0$ on $(0,1)$ and $h''$ is locally bounded on $(0,1)$, and using \eqref{30} once again, we have \begin{align*} & nEh(p_n+a/n)\,1(|p_n-p|<t) \\ & \le nE[h(p)+(p_n+a/n-p)h'(p)+C(p_n+a/n-p)^2]\,1(|p_n-p|<t) \\ & \le n[h(p)+|h(p)|E1(|p_n-p|\ge t)+E(p_n+a/n-p)h'(p) \\ &\qquad +C|h'(p)|\,E1(|p_n-p|\ge t) +CE(p_n+a/n-p)^2] \\ &\le nh(p)+C. \tag{70}\label{70} \end{align*} Similarly, \begin{align*} nEh(1-p_n+b/n)\,1(|p_n-p|<t) \le nh(1-p)+C. \tag{80}\label{80} \end{align*}

Collecting now \eqref{10}, \eqref{20}, \eqref{50}, \eqref{60}, \eqref{70}, and \eqref{80}, we get \begin{equation} I\ge\frac12\ln n-C.\quad\Box \end{equation}


In fact, following the lines of the proof, one can see that \begin{equation} \Big|I-\frac12\ln n\Big|\le C. \end{equation}

$\endgroup$
7
  • 1
    $\begingroup$ Thanks a lot for your efforts! Is there any intuitions/motivations for using concentration bounds (Chebyshev's) here? Seems like a nice trick in general. $\endgroup$
    – entropy07
    Commented May 28 at 19:33
  • 1
    $\begingroup$ @entropy07 : If we replace $p_n$ by $p$ in (20), then it is easy to see that the resulting expression is $\frac12\,\ln n+O(1)$. Also, the relative frequency $p_n$ is close for large $n$ to the probability $p$. So, it is natural to use some bounds on that closeness. $\endgroup$ Commented May 28 at 20:54
  • $\begingroup$ Can you explain the steps in $(60)$ and $(70)$? I guess I don't fully understand the two cases and why you used Taylor's expansion for the second case. $\endgroup$
    – entropy07
    Commented May 29 at 11:23
  • 1
    $\begingroup$ @entropy07 : (i) I have provided details on (60) and (70). For some of those details (in contrast with what was before), we do need to assume that $C\ge0$. Note also the added clarification "(possibly different even within one expression)" concerning the use of the symbol $C$. The Taylor expansion is used in (70) because it works. For (60), where a very different expression is bounded, such an expansion is not needed. (ii) (40) holds for all $n\ge1$, because $\ln n\le n-1$ for such $n$. $\endgroup$ Commented May 29 at 19:19
  • 1
    $\begingroup$ @entropy07 : Thank your comment. This is now fixed. $\endgroup$ Commented May 29 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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