Let U and V be two dependent discrete random variables, each
being uniformly distributed on {1, 2, . . . , k}. Let W be another
random variable having the same uniform distribution but independent of U and V . Define a random variable X = (V + W)
mod k. Show that
(a) X is uniformly distributed on {0, 1, 2, . . . , k − 1},
(b) U and X are independent.
P(X=0)=P(V+W=k)+P(V+W=2k)
P(X=i)=P(V+W=i)+P(V+W=k+i)
Nit being able to bring it in the form of discrete uniform (0,1,2,..,k-1)
Please help
And also how to approach the second part
Best Answer
(a) Fix any $0\leq \ell\leq k-1$. $$\begin{align} \Pr[X=\ell] &= \Pr[V+W=\ell \bmod k] \\ &= \sum_{i=1}^k \Pr[V=i, (W+i=\ell\bmod k)] \\ &= \sum_{i=1}^k \Pr[V=i]\Pr[W+i=\ell\bmod k] \tag{$V,W$ independent}\\ &= \sum_{i=1}^k \frac{1}{k}\cdot\frac{1}{k} \tag{$V,W$ uniform}\\&=\frac{1}{k} \end{align}$$ where we used the fact that, for any $a\in \mathbb{Z}$, there exists a unique $1\leq b\leq k$ such that $a = b \bmod k$.
This shows that $X$ is indeed uniform on $\{0,1,2,\dots, k-1\}$.
(b) To prove that $U$ and $X$ are independent, let us compute, for $0\leq i \leq k-1$, $1\leq j\leq k$, \begin{align*} \Pr[X=i, U=j] &= \sum_{\ell=1}^k \Pr[X=i, U=j, V=\ell]\\ &= \sum_{\ell=1}^k \Pr[V+W=i \bmod k, U=j, V=\ell] \\ &= \sum_{\ell=1}^k \Pr[W=i-\ell \bmod k, U=j, V=\ell] \\ &= \sum_{\ell=1}^k \Pr[W=i-\ell \bmod k]\Pr[U=j, V=\ell] \tag{$W\perp \!\!\! \perp (U,V)$}\\ &= \frac{1}{k}\sum_{\ell=1}^k \Pr[U=j, V=\ell] \tag{$W$ uniform}\\ &= \frac{1}{k}\Pr[U=j] \\ &= \Pr[X=i]\Pr[U=j] \tag{$X$ uniform} \end{align*} showing the independence.