The $ell_2$ norm of two stochastic vectors












0












$begingroup$


I would like to know why this is true:




Given an $n$-dimensional stochastic vector $v$ and another $n$-dimensional stochastic vector $u$ which distributes uniformly over ${1,dots,n}$ (meaning if the length of the vector $u$ is $n=3$ then $u = (1/3,1/3,1/3)$) then $lVert u-vrVert_2 leq 1$.




For example, let $v = (0.8,0.2)$ and $v = (0.5,0.5)$: $lVert u-vrVert_2 = lVert(0.3,-0.3)rVert_2=sqrt{2cdot0.3^2}$
which is less than 1.



I tried many different inputs and it works for all of them but I can’t figure out why?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:07










  • $begingroup$
    @herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:09






  • 1




    $begingroup$
    There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:17










  • $begingroup$
    @herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:20










  • $begingroup$
    If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
    $endgroup$
    – Clement C.
    Dec 17 '18 at 21:32


















0












$begingroup$


I would like to know why this is true:




Given an $n$-dimensional stochastic vector $v$ and another $n$-dimensional stochastic vector $u$ which distributes uniformly over ${1,dots,n}$ (meaning if the length of the vector $u$ is $n=3$ then $u = (1/3,1/3,1/3)$) then $lVert u-vrVert_2 leq 1$.




For example, let $v = (0.8,0.2)$ and $v = (0.5,0.5)$: $lVert u-vrVert_2 = lVert(0.3,-0.3)rVert_2=sqrt{2cdot0.3^2}$
which is less than 1.



I tried many different inputs and it works for all of them but I can’t figure out why?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:07










  • $begingroup$
    @herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:09






  • 1




    $begingroup$
    There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:17










  • $begingroup$
    @herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:20










  • $begingroup$
    If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
    $endgroup$
    – Clement C.
    Dec 17 '18 at 21:32
















0












0








0





$begingroup$


I would like to know why this is true:




Given an $n$-dimensional stochastic vector $v$ and another $n$-dimensional stochastic vector $u$ which distributes uniformly over ${1,dots,n}$ (meaning if the length of the vector $u$ is $n=3$ then $u = (1/3,1/3,1/3)$) then $lVert u-vrVert_2 leq 1$.




For example, let $v = (0.8,0.2)$ and $v = (0.5,0.5)$: $lVert u-vrVert_2 = lVert(0.3,-0.3)rVert_2=sqrt{2cdot0.3^2}$
which is less than 1.



I tried many different inputs and it works for all of them but I can’t figure out why?










share|cite|improve this question











$endgroup$




I would like to know why this is true:




Given an $n$-dimensional stochastic vector $v$ and another $n$-dimensional stochastic vector $u$ which distributes uniformly over ${1,dots,n}$ (meaning if the length of the vector $u$ is $n=3$ then $u = (1/3,1/3,1/3)$) then $lVert u-vrVert_2 leq 1$.




For example, let $v = (0.8,0.2)$ and $v = (0.5,0.5)$: $lVert u-vrVert_2 = lVert(0.3,-0.3)rVert_2=sqrt{2cdot0.3^2}$
which is less than 1.



I tried many different inputs and it works for all of them but I can’t figure out why?







inequality probability-distributions vectors stochastic-calculus






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 16 '18 at 18:52









Clement C.

50.9k33992




50.9k33992










asked Dec 16 '18 at 17:49









נירייב שמואלנירייב שמואל

195




195












  • $begingroup$
    Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:07










  • $begingroup$
    @herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:09






  • 1




    $begingroup$
    There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:17










  • $begingroup$
    @herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:20










  • $begingroup$
    If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
    $endgroup$
    – Clement C.
    Dec 17 '18 at 21:32




















  • $begingroup$
    Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:07










  • $begingroup$
    @herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:09






  • 1




    $begingroup$
    There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
    $endgroup$
    – herb steinberg
    Dec 16 '18 at 18:17










  • $begingroup$
    @herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
    $endgroup$
    – נירייב שמואל
    Dec 16 '18 at 18:20










  • $begingroup$
    If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
    $endgroup$
    – Clement C.
    Dec 17 '18 at 21:32


















$begingroup$
Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
$endgroup$
– herb steinberg
Dec 16 '18 at 18:07




$begingroup$
Your statement is too confusing. Are you asking about 2-d or 3-d vectors?
$endgroup$
– herb steinberg
Dec 16 '18 at 18:07












$begingroup$
@herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
$endgroup$
– נירייב שמואל
Dec 16 '18 at 18:09




$begingroup$
@herbsteinberg I am asking for n-d vectors. the 2-d and 3-d vectors where just an example in order to simplify the problem.
$endgroup$
– נירייב שמואל
Dec 16 '18 at 18:09




1




1




$begingroup$
There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
$endgroup$
– herb steinberg
Dec 16 '18 at 18:17




