Bounding Gallager’s Expurgated Bound

In dalai-ISIT-2013b, dalai-TIT-2013, a modification of the Lovász theta function, called ϑ(ρ), was introduced for the purpose of studying error exponents for codes over discrete memoryless channels. It was mentioned that this function allows one to upper bound the multi-letter version of Gallager’s expurgated lower bound on the reliability function, but this property was only proved for some particular cases. In this letter, we give a general proof and we show how this can be used for the evaluation of the expurgated bound. We finally consider some algebraic properties of the function ϑ(ρ). IEEE