Arbitrarily varying channel

Template:Short description Template:No footnotes An arbitrarily varying channel (AVC) is a communication channel model used in coding theory, and was first introduced by Blackwell, Breiman, and Thomasian. This particular channel has unknown parameters that can change over time and these changes may not have a uniform pattern during the transmission of a codeword. $n$ uses of this channel can be described using a stochastic matrix $W^n:X^n\times$ $S^n\to Y^n$, where $X$ is the input alphabet, $Y$ is the output alphabet, and $W^n(y|x,s)$ is the probability over a given set of states $S$, that the transmitted input $x=(x_1,\dots ,x_n)$ leads to the received output $y=(y_1,\dots ,y_n)$. The state $s_i$ in set $S$ can vary arbitrarily at each time unit $i$. This channel was developed as an alternative to Shannon's Binary Symmetric Channel (BSC), where the entire nature of the channel is known, to be more realistic to actual network channel situations.

Capacities and associated proofs

Capacity of deterministic AVCs

An AVC's capacity can vary depending on the certain parameters.

$R$ is an achievable rate for a deterministic AVC code if it is larger than $0$, and if for every positive $\epsilon$ and $\delta$, and very large $n$, length-$n$ block codes exist that satisfy the following equations: $\frac{1}{n}\log N>R-\delta$ and $\underset{s\in S^n}{\max }\overline{e}(s)\le \epsilon$, where $N$ is the highest value in $Y$ and where $\overline{e}(s)$ is the average probability of error for a state sequence $s$. The largest rate $R$ represents the capacity of the AVC, denoted by $c$.

As you can see, the only useful situations are when the capacity of the AVC is greater than $0$, because then the channel can transmit a guaranteed amount of data $\le c$ without errors. So we start out with a theorem that shows when $c$ is positive in an AVC and the theorems discussed afterward will narrow down the range of $c$ for different circumstances.

Before stating Theorem 1, a few definitions need to be addressed:

• An AVC is symmetric if $\sum _{s\in S}W(y|x,s)U(s|x^{\prime })=\sum _{s\in S}W(y|x^{\prime },s)U(s|x)$ for every $(x,x^{\prime },y,s)$, where $x,x^{\prime }\in X$, $y\in Y$, and $U(s|x)$ is a channel function $U:X\to S$.
• $X_r$, $S_r$, and $Y_r$ are all random variables in sets $X$, $S$, and $Y$ respectively.
• $P_{X_r}(x)$ is equal to the probability that the random variable $X_r$ is equal to $x$.
• $P_{S_r}(s)$ is equal to the probability that the random variable $S_r$ is equal to $s$.
• $P_{X_r{S}_r{Y}_r}$ is the combined probability mass function (pmf) of $P_{X_r}(x)$, $P_{S_r}(s)$, and $W(y|x,s)$. $P_{X_r{S}_r{Y}_r}$ is defined formally as $P_{X_r{S}_r{Y}_r}(x,s,y)=P_{X_r}(x)P_{S_r}(s)W(y|x,s)$.
• $H(X_r)$ is the entropy of $X_r$.
• $H(X_r|Y_r)$ is equal to the average probability that $X_r$ will be a certain value based on all the values $Y_r$ could possibly be equal to.
• $I(X_r\wedge Y_r)$ is the mutual information of $X_r$ and $Y_r$, and is equal to $H(X_r)-H(X_r|Y_r)$.
• $I(P)=\underset{Y_r}{\min }I(X_r\wedge Y_r)$, where the minimum is over all random variables $Y_r$ such that $X_r$, $S_r$, and $Y_r$ are distributed in the form of $P_{X_r{S}_r{Y}_r}$.

Theorem 1: $c>0$ if and only if the AVC is not symmetric. If $c>0$, then $c=\underset{P}{\max }I(P)$.

Proof of 1st part for symmetry: If we can prove that $I(P)$ is positive when the AVC is not symmetric, and then prove that $c=\underset{P}{\max }I(P)$, we will be able to prove Theorem 1. Assume $I(P)$ were equal to $0$. From the definition of $I(P)$, this would make $X_r$ and $Y_r$ independent random variables, for some $S_r$, because this would mean that neither random variable's entropy would rely on the other random variable's value. By using equation $P_{X_r{S}_r{Y}_r}$, (and remembering $P_{X_r}=P$,) we can get,

