Let us consider the following: suppose I have a word of length $n$ from an ordered alphabet on $n$ letters $\{1, ..., n\}$, i.e., an element $(w_i)$ of $\{n\}^{\{n\}}$.

What is the probability of choosing the first letter $w(1)$ from all possible words, considering that I would choose $w(j)$ over $w(i)$ with probability $1$ if $w(i)>w(j)$, and if I have for some subset $I\subset{n}$ (EDIT: and some $a\in \{n\}$ such that $w^{-1}(a)=I$,) I am equally likely to choose any element from $I$?

For example, if I wanted to choose a letter from all two-letter words in two-letter alphabet, i.e., $\{1,2\}^{\{1,2\}}=\{(11), (12), (21), (22)\}$, then I will choose the first letter with probability $$\frac{1}{2}=\frac{1}{4}\cdot\left(\frac{1}{2}\cdot{1\choose 1}((2-1)^{0}+(2-2)^0)+1\cdot {1 \choose 0}((2-1)^1+(2-2)^1) \right),$$ where I put $(2-2)^0=1$.

In general, I seem to arrive to the formula $$n^{n-1}=\sum_{n>m\ge0,\ n\ge k \ge 1} \frac{1}{n-m}{n-1 \choose m} (n-k)^m.$$ It seems to work for numbers up to $4$.

This seems a bit silly, because obviously any word is equally likely to start with any letter. But I do not quite see how the symmetry helps in the case of this bizarre distribution.

  • $\begingroup$ What's $a$ in $w^{-1}(a)$? $\endgroup$ – joriki Dec 11 '19 at 11:57
  • $\begingroup$ @joriki I consider $w: \{n\} \to \{n\}, i\mapsto w(i)$ $\endgroup$ – ATR Dec 11 '19 at 13:15
  • $\begingroup$ Indeed. And there's no $a$ in that. $\endgroup$ – joriki Dec 11 '19 at 13:17
  • $\begingroup$ @joriki Sorry, I used in a sense of a fixed element from $\{n\}$, see the edit above. $\endgroup$ – ATR Dec 11 '19 at 13:25
  • $\begingroup$ I must confess I have a hard time understanding this problem. $\endgroup$ – Fimpellizieri Dec 11 '19 at 13:29

As was clarified in comments the correct statement of the problem is the following:

Given a random word a letter with the lowest value is chosen (if there are several such letters one of them is chosen randomly). What is the probability that the chosen letter is the first letter of the word?

In fact the probability in question does not depend on the size of the alphabet $n$ but only on the length of the word $N$. Namely: $$ p(n,N)=\frac1N. $$ As already observed in a comment it follows immediately from the symmetry of the problem as any position for the letter with the lowest value in the word is equiprobable, i.e. equal to $\frac1N$.

This can be shown also algebraically. Indeed: $$ p(n,N)=\frac1{n^N}\sum_{k=1}^n\sum_{K=1}^N\frac1K\binom{N-1}{K-1}(n-k)^{N-K}\tag1, $$ where $k$ is the lowest letter value and $K$ is the number of letters with this value in the word. The convention $0^0=1$ is used. Here it is assumed that the first letter in the word has the value $k$ so that the factors $\binom{N-1}{K-1}$ and $(n-k)^{N-K}$ count the number of ways a) to arrange the rest $K-1$ letters with the value $k$ over the rest $N-1$ positions and b) to fill the rest $N-K$ positions with letters having a higher value (from $k+1$ to $n$) , respectively. The factor $\frac1K$ stays for the probability to choose the first letter.

We claim: $$p(n,N)=\frac1N, $$ which is due to (1) equivalent to $$\sum_{k=1}^n\sum_{K=1}^N\binom{N}{K}(n-k)^{N-K}={n^N}.\tag2 $$

The validity of the expression (2) is obvious since both sides of the equation count all possible arrangements of the letters in the word of length $N$. (Here the letters with the lowest value are allowed to be arranged in the word quite arbitrarily).

The same result can be obtained by induction. Obviously the claim (2) is valid for $n=1$. Let us show that if it is valid for some $n$ the same is true for $n+1$: $$\begin{align} &\sum_{k=1}^{n+1}\sum_{K=1}^N\binom{N}{K}(n+1-k)^{N-K}\\ =&\sum_{K=1}^N\binom{N}{K}n^{N-K} +\sum_{k=2}^{n+1}\sum_{K=1}^N\binom{N}{K}(n+1-k)^{N-K}\\ =&\sum_{K=1}^N\binom{N}{K}n^{N-K} +\sum_{k=1}^{n}\sum_{K=1}^N\binom{N}{K}(n-k)^{N-K}\\ \stackrel{I.H.}=&\sum_{K=1}^N\binom{N}{K}n^{N-K}+n^N\\ =&(n+1)^N. \end{align} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.