Probabilities for "What number is that? — asks grandpa"

Question

_{Inspired from Multilanguage generalization of "What number is that? Asks Grandpa" and What number is that ? Asks Grandpa}

---

In this puzzle we will use the English alphabet of 26 letters. We create a language that uses it and we call it $LANG$. Previously in What number is that ? Asks Grandpa the issue was:

What is the smallest positive integer $N$ for which:
If you take its WORD anagram and subtract the number $N$ itself, you get some positive integer quantity.
Anagram of the number - Number > 0"?

• Hence the smallest legal number in English would be 67 — SIXTY-SEVEN— since 76 — SEVENTY-SIX — is also a legal number, and 76 - 67 is positive.

For $LANG$ things are quite different as each number is written this way:

1. $0$ can not be written in $LANG$.
2. $i>0$ written in $LANG$ is at least of length $i$.
3. $i>0$ written in $LANG$ is of length $i+k$ with $0 \le k\le i$ with probablity $\dfrac{1}{i+1}$.
4. All letters of any $i>0$ written in $LANG$ are equally randomly drawn from the English alphabet. Each letter having a probability of $\dfrac{1}{26}$ to be drawn.

Example $i=3$

2. $i$ will be composed by $3$ letters at least.
3. $i$ will be composed by $3$ letters with probability $\dfrac1{i+3}=\dfrac14$. $i$ could also be composed of $4$, $5$, or $6$ letters with the same probability of $0.25$.
4. If after a first draw, $i$ was to be of length $4$, $i$ could be: $aaaa$ or $love$ both with probability $\dfrac{1}{26^4}\simeq 0.0000022$.

Puzzle

You have the choice to select $N > 0$ such that you will have a draw on $I=\{1,\dots ,N\}$. There is a success if and only if there is an anagram on at least one $(i,i')\in I^2$ with $i$ and $i'$ representing two different $LANG$ numbers.

What smallest $N$ would you select to ensure that your probability of success is greater than $0.26$?

Answer 1

I would like to present an argument that shows that

There is no $N$ which yields a probability of $0.26$.

In fact

The probability won't go above $0.0006$ for any $N$.

Proof

For two numbers $m > n$, let's first compute the probability, $p_l(m,n)$, that the word for $m$ is the same length as the word for $n$.
Obviously if $m > 2n$, $p_l(m,n) = 0$, otherwise $p_l(m,n) = \frac{2n+1-m}{(m+1)(n+1)} $, (which comes from looking at the region of overlap).
Now suppose the words for $m$ and $n$ are of the same length. Then what is the probability, $p_a(m,n)$, that the words are anagrams of each other? Well, I have found this to be a tricky computation but we can put an upper bound on it.
In particular, let the length of the words be $N$ and suppose $N$ is large. Then the two words are anagrams of each other if they contain the same number of as, bs, cs, etc. The randomly generated word which would produce the most such anagrams is one which has an equal distribution across the letters - same number of as, bs, cs, etc - or as close as possible. The number of anagrams of such a word is roughly approximated by $\frac{N!}{\left(\left( \frac{N}{26} \right)!\right)^{26}}$ (note that we can extend the definition of factorial using the gamma function) which is always less than $26^{26}$.
The total number of possibly generated words of length $N$ is $26^N$. Hence, putting these together, for large enough $N$, if the words for $m$ and $n$ are of length $N$, we have $$p_a(m,n) < 26^{26-N}$$ In fact, this is also a bound for small $N$ (albeit a very loose one).
We can combine the two formulae above to find that the probability, $p_A(m,n)$ that the words for $2n \geq m > n$ are anagrams of each other is bounded as follows $$ p_A(m,n) < \frac{26^{26-m} + 26^{25-m} + 26^{24-m}+\ldots+26^{26-2n}}{(m+1)(n+1)} = \frac{26^{27-m} - 26^{26-2n}}{25(m+1)(n+1)}$$ In particular, when we introduce the word for a new number $m$, the probability that it is an anagram of a previous word, $p_p(m)$ is bounded above as follows $$ p_p(m) < \displaystyle \sum_{k=1}^{m/2} \frac{26^{27-m} - 26^{26-2(m-k)}}{25(m+1)(m-k+1)} < \frac{m 26^{27-m}}{25(m+1)(m+2)} < \frac{26^{27-m}}{25(m+2)}$$ Using this, we see that the probability, $P(m)$ for any of the words for numbers greater than or equal to $m$ being an anagram of a word for a smaller number is also bounded, that is $$ P(m) < \displaystyle \sum_{k=m}^{\infty} \frac{26^{27-k}}{25(k+2)} < \frac{26^{28-m}}{625(m+2)}$$ We can see that for even reasonably small values, this probability is very small. For example $P(33) \approx 1.34 \times 10^{-11}$ so we'll have to be pretty close to exceeding $0.26$ by the time we get to the word for $33$.
A quick computation shows that the existence of anagrams in the words for the first $32$ numbers is around $0.00056$ so we won't get a probability very much higher than this for any $N$.