$begingroup$
There is other confusing stuff. For example U length 3 and U=(1/3,1/3,1/3) is wrong. In general $|v-u|le 1$ is not true without more descriptions for $u$ and $v$.
$endgroup$
– herb steinberg
Dec 16 '18 at 18:17












$begingroup$
@herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
$endgroup$
– נירייב שמואל
Dec 16 '18 at 18:20




$begingroup$
@herbsteinberg that's why I indicated that U distribute uniformly between 1 untill n.
$endgroup$
– נירייב שמואל
Dec 16 '18 at 18:20












$begingroup$
If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
$endgroup$
– Clement C.
Dec 17 '18 at 21:32






$begingroup$
If I may, why are there votes to close with no comment on it? Sure, the OP hasnt included their attempts (if any), but then the minimum here (for a new contributor) would be to point it out instead of just voting for closure... "נירייב שמואל is a new contributor to this site. Take care in asking for clarification, commenting, and answering."
$endgroup$
– Clement C.
Dec 17 '18 at 21:32












1 Answer
1






active

oldest

votes


















1












$begingroup$

First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform,
$$
lVert u-vrVert_2 leq lVert urVert_2+ lVert vrVert_2 = frac{1}{sqrt{n}} + 1
$$



Now, for the stronger claim. Observe that
$$begin{align}
lVert u-vrVert_2^2 &= sum_{k=1}^n (u_k-v_k)^2 =
sum_{k=1}^n u_k^2 + sum_{k=1}^n v_k^2 - 2sum_{k=1}^n u_k v_k
= ncdot frac{1}{n^2} + lVert vrVert_2^2 - frac{2}{n}sum_{k=1}^n v_k\
&= frac{1}{n} + lVert vrVert_2^2 - frac{2}{n}
= lVert vrVert_2^2 - frac{1}{n} \
&leq 1 - frac{1}{n}
end{align}$$

where the last inequality comes from the fact that $$lVert vrVert_2^2 = sum_{k=1}^n v_k^2 leq sum_{k=1}^n v_k = 1$$
(more generally, $lVert vrVert_p leq lVert vrVert_q$ if $pgeq qgeq 1$).




Upshot: the squared $ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $ell_2$ norm:
$$
lVert u-vrVert_2^2 = lVert vrVert_2^2 - frac{1}{n}
$$

which can itself be interpreted as the collision probability
$$
lVert vrVert_2^2 = mathbb{P}_{v}{ X=Y}
$$

where $X,Y$ are independent random variables with pmf $v$.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
    $endgroup$
    – Clement C.
    Dec 16 '18 at 18:49













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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3042911%2fthe-ell-2-norm-of-two-stochastic-vectors%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









1












$begingroup$

First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform,
$$
lVert u-vrVert_2 leq lVert urVert_2+ lVert vrVert_2 = frac{1}{sqrt{n}} + 1
$$



Now, for the stronger claim. Observe that
$$begin{align}
lVert u-vrVert_2^2 &= sum_{k=1}^n (u_k-v_k)^2 =
sum_{k=1}^n u_k^2 + sum_{k=1}^n v_k^2 - 2sum_{k=1}^n u_k v_k
= ncdot frac{1}{n^2} + lVert vrVert_2^2 - frac{2}{n}sum_{k=1}^n v_k\
&= frac{1}{n} + lVert vrVert_2^2 - frac{2}{n}
= lVert vrVert_2^2 - frac{1}{n} \
&leq 1 - frac{1}{n}
end{align}$$

where the last inequality comes from the fact that $$lVert vrVert_2^2 = sum_{k=1}^n v_k^2 leq sum_{k=1}^n v_k = 1$$
(more generally, $lVert vrVert_p leq lVert vrVert_q$ if $pgeq qgeq 1$).




Upshot: the squared $ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $ell_2$ norm:
$$
lVert u-vrVert_2^2 = lVert vrVert_2^2 - frac{1}{n}
$$

which can itself be interpreted as the collision probability
$$
lVert vrVert_2^2 = mathbb{P}_{v}{ X=Y}
$$

where $X,Y$ are independent random variables with pmf $v$.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
    $endgroup$
    – Clement C.
    Dec 16 '18 at 18:49


















1












$begingroup$

First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform,
$$
lVert u-vrVert_2 leq lVert urVert_2+ lVert vrVert_2 = frac{1}{sqrt{n}} + 1
$$



Now, for the stronger claim. Observe that
$$begin{align}
lVert u-vrVert_2^2 &= sum_{k=1}^n (u_k-v_k)^2 =
sum_{k=1}^n u_k^2 + sum_{k=1}^n v_k^2 - 2sum_{k=1}^n u_k v_k
= ncdot frac{1}{n^2} + lVert vrVert_2^2 - frac{2}{n}sum_{k=1}^n v_k\
&= frac{1}{n} + lVert vrVert_2^2 - frac{2}{n}
= lVert vrVert_2^2 - frac{1}{n} \
&leq 1 - frac{1}{n}
end{align}$$

