Getting closer to $k$ min-entropy using summation
$begingroup$
A distribution $D$ over $Lambda$ has $k$ min-entropy if the largest probability mass given to any element in $Lambda$ is $2^{-k}$ (i.e., for all $ainLambda$, $D(a)leq 2^{-k}$, and for some $a$ it is $2^{-k}$). We denote it by $H_infty(D)=k$.
Let $X$ and $Y$ be two independent distributions over ${0, 1}^n$ such that both $X$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy and $Y$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy.
Let $Z=X+Y$ denote the distribution over ${0, 1}^n$ obtained by sampling $xsim X$ and $ysim Y$ and outputting $x+y$, where the sum is addition modulo $2$ coordinate wise.
Prove that $Z$ is $epsilon^2$-close in statistical distance to a distribution with min-entropy at least $k$.
It is clear that $H_infty(Z)leqmin{H_infty(X),H_infty(Y)}$, but I don't see how that helps.
Note that by statistical distance I mean TV distance.
probability-theory entropy
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
$endgroup$
add a comment |
$begingroup$
A distribution $D$ over $Lambda$ has $k$ min-entropy if the largest probability mass given to any element in $Lambda$ is $2^{-k}$ (i.e., for all $ainLambda$, $D(a)leq 2^{-k}$, and for some $a$ it is $2^{-k}$). We denote it by $H_infty(D)=k$.
Let $X$ and $Y$ be two independent distributions over ${0, 1}^n$ such that both $X$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy and $Y$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy.
Let $Z=X+Y$ denote the distribution over ${0, 1}^n$ obtained by sampling $xsim X$ and $ysim Y$ and outputting $x+y$, where the sum is addition modulo $2$ coordinate wise.
Prove that $Z$ is $epsilon^2$-close in statistical distance to a distribution with min-entropy at least $k$.
It is clear that $H_infty(Z)leqmin{H_infty(X),H_infty(Y)}$, but I don't see how that helps.
Note that by statistical distance I mean TV distance.
probability-theory entropy
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
$endgroup$
1
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46
add a comment |
$begingroup$
A distribution $D$ over $Lambda$ has $k$ min-entropy if the largest probability mass given to any element in $Lambda$ is $2^{-k}$ (i.e., for all $ainLambda$, $D(a)leq 2^{-k}$, and for some $a$ it is $2^{-k}$). We denote it by $H_infty(D)=k$.
Let $X$ and $Y$ be two independent distributions over ${0, 1}^n$ such that both $X$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy and $Y$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy.
Let $Z=X+Y$ denote the distribution over ${0, 1}^n$ obtained by sampling $xsim X$ and $ysim Y$ and outputting $x+y$, where the sum is addition modulo $2$ coordinate wise.
Prove that $Z$ is $epsilon^2$-close in statistical distance to a distribution with min-entropy at least $k$.
It is clear that $H_infty(Z)leqmin{H_infty(X),H_infty(Y)}$, but I don't see how that helps.
Note that by statistical distance I mean TV distance.
probability-theory entropy
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
$endgroup$
A distribution $D$ over $Lambda$ has $k$ min-entropy if the largest probability mass given to any element in $Lambda$ is $2^{-k}$ (i.e., for all $ainLambda$, $D(a)leq 2^{-k}$, and for some $a$ it is $2^{-k}$). We denote it by $H_infty(D)=k$.
Let $X$ and $Y$ be two independent distributions over ${0, 1}^n$ such that both $X$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy and $Y$ is $epsilon$-close in statistical distance to a distribution with $k$ min-entropy.
Let $Z=X+Y$ denote the distribution over ${0, 1}^n$ obtained by sampling $xsim X$ and $ysim Y$ and outputting $x+y$, where the sum is addition modulo $2$ coordinate wise.
Prove that $Z$ is $epsilon^2$-close in statistical distance to a distribution with min-entropy at least $k$.
It is clear that $H_infty(Z)leqmin{H_infty(X),H_infty(Y)}$, but I don't see how that helps.
Note that by statistical distance I mean TV distance.
probability-theory entropy
probability-theory entropy
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
edited Dec 26 '18 at 5:59
Don Fanucci
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
asked Dec 24 '18 at 21:08
Don FanucciDon Fanucci
1,320421
1,320421
1
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46
add a comment |
1
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46
1
1
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46
add a comment |
0
active
oldest
votes
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051639%2fgetting-closer-to-k-min-entropy-using-summation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051639%2fgetting-closer-to-k-min-entropy-using-summation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
$begingroup$
Just to be sure, by statistical distance you mean total variation, yes? In any case, this can't be true at the level of generality of your formulation - suppose $X ,Y$ are uniform. It is easy to see that $Z$ is also uniform. So $Z$ cannot get closer to any other distribution than $X$ and $Y$. In particular, if I pick $epsilon$ to be the minimum TV distance that a distribution with min-entropy $k$ is from the uniform, then $Z$ is also at a distance $ge epsilon$ from every $k$ min-entropy distribution. Are there missing hypotheses?
$endgroup$
– stochasticboy321
Dec 26 '18 at 1:16
$begingroup$
@stochasticboy321 I have edited it. Indeed by the statistical distance I mean TV distance. Also I have changed the claim to be proven.
$endgroup$
– Don Fanucci
Dec 26 '18 at 4:46