List Decoding - List-decoding Capacity - Sketch of Proof

Sketch of Proof

The idea behind the proof is similar to that of Shannon's proof for capacity of the binary symmetric channel where a random code is picked and showing that it is (, )-list-decodable with high probability as long as the rate . For rates exceeding the above quantity, it can be shown that the list size becomes super-polynomially large.

A "bad" event is defined as one in which, given a received word and messages, it so happens that, for every where is the fraction of errors that we wish to correct and is the Hamming ball of radius with the received word as the center.

Now, the probability that a codeword associated with a fixed message lies in a Hamming ball is given by

where the quantity is the volume of a Hamming ball of radius with the received word as the center. The inequality in the above relation follows from the upper bound on the volume of a Hamming ball. The quantity gives a very good estimate on the volume of a Hamming ball of radius centered around any word in . Put another way, the volume of a Hamming ball is translation invariant. To continue with the proof sketch, we conjure the union bound in probability theory which tells us that the probability of a bad event happening for a given is upper bounded by the quantity .

With the above in mind, the probability of "any" bad event happening can be shown to be less than . To show this, we work our way over all possible received words and every possible subset of messages in .

Now turning to the proof of part (ii), we need to show that there are super-polynomially many codewords around every when the rate exceeds the list-decoding capacity. We need to show that is super-polynomially large if the rate . Fix a codeword . Now, for every picked at random, we have

since Hamming balls are translation invariant. From the definition of the volume of a Hamming ball and the fact that is chosen uniformly at random from we also have

Let us now define an indicator variable such that

0 otherwise.

Taking the expectation of the volume of a Hamming ball we have


begin{align}
E & = sum E text{ for every } c in mathcal{C} \
& = sum Prtext{ for every } c in mathcal{C} \
& ge sum q^{-n(1 - H_q(p) + o(n))} \
& = sum q^{n} \
& ge q^{Omega(n)}
end{align}

Therefore, by the probabilistic method, we have shown that if the rate exceeds the list-decoding capacity, then the list size becomes super-polynomially large. This completes the proof sketch for the list-decoding capacity.

Read more about this topic:  List Decoding, List-decoding Capacity

Famous quotes containing the words proof and/or sketch:

    There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.
    Herman Melville (1819–1891)

    the vagabond began
    To sketch a face that well might buy the soul of any man.
    Then, as he placed another lock upon the shapely head,
    With a fearful shriek, he leaped and fell across the
    picture—dead.
    Hugh Antoine D’Arcy (1843–1925)