Change search
ReferencesLink to record
Permanent link

Direct link
Exact Probability Distribution versus Entropy
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science.ORCID iD: 0000-0001-6302-7006
2014 (English)In: Entropy, ISSN 1099-4300, E-ISSN 1099-4300, Vol. 16, no 10, 5198-5210 p.Article in journal (Refereed) Published
Abstract [en]

The problem addressed concerns the determination of the average numberof successive attempts of guessing a word of a certain length consisting of letters withgiven probabilities of occurrence. Both first- and second-order approximations to a naturallanguage are considered. The guessing strategy used is guessing words in decreasing orderof probability. When word and alphabet sizes are large, approximations are necessary inorder to estimate the number of guesses. Several kinds of approximations are discusseddemonstrating moderate requirements regarding both memory and central processing unit(CPU) time. When considering realistic sizes of alphabets and words (100), the numberof guesses can be estimated within minutes with reasonable accuracy (a few percent) andmay therefore constitute an alternative to, e.g., various entropy expressions. For manyprobability distributions, the density of the logarithm of probability products is close to anormal distribution. For those cases, it is possible to derive an analytical expression for theaverage number of guesses. The proportion of guesses needed on average compared to thetotal number decreases almost exponentially with the word length. The leading term in anasymptotic expansion can be used to estimate the number of guesses for large word lengths.Comparisons with analytical lower bounds and entropy expressions are also provided.

Place, publisher, year, edition, pages
Basel, Switzerland: MDPI AG , 2014. Vol. 16, no 10, 5198-5210 p.
Keyword [en]
information entropy, security, guessing
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:kau:diva-34247DOI: 10.3390/e16105198ISI: 000344459500003OAI: diva2:754175
Available from: 2014-10-09 Created: 2014-10-09 Last updated: 2016-05-19Bibliographically approved

Open Access in DiVA

entropy-16-05198.pdf(636 kB)58 downloads
File information
File name FULLTEXT01.pdfFile size 636 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Andersson, Kerstin
By organisation
Department of Mathematics and Computer Science
In the same journal
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 58 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 128 hits
ReferencesLink to record
Permanent link

Direct link