$P_{Y_r}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_r}(s)W(y|x,s)$

$\equiv ($since $X_r$ and $Y_r$ are independent random variables, $W(y|x,s)=W^{\prime }(y|s)$ for some $W^{\prime })$

$P_{Y_r}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_r}(s)W^{\prime }(y|s)$

$\equiv ($because only $P(x)$ depends on $x$ now$)$

$P_{Y_r}(y)=\sum _{s\in S}{P}_{S_r}(s)W^{\prime }(y|s)[\sum _{x\in X}P(x)]$

$\equiv ($because $\sum _{x\in X}P(x)=1)$

$P_{Y_r}(y)=\sum _{s\in S}{P}_{S_r}(s)W^{\prime }(y|s)$

So now we have a probability distribution on $Y_r$ that is independent of $X_r$. So now the definition of a symmetric AVC can be rewritten as follows: $\sum _{s\in S}{W}^{\prime }(y|s)P_{S_r}(s)=\sum _{s\in S}{W}^{\prime }(y|s)P_{S_r}(s)$ since $U(s|x)$ and $W(y|x,s)$ are both functions based on $x$, they have been replaced with functions based on $s$ and $y$ only. As you can see, both sides are now equal to the $P_{Y_r}(y)$ we calculated earlier, so the AVC is indeed symmetric when $I(P)$ is equal to $0$. Therefore, $I(P)$ can only be positive if the AVC is not symmetric.

Proof of second part for capacity: See the paper "The capacity of the arbitrarily varying channel revisited: positivity, constraints," referenced below for full proof.

Capacity of AVCs with input and state constraints

The next theorem will deal with the capacity for AVCs with input and/or state constraints. These constraints help to decrease the very large range of possibilities for transmission and error on an AVC, making it a bit easier to see how the AVC behaves.

Before we go on to Theorem 2, we need to define a few definitions and lemmas:

For such AVCs, there exists:

- An input constraint $\mathrm{\Gamma }$ based on the equation $g(x)=\frac{1}{n}\sum _{i=1}^{n}g(x_i)$, where $x\in X$ and $x=(x_1,\dots ,x_n)$.

- A state constraint $\mathrm{\Lambda }$, based on the equation $l(s)=\frac{1}{n}\sum _{i=1}^{n}l(s_i)$, where $s\in X$ and $s=(s_1,\dots ,s_n)$.

- ${\mathrm{\Lambda }}_0(P)=\min \sum _{x\in X,s\in S}P(x)l(s)$

- $I(P,\mathrm{\Lambda })$ is very similar to $I(P)$ equation mentioned previously, $I(P,\mathrm{\Lambda })=\underset{Y_r}{\min }I(X_r\wedge Y_r)$, but now any state $s$ or $S_r$ in the equation must follow the $l(s)\le \mathrm{\Lambda }$ state restriction.

Assume $g(x)$ is a given non-negative-valued function on $X$ and $l(s)$ is a given non-negative-valued function on $S$ and that the minimum values for both is $0$. In the literature I have read on this subject, the exact definitions of both $g(x)$ and $l(s)$ (for one variable $x_i$,) is never described formally. The usefulness of the input constraint $\mathrm{\Gamma }$ and the state constraint $\mathrm{\Lambda }$ will be based on these equations.

For AVCs with input and/or state constraints, the rate $R$ is now limited to codewords of format $x_1,\dots ,x_N$ that satisfy $g(x_i)\le \mathrm{\Gamma }$, and now the state $s$ is limited to all states that satisfy $l(s)\le \mathrm{\Lambda }$. The largest rate is still considered the capacity of the AVC, and is now denoted as $c(\mathrm{\Gamma },\mathrm{\Lambda })$.