where the last inequality comes from the fact that $$lVert vrVert_2^2 = sum_{k=1}^n v_k^2 leq sum_{k=1}^n v_k = 1$$
(more generally, $lVert vrVert_p leq lVert vrVert_q$ if $pgeq qgeq 1$).




Upshot: the squared $ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $ell_2$ norm:
$$
lVert u-vrVert_2^2 = lVert vrVert_2^2 - frac{1}{n}
$$

which can itself be interpreted as the collision probability
$$
lVert vrVert_2^2 = mathbb{P}_{v}{ X=Y}
$$

where $X,Y$ are independent random variables with pmf $v$.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
    $endgroup$
    – Clement C.
    Dec 16 '18 at 18:49
















1












1








1





$begingroup$

First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform,
$$
lVert u-vrVert_2 leq lVert urVert_2+ lVert vrVert_2 = frac{1}{sqrt{n}} + 1
$$



Now, for the stronger claim. Observe that
$$begin{align}
lVert u-vrVert_2^2 &= sum_{k=1}^n (u_k-v_k)^2 =
sum_{k=1}^n u_k^2 + sum_{k=1}^n v_k^2 - 2sum_{k=1}^n u_k v_k
= ncdot frac{1}{n^2} + lVert vrVert_2^2 - frac{2}{n}sum_{k=1}^n v_k\
&= frac{1}{n} + lVert vrVert_2^2 - frac{2}{n}
= lVert vrVert_2^2 - frac{1}{n} \
&leq 1 - frac{1}{n}
end{align}$$

where the last inequality comes from the fact that $$lVert vrVert_2^2 = sum_{k=1}^n v_k^2 leq sum_{k=1}^n v_k = 1$$
(more generally, $lVert vrVert_p leq lVert vrVert_q$ if $pgeq qgeq 1$).




Upshot: the squared $ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $ell_2$ norm:
$$
lVert u-vrVert_2^2 = lVert vrVert_2^2 - frac{1}{n}
$$

which can itself be interpreted as the collision probability
$$
lVert vrVert_2^2 = mathbb{P}_{v}{ X=Y}
$$

where $X,Y$ are independent random variables with pmf $v$.







share|cite|improve this answer











$endgroup$



First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform,
$$
lVert u-vrVert_2 leq lVert urVert_2+ lVert vrVert_2 = frac{1}{sqrt{n}} + 1
$$



Now, for the stronger claim. Observe that
$$begin{align}
lVert u-vrVert_2^2 &= sum_{k=1}^n (u_k-v_k)^2 =
sum_{k=1}^n u_k^2 + sum_{k=1}^n v_k^2 - 2sum_{k=1}^n u_k v_k
= ncdot frac{1}{n^2} + lVert vrVert_2^2 - frac{2}{n}sum_{k=1}^n v_k\
&= frac{1}{n} + lVert vrVert_2^2 - frac{2}{n}
= lVert vrVert_2^2 - frac{1}{n} \
&leq 1 - frac{1}{n}
end{align}$$

where the last inequality comes from the fact that $$lVert vrVert_2^2 = sum_{k=1}^n v_k^2 leq sum_{k=1}^n v_k = 1$$
(more generally, $lVert vrVert_p leq lVert vrVert_q$ if $pgeq qgeq 1$).




Upshot: the squared $ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $ell_2$ norm:
$$
lVert u-vrVert_2^2 = lVert vrVert_2^2 - frac{1}{n}
$$

which can itself be interpreted as the collision probability
$$
lVert vrVert_2^2 = mathbb{P}_{v}{ X=Y}
$$

where $X,Y$ are independent random variables with pmf $v$.








share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 17 '18 at 0:07

























answered Dec 16 '18 at 18:34









Clement C.Clement C.

50.9k33992




50.9k33992












  • $begingroup$
    Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
    $endgroup$
    – Clement C.
    Dec 16 '18 at 18:49




















  • $begingroup$
    Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
    $endgroup$
    – Clement C.
    Dec 16 '18 at 18:49


















$begingroup$
Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
$endgroup$
– Clement C.
Dec 16 '18 at 18:49






$begingroup$
Note: the reason for the last comment in the "upshot" is that this view of the $ell_2$ distance to uniform as directly related to the collision probability is the basis for most uniformity testing algorithms (given i.i.d. realizations from a discrete r.v., decide whether its distribution is uniform vs. far from uniform). I figured it was worth mentioning.
$endgroup$
– Clement C.
Dec 16 '18 at 18:49




















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3042911%2fthe-ell-2-norm-of-two-stochastic-vectors%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

Willebadessen

Ida-Boy-Ed-Garten

Residenzschloss Arolsen