I am working on the following exercise:
Let $X, Z$ be independent RVs with values in $\mathcal{X} = \{0, 1, \ldots , n − 1\}$
and with probability distributions $p_X$ and $p_Z$ respectively. Let $Y$ be the RV
$Y = X + Z \pmod n$ with values in $\mathcal{Y} = \mathcal{X}$ . Let $C = (X , P, Y)$ be a memoryless channel with input RV $X$, output RV $Y$ and transition matrix $P$.Show how we can compute P.
My Attempt: Let's first assume w.l.o.g that $Z$ takes a fixed value $z \in \{0, \ldots n-1\}$. By the definition of $Y$ as $Y = X + Z \pmod n$ we see that to have $Y = y$ for $y \in \{0, \ldots, n-1\}$ the RV $X$ has to assume the value $x = y-z \pmod n$. By the independence of $X$ and $Z$ we therefore have
$$p(y \mid x) = p(X = y-z \pmod n \mid Z = z) = p(X = y-z \pmod n) \cdot p(Z = z).$$
With this we have found an alternate expression for the entries of the transition matrix $P$, but I do not see how I could write it down concretely. Could you help me?
Best Answer
The distribution of $Y$ is a convolution of those of $X$ and $Z.$
Since $$P_Y[Y=y]=\sum_{x} P_X[X=x]P_Z[y-x]$$ so that for example $$P_Y[Y=0]=\sum_{x} P_X[X=x]P_Z[-x]$$ and $$P_Y[Y=1]=\sum_{x} P_X[X=x]P_Z[1-x]$$ we can write the transition matrix $P$ of the channel as a circulant $n\times n$ matrix with first row $$[P_Z[0],P_Z[n-1],\ldots,P_Z[1]],$$ and the next row a right cyclic shift of the first row, etc.