Return to Answer

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$, is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant correlation matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$, is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant convolution matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$,is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant correlation matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$, is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant correlation matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$, is the conditional distribution $P(Y|X,N)$ that is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant correlation matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.

This answer is a bit late, but the problem has quite an elegant solution based on the Fourier transform and I wanted to add it.

The action of the BSC can be modeled as a$\pmod 2$ sum of the data bit, $X$, and a random noise bit, $N$, who's probability distribution is $P(N=0)=1-p$ and $P(N=1)=p$,

$$Y = X \oplus N.$$

The distribution over the output, $Y$,is a convolution of the quantities $P(X)$ and $P(N)$,

$$P(Y=y) = \sum_{x \in \{0,1\}} P(X=x)P(N=x\oplus y).$$

This is a linear transformation of the probabilities. The circulant correlation matrix obtained from one of the vectors is diagonalized by the 2x2 DFT Hadamard matrix,

$$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and the convolution becomes a product of spectra in the transform domain. The sum of $L$ identically distributed noise bits corresponds to exponentiation in the transform domain followed by an inverse transform,

$$H^{-1}\left(H\begin{bmatrix}1-p\\p\end{bmatrix}\right)^L = \frac{1}{2}\begin{bmatrix}{1 + (1 - 2p)^L}\\{1 - (1 - 2p)^L}\end{bmatrix},$$

where the second element of the result vector represents the probability $P(N_1 \oplus N_2 \oplus N_3 \oplus \ldots \oplus N_L = 1)$, which is the flip probability for the cascaded BSC.