0
$\begingroup$

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?

  • 0
    Are you assuming that X and Y are independent and/or that X is uniform? (I suspect that both answers are "no".)2012-11-13

1 Answers 1

1

$\Pr(Y=v) = 1/K$ for every $0\le v< K$, while $\Pr(Y=v) = (v+1)/KM$ for every $0\le v (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 (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 and bounding the rest of the contribution to $\Delta(Y,X+Y)$ more trivially.

  • 0
    I made it community wiki so anyone can fix typos if they find them.2012-11-14