#ConradMitzenmacher-7
"A. Notation and Terminology
Throughout this paper, the phrase ›log-ratio‹ for a pair of positive real numbers refers to the ratio of their logarithms (to a common base, the choice of which cancels out)..
All logarithms without an indicated base
>
"A. Notation and Terminology
Throughout this paper, the phrase ›log-ratio‹ for a pair of positive real numbers refers to the ratio of their logarithms (to a common base, the choice of which cancels out)..
All logarithms without an indicated base
>
>are understood to be taken to the base 𝑒..
II. Review of Definitions and History
Our treatment here is based on a recent survey by Mitzenmacher [#Internet #Mathematics 1(2), 226‒251 (2004)], to which we refer the reader for more information.[ Footnote: For instance,
>
II. Review of Definitions and History
Our treatment here is based on a recent survey by Mitzenmacher [#Internet #Mathematics 1(2), 226‒251 (2004)], to which we refer the reader for more information.[ Footnote: For instance,
>
>this survey describes another argument that leads to a #PowerLaw of word frequency based on preferential attachment, originally due to Simon [Biometrika 42(3/4), 425–440 (1955)]. We do not present this argument here.]
In what follows, we let 𝑓ⱼ be the (asymptotic) fraction of>
In what follows, we let 𝑓ⱼ be the (asymptotic) fraction of>
>the time the 𝑗th most frequently used word appears.
..several words can have the same probability of occurrence..
..we will say that 𝑓ⱼ follows a #PowerLaw in 𝑗 if there exist..constants 𝑐₁,𝑐₂,α such that 𝑐₁𝑗^{–α}⩽𝑓ⱼ⩽𝑐₂𝑗^{–α} for sufficiently large 𝑗.
>
..several words can have the same probability of occurrence..
..we will say that 𝑓ⱼ follows a #PowerLaw in 𝑗 if there exist..constants 𝑐₁,𝑐₂,α such that 𝑐₁𝑗^{–α}⩽𝑓ⱼ⩽𝑐₂𝑗^{–α} for sufficiently large 𝑗.
>
>
We sketch #Mandelbrot’s argument that leads to a power law in the rank-frequency distribution of words [Communication Theory, W. Jackson, Ed; Butterworth 1953, 486–502].
Consider some language consisting of 𝑊 words. The cost of transmitting the 𝑗th most frequent word
>
We sketch #Mandelbrot’s argument that leads to a power law in the rank-frequency distribution of words [Communication Theory, W. Jackson, Ed; Butterworth 1953, 486–502].
Consider some language consisting of 𝑊 words. The cost of transmitting the 𝑗th most frequent word
>
>of the language is denoted by 𝐶_𝑗.
For example, if we think of #English text, the cost of a word might be thought of as the number of letters plus the additional cost of a space. We therefore naturally expect the most frequent words to have the smallest number of letters.
>
For example, if we think of #English text, the cost of a word might be thought of as the number of letters plus the additional cost of a space. We therefore naturally expect the most frequent words to have the smallest number of letters.
>
>Let us take the cost of a space to be 0. Then if the alphabet size is N>1, there are N^k possible words of length k (including k=0; we allow the empty word for convenience). In particular, the words with letters have frequency ranks from 1+ (N^k-1)/(N-1) to (N^{k+1}-1)/(N-1).
>
>
>
[This is obviously true: before the "words with k letters" there are all the words from 0 to k-1 letters, and there are 1+N+N^2+...+N^{k-1} = N^k-1)/(N-1) of those. LG,I]
It follows that log_N 𝑗 ⩽ 𝐶_𝑗 ⩽ log_N 𝑗 +1.
Suppose that we wish to design the language to
>
[This is obviously true: before the "words with k letters" there are all the words from 0 to k-1 letters, and there are 1+N+N^2+...+N^{k-1} = N^k-1)/(N-1) of those. LG,I]
It follows that log_N 𝑗 ⩽ 𝐶_𝑗 ⩽ log_N 𝑗 +1.
Suppose that we wish to design the language to
>
>optimize the average amount of #information per unit transmission cost.
Here, we take the average amount of information to be the entropy. We think of each word in our transmission as being selected randomly, and the probability that a word in the transmission is the 𝑗th word
>
Here, we take the average amount of information to be the entropy. We think of each word in our transmission as being selected randomly, and the probability that a word in the transmission is the 𝑗th word
>
• • •
Missing some Tweet in this thread? You can try to
force a refresh
