Strict Bernstein Inequality











up vote
3
down vote

favorite
3













We define the entropy function by
$$H(x)=xlnfrac{1}{x}+(1-x)lnfrac{1}{1-x} quad text{ for } 0 leq x leq 1 $$
where $H(0)=H(1)=0$.



a) For integers $0leq kleq n$ prove that
$$binom{n}{k} leq e^{ncdot H(x)} quad text{ for } x=frac{k}{n}. $$
$textit{Hint}$: use that $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$



b) For integers $0 leq k leq n$, prove that
$$binom{n}{k} geq frac{1}{n+1}e^{ncdot H(x)} quad text{ for } x=frac{k}{n}$$
$textit{Hint}$: use the hint for part a)



c) Let $X_1,X_2,...X_n$ be independent r.v. s.t. $$mathbf{P}(X_k=1)=frac{1}{2} text{ and } mathbf{P}(X_k=-1)=frac{1}{2} $$



Let $X=X_1+X_2+...+X_n$. Deduce from parts a) and b) that for any $0 leq alpha <1 $ $$lim_{n rightarrow infty}sqrt[n]{mathbf{P}(Xgeq alpha n)}=sqrt{frac{1}{(1-alpha)^{1-alpha}(1+alpha)^{1+alpha}}} $$




Attempt at a) we know $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$
$$begin{align} binom{n}{m}x^m(1-x)^{n-m} leq & ; 1 \ lnleft(binom{n}{m}right)+lnleft(x^mright)+lnleft((1-x)^{n-m}right)leq & ; 0 \ lnbinom{n}{m}leq &-(m)ln(x)-(n-m)ln(1-x) \ binom{n}{m} leq & ; e^{-mln(x)-(n-m)ln(1-x)}end{align}$$



Choosing $k=m$, and then letting $frac{k}{n}=x$:



$$begin{align} binom{n}{k} leq & ; e^{-kln(x)-(n-k)ln(1-x)} \ binom{n}{k} leq & ; e^{-nleft(frac{k}{n}ln(x)+(1-frac{k}{n})ln(1-x)right)} \ binom{n}{k} leq & ; e^{nleft(xln(frac{1}{x})+(1-x)ln(frac{1}{1-x})right)}\ binom{n}{k} leq & ; e^{nH(x)}end{align}$$










share|cite|improve this question
























  • math.stackexchange.com/questions/2998474/… linking these two.
    – elcharlosmaster
    yesterday















up vote
3
down vote

favorite
3













We define the entropy function by
$$H(x)=xlnfrac{1}{x}+(1-x)lnfrac{1}{1-x} quad text{ for } 0 leq x leq 1 $$
where $H(0)=H(1)=0$.



a) For integers $0leq kleq n$ prove that
$$binom{n}{k} leq e^{ncdot H(x)} quad text{ for } x=frac{k}{n}. $$
$textit{Hint}$: use that $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$



b) For integers $0 leq k leq n$, prove that
$$binom{n}{k} geq frac{1}{n+1}e^{ncdot H(x)} quad text{ for } x=frac{k}{n}$$
$textit{Hint}$: use the hint for part a)



c) Let $X_1,X_2,...X_n$ be independent r.v. s.t. $$mathbf{P}(X_k=1)=frac{1}{2} text{ and } mathbf{P}(X_k=-1)=frac{1}{2} $$



Let $X=X_1+X_2+...+X_n$. Deduce from parts a) and b) that for any $0 leq alpha <1 $ $$lim_{n rightarrow infty}sqrt[n]{mathbf{P}(Xgeq alpha n)}=sqrt{frac{1}{(1-alpha)^{1-alpha}(1+alpha)^{1+alpha}}} $$




Attempt at a) we know $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$
$$begin{align} binom{n}{m}x^m(1-x)^{n-m} leq & ; 1 \ lnleft(binom{n}{m}right)+lnleft(x^mright)+lnleft((1-x)^{n-m}right)leq & ; 0 \ lnbinom{n}{m}leq &-(m)ln(x)-(n-m)ln(1-x) \ binom{n}{m} leq & ; e^{-mln(x)-(n-m)ln(1-x)}end{align}$$



Choosing $k=m$, and then letting $frac{k}{n}=x$:



$$begin{align} binom{n}{k} leq & ; e^{-kln(x)-(n-k)ln(1-x)} \ binom{n}{k} leq & ; e^{-nleft(frac{k}{n}ln(x)+(1-frac{k}{n})ln(1-x)right)} \ binom{n}{k} leq & ; e^{nleft(xln(frac{1}{x})+(1-x)ln(frac{1}{1-x})right)}\ binom{n}{k} leq & ; e^{nH(x)}end{align}$$










share|cite|improve this question
























  • math.stackexchange.com/questions/2998474/… linking these two.
    – elcharlosmaster
    yesterday













up vote
3
down vote

favorite
3









up vote
3
down vote

favorite
3






3






We define the entropy function by
$$H(x)=xlnfrac{1}{x}+(1-x)lnfrac{1}{1-x} quad text{ for } 0 leq x leq 1 $$
where $H(0)=H(1)=0$.



a) For integers $0leq kleq n$ prove that
$$binom{n}{k} leq e^{ncdot H(x)} quad text{ for } x=frac{k}{n}. $$
$textit{Hint}$: use that $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$



b) For integers $0 leq k leq n$, prove that
$$binom{n}{k} geq frac{1}{n+1}e^{ncdot H(x)} quad text{ for } x=frac{k}{n}$$
$textit{Hint}$: use the hint for part a)



c) Let $X_1,X_2,...X_n$ be independent r.v. s.t. $$mathbf{P}(X_k=1)=frac{1}{2} text{ and } mathbf{P}(X_k=-1)=frac{1}{2} $$



