The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
An inequality on guessing and its application to sequential decoding
Open accessAbstract
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 decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X|Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X|Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344305 · Cited by 5,399
On Measures of Entropy and Information
Rényi, A. (1961) · Project Euclid (Cornell University) · Cited by 4,031
Information Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,012
A simple derivation of the coding theorem and some applications
Gallager, R. (1965) · IEEE Transactions on Information Theory · doi:10.1109/tit.1965.1053730 · Cited by 687
Fast Sequential Decoding Algorithm Using a Stack
Jelinek, F. (1969) · IBM Journal of Research and Development · doi:10.1147/rd.136.0675 · Cited by 541
A heuristic discussion of probabilistic decoding
Fano, R. (1963) · IEEE Transactions on Information Theory · doi:10.1109/tit.1963.1057827 · Cited by 494
Massey, J. L. (2002) · Proceedings of 1994 IEEE International Symposium on Information Theory · doi:10.1109/isit.1994.394764 · Cited by 463
Generalized cutoff rates and Renyi's information measures
Csiszár, I. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.370121 · Cited by 348
Sequential decoding for reliable communication
Wozencraft, J. M. (1957) · Cited by 141
An upper bound on moments of sequential decoding effort
Jelinek, F. (1969) · IEEE Transactions on Information Theory · doi:10.1109/tit.1969.1054264 · Cited by 62
Metadata
- Authors
- Arikan, E.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1996
- Volume
- 42
- Issue
- 1
- Pages
- 99-105
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2165203736
- Cited by
- 308
- References
- 11
- FWCI
- 5.35
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: An inequality on guessing and its application to sequential decoding. https://app.cochat.ai/papers/10.1109/18.481781
- The paper
- Arikan, E. (1996). An inequality on guessing and its application to sequential decoding. IEEE Transactions on Information Theory. https://doi.org/10.1109/18.481781
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.