Always Good Turing: Asymptotically Optimal Probability Estimation Export

@inproceedings{citeulike:258767, abstract = {While deciphering the Enigma Code during World War II, I.J. Good and A.M. Turing considered the problem of estimating a probability distribution from a sample of data. They derived a surprising and un- intuitive formula that has since been used in a va- riety of applications and studied by a number of re- searchers. Borrowing an information-theoretic and machine-learning framework, we de¯ne the attenua- tion of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily-long sequence by any distribution, and the corresponding probability assigned by the estima- tor. We show that some common estimators have in¯- nite attenuation and that the attenuation of the Good- Turing estimator is low, yet larger than one. We then derive an estimator whose attenuation is one, namely, as the length of any sequence increases, the per-symbol probability assigned by the estimator is as high as pos- sible. Interestingly, some of the proofs use celebrated results by Hardy and Ramanujan on the number of partitions of an integer. To better understand the be- havior of the estimator, we study the probability it as- signs to several simple sequences. We show that for some sequences this probability agrees with our intu- ition, while for others it is rather unexpected.}, author = {Orlitsky, Alon and Santhanam, Narayana P. and Zhang, Junan}, citeulike-article-id = {258767}, citeulike-linkout-0 = {http://bloglines.com/myblogs}, citeulike-linkout-1 = {http://kodiak.ucsd.edu/alon/papers/alw_gd_trn.pdf}, journal = {FOCS}, keywords = {cryptography, estimator, probability, turing}, posted-at = {2005-07-18 08:49:45}, priority = {2}, title = {Always Good Turing: Asymptotically Optimal Probability Estimation}, url = {http://bloglines.com/myblogs} }

TY - CONF ID - citeulike:258767 L3 - citeulike-article-id:258767 N2 - While deciphering the Enigma Code during World War II, I.J. Good and A.M. Turing considered the problem of estimating a probability distribution from a sample of data. They derived a surprising and un- intuitive formula that has since been used in a va- riety of applications and studied by a number of re- searchers. Borrowing an information-theoretic and machine-learning framework, we de¯ne the attenua- tion of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily-long sequence by any distribution, and the corresponding probability assigned by the estima- tor. We show that some common estimators have in¯- nite attenuation and that the attenuation of the Good- Turing estimator is low, yet larger than one. We then derive an estimator whose attenuation is one, namely, as the length of any sequence increases, the per-symbol probability assigned by the estimator is as high as pos- sible. Interestingly, some of the proofs use celebrated results by Hardy and Ramanujan on the number of partitions of an integer. To better understand the be- havior of the estimator, we study the probability it as- signs to several simple sequences. We show that for some sequences this probability agrees with our intu- ition, while for others it is rather unexpected. JF - FOCS TI - Always Good Turing: Asymptotically Optimal Probability Estimation KW - cryptography KW - estimator KW - probability KW - turing AU - Orlitsky, Alon AU - Santhanam, Narayana AU - Zhang, Junan UR - http://bloglines.com/myblogs ER -