9
$\begingroup$

The question concerns statistic properties of random words in a finite alphabet $A$.

By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.

Let $w$ be a word in the alphabet $A$. A nonempty word $u\in A^{<\omega}$ is called $w$-fixed if $w$ contains a unique subword, equal to $u$.

The dictionary of the word $w$ is defined as the set $D(w)$ of all minimal $w$-fixed subwords of $w$.

The fraction $$\rho(w)=\frac{|D(w)|}{|w|}$$will be called the randomness of the text $w$. Here $|D(w)|$ and $|w|$ is the cardinality of the set $D(w)$ and the length of the word $w$, respectively.

For example, for the word "Mathoverflow" its dictionary is the set $\{$'M', 'A', 'T', 'H', 'V', 'E', 'R', 'F', 'L', 'W'$\}$ and the randomness is equal to $$\frac{10}{12}\approx 0.833...$$

On the other hand, for the word "Stackexchange" the distionary is the set $\{$'S', 'T', 'K', 'X', 'H', 'N', 'G', 'AC'$\}$ and its randomness is equal to $$\frac{8}{13}\approx 0.615...$$

The computer calculations show that the randomness of the text about Mathoverflow in Wikipedia has length 2570 and randomness equal to $\frac{1087}{2570}=0.423...$

The text about Conan Doyl from Wikipedia has randomness $\frac{10120}{25710}\approx 0.394...$

and the text about Communism in Wikipedia has randomness $\frac{11952}{40230}\approx 0.297...$

Three randomly generated texts of the same length as the mentioned meaningfull texts from Wikipedia have randomness $\frac{2220}{2570}=0.864...$, $\frac{19866}{25710}=0.773...,$ and $\frac{33552}{40230}=0.834...$, respectively (if my program counts well).

So, we see that real meaningfull texts have smaller randomness (which decreases with growth of the length of the text) comparing to the randomness of random texts.

Problem 1. What is an expected value $\rho_n(|A|)$ of the randomness $\rho(w)$ of a random word of a fixed length $n$ in the alphabet $A$? What is the value of the limit $\rho_\infty(|A|)=\lim_{n\to\infty}\rho_n(|A|)$? (I hope that this limit does exist and depend on $|A|$).

Problem 2. Is the above randomness of texts related to other randomness measures like entropy?

Remark. Taking into account that any two minimal $w$-fixed words with the same starting letter coincide, we can conclude that $|D(w)|\le|w|$ and hence $\rho_n(|A|)\le 1$ for any alphabet $A$ and any $n$. Consequently, $\rho_\infty(|A|)\le 1$ (if this limit exists).

Improve this question
$\endgroup$
10
  • $\begingroup$ I think that there is a typo in the definition of $w$-fixed word $u$. You write that $u$ is $w$-fixed if (the alphabet) $A$ contains a unique subword equal to $u$. $\endgroup$
    – Liviu Nicolaescu
    Commented Oct 1, 2020 at 17:42
  • $\begingroup$ @LiviuNicolaescu You are right. The misprint is corrected. Thank you. $\endgroup$
    – Taras Banakh
    Commented Oct 1, 2020 at 17:48
  • 1
    $\begingroup$ Why is the denominator of the first large example 2570 and not 2579? Also, did you try randomly permuting the words of the text (keeping the words themselves intact)? $\endgroup$
    – Brendan McKay
    Commented Oct 2, 2020 at 7:10
  • $\begingroup$ How did you generate random words in your simulation? I mean what is the distribution on $A^n$ from which they are sampled? Also, which distribution do you mean when talking about random words in Problem 1? If it is uniform, then there is no surprise as it is known since Morse and Markov (let alone Shannon) that the empirical distributions of real texts are very far from uniform. $\endgroup$
    – R W
    Commented Oct 2, 2020 at 13:59
  • 1
    $\begingroup$ Not addressing the question as is, rather proposing a method of detection of meaningfulness of a text, that also addresses the objection by @BrendanMcKay. The keywords are LNRE (large number of rare events) and Zipf-Mandelbrot law. In its strongest form the principle is that in a meaningful and whole text, for small $n$ (like $n<10$) the proportion of words that appear exactly $n$ times is about $\frac1{n(n+1)}$ of words that appear (at least once). In a random text, this fails, as well as in a chunk of a whole text or a union of several diverse whole texts. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 3, 2020 at 4:42

0

Reset to default

You must log in to answer this question.