Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Delta(X,Y)$ denote the (variational) distance between two discrete random variables $X$ and $Y$. $\Delta(X,Y)$ is given by: $\Delta(X,Y)=\frac{1}{2}\sum_{v \in V} |\Pr[X=v] - \Pr[Y=v]|$. $V$ is the set of possible values for $X$ and $Y$. We can also see $\Delta(X,Y)$ as the distance between the distributions of $X$ and $Y$. Thus $\Delta(X,Y)=0$ means that the distributions of $X$ and $Y$ are the same.

Suppose that two positive integers $M$ and $K$ are given, with $M\leq K$. And let $X$ be a random variable that takes on values in $\{0,\ldots,M-1\}$, and $Y$ a random variable uniform on $\{0,\ldots,K-1\}$. Then the following holds: $\Delta(Y,X+Y)\leq \frac{M-1}{K}$.

I wrote it out several times but I don't get how they came up with that bound. Can anyone help me with this?

share|cite|improve this question
Are you assuming that X and Y are independent and/or that X is uniform? (I suspect that both answers are "no".) – Did Nov 13 '12 at 10:27

$\Pr(Y=v) = 1/K$ for every $0\le v< K$, while $\Pr(Y=v) = (v+1)/KM$ for every $0\le v<M$ (since there are $v+1$ solutions to $v_X + v_Y = v$ in the appropriate ranges) and $\Pr(Y=v) = 1/K$ for every $v\le M<K$ (since there are $M$ solutions to $v_X + v_Y = v$ in the appropriate ranges). Therefore \begin{align*} \Delta(X,X+Y) &= \frac12 \bigg( \sum_{v=0}^{M-1} \bigg( \frac 1K - \frac{v+1}{KM} \bigg) + \sum_{v=M}^{K-1} \bigg( \frac 1K - \frac1K \bigg) \bigg) \\ &= \frac12 \bigg( \frac MK - \frac{M(M+1)/2}{KM} \bigg) = \frac{M-1}{4K}. \end{align*} Perhaps the upper bound of $(M-1)/K$ comes from noticing that $\Pr(Y=v) = \Pr(X+Y=v)$ for all $M\le v<K$ and bounding the rest of the contribution to $\Delta(Y,X+Y)$ more trivially.

share|cite|improve this answer
This answer might have several typos. Could you check? – Did Nov 13 '12 at 10:26
I made it community wiki so anyone can fix typos if they find them. – Greg Martin Nov 14 '12 at 8:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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