A simple derivation of the refined sphere packing bound under certain symmetry hypotheses

A judicious application of the Berry-Esseen theorem via suitable Augustin information measures is demonstrated to be sufficient for deriving the sphere packing bound with a prefactor that is Ω n −0.5 1−E′ sp R for all codes on certain families of channels including the Gaussian channels and the nonstationary Rényi symmetric channels and for the constant composition codes on stationary memoryless channels. The resulting nonasymptotic bounds have definite approximation error terms. As a preliminary result that might be of interest on its own, the trade-off between type I and type II error probabilities in the hypothesis testing problem with possibly non-stationary independent samples is determined up to some multiplicative constants, assuming that the probabilities of both types of error are decaying exponentially with the number of samples, using the Berry-Esseen theorem.

Keywords:

Hypothesis testing, Berry-Esseen theorem, sphere packing bound, Augustin information measures, constant composition codes, Renyi symmetry Gaussian channels,

PDF

___

[1] Altuğ Y, Wagner AB. Refinement of the sphere packing bound for symmetric channels. In: 49th Annual Allerton Conference on Communication, Control, and Computing; Monticello, IL, USA; 2011. pp. 30-37. doi: 10.1109/Allerton.2011.6120146
[2] Altuğ Y, Wagner AB. Refinement of the sphere-packing bound: asymmetric channels. IEEE Transactions on Information Theory 2014; 60 (3):1592-1614. doi: 10.1109/TIT.2014.2299275
[3] Altuğ Y, Wagner AB. On exact asymptotics of the error probability in channel coding: symmetric channels 2019. arXiv:1908.11419 [cs.IT].
[4] Arikan E. On the reliability exponent of the exponential timing channel. IEEE Transactions on Information Theory 2002; 48 (6): 1681-1689. doi:10.1109/TIT.2002.1003846
[5] Augustin U. Error estimates for low rate codes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 1969; 14 (1): 61-88. doi:10.1007/BF00534118
[6] Augustin U. Noisy Channels. Habilitation thesis, Universität Erlangen-Nürnberg, Erlangen, Germany, 1978.
[7] Bahadur RR, Ranga Rao R. On deviations of the sample mean. The Annals of Mathematical Statistics 1960; 31 (4): 1015-1027. doi: 10.1214/aoms/1177705674
[8] Berry AC. The accuracy of the Gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society 1941; 49 (1): 122-136. doi: 10.2307/1990053
[9] Burnashev MV, Kutoyants YuA. On the sphere-packing bound, capacity, and similar results for Poisson channels. Problems of Information Transmission 1999; 35 (2): 95-111.
[10] Cheng HC, Hsieh MH, Tomamichel M. Quantum sphere-packing bounds with polynomial prefactors. IEEE Transactions on Information Theory 2019; 65 (5): 2872-2898. doi: 10.1109/TIT.2019.2891347
[11] Cheng HC, Nakiboğlu B. Refined strong converse for the constant composition codes 2020. arXiv:2002.11414 [cs.IT].
[12] Csiszár I, Longo G. On the error exponent for source coding and for testing simple statistical hypotheses. Studia Scientiarum Mathematicarum Hungarica 1971; 6:181-191.
[13] Csiszár I, Körner J. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, Cambridge, UK, 2011.
[14] Dalai M. Lower bounds on the probability of error for classical and classical-quantum channels. IEEE Transactions on Information Theory 2013; 59 (12): 8027-8056. doi:10.1109/TIT.2013.2283794
[15] Dalai M, Winter A. Constant compositions in the sphere packing bound for classical-quantum channels. IEEE Transactions on Information Theory 2017; 63 (9): 5603-5617. doi:10.1109/TIT.2017.2726555
[16] Dobrushin RL. Asymptotic estimates of the probability of error for transmission of messages over a discrete memoryless communication channel with a symmetric transition probability matrix. Theory of Probability and Its Applications 1962; 7 (3): 270-300. doi: 10.1137/1107027
[17] Dobrushin RL. An asymptotic bound for the probability error of information transmission through a channel without memory using the feedback. Problemy Kibernetiki 1962; (8): 161-168.
[18] Ebert PM. Error Bounds For Parallel Communication Channels, Technical Report 448, Research Laboratory of Electronics at Massachusetts Institute of Technology. Cambridge, MA, USA: Massachusetts Institute of Technology, 1966.
[19] Elias P. Coding for two noisy channels. In: Proceedings of Third London Symposium of Information Theory; London, UK; Butterworth Scientific, 1955. pp. 61-74.
[20] Van Erven T, Harremoës P. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory 2014; 60 (7): 3797-3820. doi: 10.1109/TIT.2014.2320500
[21] Esseen CG. On the Liapunoff limit of error in the theory of probability. Arkiv för Matematik, Astronomi Och Fysik 1942; A28: 1-19.
[22] Esseen CG. Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law. Acta Mathematica 1945; 77: 1-125. doi:10.1007/BF02392223
[23] Gallager RG. A simple derivation of the coding theorem and some applications. IEEE Transactions on Information Theory 1965; 11 (1): 3-18. doi: 10.1109/TIT.1965.1053730
[24] Gallager RG. Information theory and reliable communication. New York, NY, USA: John Wiley & Sons, Inc.,1968.
[25] Gnedenko BV, Kolmogorov AN. Limit Distributions for Sums of Independent Random Variables. Cambridge, MA, USA: Addison-Wesley, 1954.
[26] Haroutunian EA. Bounds for the exponent of the probability of error for a semicontinuous memoryless channel. Problems of Information Transmission 1968; 4 (4).
[27] Haroutunian EA. Lower bound for error probability in channels with feedback. Problems of Information Transmission 1977; 13 (2):107-114.
[28] Holevo AS. Remarks on the classical capacity of quantum channel. 2002. arXiv:quant-ph/0212025.
[29] Jensen JL. Saddlepoint approximations. New York, NY, USA: Oxford University Press, 1995.
[30] Lancho A, Östman J, Durisi G, Koch T, and Vazquez-Vilar G. Saddlepoint approximations for noncoherent singleantenna rayleigh block-fading channels. In: 2019 International Symposium on Information Theory; Paris, France; 2019. pp.612-616. doi:10.1109/ISIT.2019.8849659
[31] Lancho A, Östman J, Durisi G, Koch T, and Vazquez-Vilar G. Saddlepoint approximations for short-packet wireless communications. 2019. arXiv:1904.10442 [cs.IT].
[32] Lapidoth A. On the reliability function of the ideal Poisson channel with noiseless feedback. IEEE Transactions on Information Theory 1993; 39 (2): 491-503. doi: 10.1109/18.212279
[33] Nakiboğlu B. The Augustin center and the sphere packing bound for memoryless channels. In: 2017 International Symposium on Information Theory; Aachen, Germany; 2017. pp.1401-1405. doi: 10.1109/ISIT.2017.8006759
[34] Nakiboğlu B. The sphere packing bound for memoryless channels. 2018. arXiv:1804.06372 [cs.IT].
[35] Nakiboğlu B. The Augustin capacity and center. Problems of Information Transmission 2019; 55 (4): 299-342. doi: 10.1134/S003294601904001 (arXiv:1803.07937 [cs.IT])
[36] Nakiboğlu B. The Rényi capacity and center. IEEE Transactions on Information Theory 2019; 65 (2): 841-860. doi: 10.1109/TIT.2018.2861002
[37] Nakiboğlu B. A simple derivation of the refined spb for the constant composition codes. In: 2019 International Symposium on Information Theory; Paris, France; 2019. pp. 2659-2663. doi: 10.1109/ISIT.2019.8849819
[38] Nakiboğlu B. The sphere packing bound for DSPCs with feedback à la Augustin. IEEE Transactions on Communications 2019; 67 (11): 7456-7467. doi: 10.1109/TCOMM.2019.2931302
[39] Nakiboğlu B. The sphere packing bound via Augustin’s method. IEEE Transactions on Information Theory 2019; 65 (2): 816-840. doi: 10.1109/TIT.2018.2882547
[40] Omura JK. A lower bounding method for channel and source coding probabilities. Information and Control 1975; 27 (2): 148-177. doi: 10.1016/S0019-9958(75)90120-5
[41] Richters JS. Communication over fading dispersive channels, Technical report 464, Research Laboratory of Electronics at Massachusetts Institute of Technology. Cambridge, MA, USA: Massachusetts Institute of Technology, 1967.
[42] Rudin W. Principles of Mathematical Analysis. New York, NY, USA: McGraw-Hill, 1976.
[43] Shannon CE. Probability of error for optimal codes in a Gaussian channel. Bell System Technical Journal 1959; 38 (3): 611-656. doi: 10.1002/j.1538-7305.1959.tb03905.x
[44] Shannon CE, Gallager RG, Berlekamp ER. Lower bounds to error probability for coding on discrete memoryless channels. I. Information and Control 1967; 10 (1): 65-103. doi: 10.1016/S0019-9958(67)90052-6
[45] Shevtsova IG. An improvement of convergence rate estimates in the Lyapunov theorem. Doklady Mathematics 2010; 82 (3): 862-864. doi: 10.1134/S1064562410060062
[46] Strassen V. Asymptotische abschätzungen in Shannons Informationstheorie (in German). In: Transactions of the Third Prague Conference on Information Theory, Statistical Decision Functions, Random Processes. Prague, Czech Republic: Czechoslovak Academy of Sciences, 1962. pp. 689-723.
[47] Vazquez-Vilar G. Error probability bounds for gaussian channels under maximal and average power constraints. 2019. arXiv:1907.03163 [cs.IT].
[48] Vazquez-Vilar G, i Fabregas AG, Koch T, Lancho A. Saddlepoint approximation of the error probability of binary hypothesis testing. In: 2018 International Symposium on Information Theory; Colorado, USA; 2018. pp. 2306-2310. doi: 10.1109/ISIT.2018.8437503
[49] Wiechman G, Sason I. An improved sphere-packing bound for finite-length codes over symmetric memoryless channels. IEEE Transactions on Information Theory 2008; 54 (5): 1962-1990. doi: 10.1109/TIT.2008.920216
[50] Wyner AD. Capacity and error exponent for the direct detection photon channel. II. IEEE Transactions on Information Theory 1988; 34 (6): 1462-1471. doi: 10.1109/18.21285

ISSN: 1300-0098
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv