q-ary symmetric channel error probability

Question

Why is it valid to assume that $0< p < (q-1)/q$, where $p$ is the probability of symbol error. When $(q-1) / q< p <1$, why are we able to flip it? We are not in binary channel, so we are not able to flip all 1 to 0, all 0 to 1, how can we do that? My thought is to randomly pick any other symbol at an equal probability

Answer 1

In a $q$-ary channel with input and output alphabet $\{0,1, \ldots, q-1\}$, consider the transition probabilities $p_{i,j}$ that tell us the probability that a transmitted $i$ is received as a $j$. Note that for each $i$, $\sum_{j=0}^{q-1} p_{i,j} = 1$ since something must be received when $i$ is transmitted. In a $q$-ary symmetric channel, all the $p_{i,j}$ have the same value $\hat{p}$ for all $i\neq j$ while all the $p_{i,i}$ have the same value $\alpha$. Thus, $$\hat{p}(q-1) + \alpha = 1.$$ The OP defines the probability of symbol error as $p = \hat{p}(q-1)$ -- it is the probability that an incorrect symbol is received -- and so we have that $p+\alpha = 1$.

Now, of the $q$ numbers $p_{i,0}, p_{i,0}, \ldots, p_{i,q-1}$ whose sum is $1$, at least one, hopefully $p_{i,i} = \alpha$, must be larger than $\frac 1q$ because if none of the $p_{I,j}$ exceed $\frac 1q$, then they must all will equal $\frac 1q$ and the channel will be useless: the output will be independent of the input. So, since $p+\alpha = 1$ and $\alpha > \frac 1q$, we see that $$p + \frac 1q < 1 \implies p < 1 - \frac 1q = \frac{q-1}{q}.$$

So why does this argument not work when $q = 2$?? well for the binary symmetric channel, if $p > \frac 12 = \frac{q-1}{q}\big\vert_{q=2}$, as mathematicians we can just cuss the engineer for mis-labeling the channel outputs and tell him to flip the output bits, thus converting the binary symmetric channel with crossover probability $p > \frac 12$ into a binary symmetric channel with crossover probability $1-p < \frac 12$. Unfortunately such "flipping" does not work when $q>2$