publication . Article . Conference object . 1996

An inequality on guessing and its application to sequential decoding

Arıkan, Erdal;
Open Access
  • Published: 01 Jan 1996 Journal: IEEE Transactions on Information Theory, volume 42, pages 99-105 (issn: 0018-9448, Copyright policy)
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • Country: Turkey
Abstract
Let (X,Y) be a pair of discrete random variables with X taking one of M possible values, Suppose the value of X is to be determined, given the value of Y, by asking questions of the form "Is X equal to x?" until the answer is "Yes". Let G(x|y) denote the number of guesses in any such guessing scheme when X=x, Y=y. We prove that E[G(X|Y)/sup /spl rho//]/spl ges/(1+lnM)/sup -/spl rho///spl Sigma//sub y/[/spl Sigma//sub x/P/sub X,Y/(x,y)/sup 1/1+/spl rho//]/sup 1+/spl rho// for any /spl rho//spl ges/0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decod...
Subjects
arXiv: Computer Science::Information TheoryComputer Science::Software Engineering
ACM Computing Classification System: Data_CODINGANDINFORMATIONTHEORY
free text keywords: Decoding, Random variables, Entropy, Computational complexity, Communication channels, Memoryless systems, Information theory, Random processes, Probability distribution, Estimation theory, Algorithms, Codes (symbols), Communication Channels (information Theory), Communication Systems, Computational Methods, Probability, Theorem Proving, Finite Input Alphabets, Guessing Function, Holder Inequality, Memoryless Channels, Renyi Entropy, Sequential Decoding, Shannon Entropy, Tree Code, H infinity control
Related Organizations
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue