Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

$\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|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
add comment

Your Answer

 
discard

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.