Lemma 1: Any codes where $\mathrm{\Lambda }$ is greater than ${\mathrm{\Lambda }}_0(P)$ cannot be considered "good" codes, because those kinds of codes have a maximum average probability of error greater than or equal to $\frac{N-1}{2N}-\frac{1}{n}\frac{l_{max}^2}{n(\mathrm{\Lambda }-{\mathrm{\Lambda }}_0(P){)}^2}$, where $l_{max}$ is the maximum value of $l(s)$. This isn't a good maximum average error probability because it is fairly large, $\frac{N-1}{2N}$ is close to $\frac{1}{2}$, and the other part of the equation will be very small since the $(\mathrm{\Lambda }-{\mathrm{\Lambda }}_0(P))$ value is squared, and $\mathrm{\Lambda }$ is set to be larger than ${\mathrm{\Lambda }}_0(P)$. Therefore, it would be very unlikely to receive a codeword without error. This is why the ${\mathrm{\Lambda }}_0(P)$ condition is present in Theorem 2.

Theorem 2: Given a positive $\mathrm{\Lambda }$ and arbitrarily small $\alpha >0$, $\beta >0$, $\delta >0$, for any block length $n\ge n_0$ and for any type $P$ with conditions ${\mathrm{\Lambda }}_0(P)\ge \mathrm{\Lambda }+\alpha$ and $\underset{x\in X}{\min }P(x)\ge \beta$, and where $P_{X_r}=P$, there exists a code with codewords $x_1,\dots ,x_N$, each of type $P$, that satisfy the following equations: $\frac{1}{n}\log N>I(P,\mathrm{\Lambda })-\delta$, $\underset{l(s)\le \mathrm{\Lambda }}{\max }\overline{e}(s)\le \exp (-n\gamma )$, and where positive $n_0$ and $\gamma$ depend only on $\alpha$, $\beta$, $\delta$, and the given AVC.

Proof of Theorem 2: See the paper "The capacity of the arbitrarily varying channel revisited: positivity, constraints," referenced below for full proof.

Capacity of randomized AVCs

The next theorem will be for AVCs with randomized code. For such AVCs the code is a random variable with values from a family of length-n block codes, and these codes are not allowed to depend/rely on the actual value of the codeword. These codes have the same maximum and average error probability value for any channel because of its random nature. These types of codes also help to make certain properties of the AVC more clear.

Before we go on to Theorem 3, we need to define a couple important terms first:

$W_{\zeta }(y|x)=\sum _{s\in S}W(y|x,s)P_{S_r}(s)$
$I(P,\zeta )$ is very similar to the $I(P)$ equation mentioned previously, $I(P,\zeta )=\underset{Y_r}{\min }I(X_r\wedge Y_r)$, but now the pmf $P_{S_r}(s)$ is added to the equation, making the minimum of $I(P,\zeta )$ based a new form of $P_{X_r{S}_r{Y}_r}$, where $W_{\zeta }(y|x)$ replaces $W(y|x,s)$.

Theorem 3: The capacity for randomized codes of the AVC is $c=ma{x}_{P}I(P,\zeta )$.

Proof of Theorem 3: See paper "The Capacities of Certain Channel Classes Under Random Coding" referenced below for full proof.

See also

• Binary symmetric channel
• Binary erasure channel
• Z-channel (information theory)
• Channel model
• Information theory
• Coding theory

References

• Ahlswede, Rudolf and Blinovsky, Vladimir, "Classical Capacity of Classical-Quantum Arbitrarily Varying Channels," https://ieeexplore.ieee.org/document/4069128
• Blackwell, David, Breiman, Leo, and Thomasian, A. J., "The Capacities of Certain Channel Classes Under Random Coding," https://www.jstor.org/stable/2237566
• Csiszar, I. and Narayan, P., "Arbitrarily varying channels with constrained inputs and states," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2598&isnumber=154
• Csiszar, I. and Narayan, P., "Capacity and Decoding Rules for Classes of Arbitrarily Varying Channels," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=32153&isnumber=139
• Csiszar, I. and Narayan, P., "The capacity of the arbitrarily varying channel revisited: positivity, constraints," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155
• Lapidoth, A. and Narayan, P., "Reliable communication under channel uncertainty," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554