On lower bounds for the redundancy of optimal codes

The problem of providing bounds on the redundancy of an optimal code for a discrete memoryless source in terms of the probability distribution of the source, has been extensively studied in the literature. The attention has m ainly focused on binary codes for the case when the most or the least likel y source letter probabilities are known. In this paper we analyze the relationships among tight lower bounds on the redundancy r. Let r greater than or equal to phi(D,i)(x) be the tight lower bound on r for D-ary codes in terms of the value x of the i-th most likely source letter probability. We prove that phi(D,i-1)(x) less than or equal to phi(D,i)(x) for all possible x and i. As a consequence, we can bound the redundancy when only the value of a probability (but not its rank) is know n. Another consequence is a shorter and simpler proof of a known bound. We also provide some other properties of tight lower bounds. Finally, we deter mine an achievable lower bound on r in terms of the least likely source let ter probability for D greater than or equal to 3, generalizing the known bo und for the case D = 2.