Let $X=X_1+X_2+...+X_n$. Deduce from parts a) and b) that for any $0 leq alpha <1 $ $$lim_{n rightarrow infty}sqrt[n]{mathbf{P}(Xgeq alpha n)}=sqrt{frac{1}{(1-alpha)^{1-alpha}(1+alpha)^{1+alpha}}} $$




Attempt at a) we know $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$
$$begin{align} binom{n}{m}x^m(1-x)^{n-m} leq & ; 1 \ lnleft(binom{n}{m}right)+lnleft(x^mright)+lnleft((1-x)^{n-m}right)leq & ; 0 \ lnbinom{n}{m}leq &-(m)ln(x)-(n-m)ln(1-x) \ binom{n}{m} leq & ; e^{-mln(x)-(n-m)ln(1-x)}end{align}$$



Choosing $k=m$, and then letting $frac{k}{n}=x$:



$$begin{align} binom{n}{k} leq & ; e^{-kln(x)-(n-k)ln(1-x)} \ binom{n}{k} leq & ; e^{-nleft(frac{k}{n}ln(x)+(1-frac{k}{n})ln(1-x)right)} \ binom{n}{k} leq & ; e^{nleft(xln(frac{1}{x})+(1-x)ln(frac{1}{1-x})right)}\ binom{n}{k} leq & ; e^{nH(x)}end{align}$$










share|cite|improve this question
















We define the entropy function by
$$H(x)=xlnfrac{1}{x}+(1-x)lnfrac{1}{1-x} quad text{ for } 0 leq x leq 1 $$
where $H(0)=H(1)=0$.



a) For integers $0leq kleq n$ prove that
$$binom{n}{k} leq e^{ncdot H(x)} quad text{ for } x=frac{k}{n}. $$
$textit{Hint}$: use that $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$



b) For integers $0 leq k leq n$, prove that
$$binom{n}{k} geq frac{1}{n+1}e^{ncdot H(x)} quad text{ for } x=frac{k}{n}$$
$textit{Hint}$: use the hint for part a)



c) Let $X_1,X_2,...X_n$ be independent r.v. s.t. $$mathbf{P}(X_k=1)=frac{1}{2} text{ and } mathbf{P}(X_k=-1)=frac{1}{2} $$



Let $X=X_1+X_2+...+X_n$. Deduce from parts a) and b) that for any $0 leq alpha <1 $ $$lim_{n rightarrow infty}sqrt[n]{mathbf{P}(Xgeq alpha n)}=sqrt{frac{1}{(1-alpha)^{1-alpha}(1+alpha)^{1+alpha}}} $$




Attempt at a) we know $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$
$$begin{align} binom{n}{m}x^m(1-x)^{n-m} leq & ; 1 \ lnleft(binom{n}{m}right)+lnleft(x^mright)+lnleft((1-x)^{n-m}right)leq & ; 0 \ lnbinom{n}{m}leq &-(m)ln(x)-(n-m)ln(1-x) \ binom{n}{m} leq & ; e^{-mln(x)-(n-m)ln(1-x)}end{align}$$



Choosing $k=m$, and then letting $frac{k}{n}=x$:



$$begin{align} binom{n}{k} leq & ; e^{-kln(x)-(n-k)ln(1-x)} \ binom{n}{k} leq & ; e^{-nleft(frac{k}{n}ln(x)+(1-frac{k}{n})ln(1-x)right)} \ binom{n}{k} leq & ; e^{nleft(xln(frac{1}{x})+(1-x)ln(frac{1}{1-x})right)}\ binom{n}{k} leq & ; e^{nH(x)}end{align}$$







probability random-variables binomial-theorem






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 23 hours ago

























asked yesterday









elcharlosmaster

1036




1036












  • math.stackexchange.com/questions/2998474/… linking these two.
    – elcharlosmaster
    yesterday


















  • math.stackexchange.com/questions/2998474/… linking these two.
    – elcharlosmaster
    yesterday
















math.stackexchange.com/questions/2998474/… linking these two.
– elcharlosmaster
yesterday




math.stackexchange.com/questions/2998474/… linking these two.
– elcharlosmaster
yesterday










1 Answer
1






active

oldest

votes

















up vote
1
down vote













I start with part (a). From the suggestion one has:



${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$



and taking logarithms:



$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$



The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.






share|cite|improve this answer





















  • I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
    – Thomas
    5 hours ago













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














 

draft saved


draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998530%2fstrict-bernstein-inequality%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote













I start with part (a). From the suggestion one has:



${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$



and taking logarithms:



$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$



The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.






share|cite|improve this answer





















  • I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
    – Thomas
    5 hours ago

















up vote
1
down vote













I start with part (a). From the suggestion one has:



${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$



and taking logarithms:



$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$



The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.






share|cite|improve this answer





















  • I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
    – Thomas
    5 hours ago















up vote
1
down vote










up vote
1
down vote









I start with part (a). From the suggestion one has:



${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$



and taking logarithms:



$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$



The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.






share|cite|improve this answer












I start with part (a). From the suggestion one has:



${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$



and taking logarithms:



$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$



The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered yesterday









Thomas

12318




12318












  • I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
    – Thomas
    5 hours ago




















  • I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
    – Thomas
    5 hours ago


















I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
– Thomas
5 hours ago






I tried with part (b) but in that case it is more problematic (for me) to use the hint of part 1...
– Thomas
5 hours ago




















 

draft saved


draft discarded



















































 


draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998530%2fstrict-bernstein-inequality%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

AnyDesk - Fatal Program Failure

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

QoS: MAC-Priority for clients behind a repeater