I'm studying the paper Database-friendly random projections: Johnson-Lindenstrauss with binary coins by D. Achlioptas and can't manage to work out the total number of permutations with repetitions in equation (2).

To put it in context, say you want to generate 12-element long sequences composed of $\{-1, 0, +1\}$ where $\{0\}$ occurs with $p=\frac{2}{3}$ and each of $\{-1, +1\}$ with $p=\frac{1}{6}$.

For example, the following are well-formed sequences, as each is made up of 8 $\{0\}$-elements, 2 $\{-1\}$-elements and 2 $\{+1\}$-elements:

$$ 0~0~0~0~0~0~0~0 -1 -1 +1 +1 $$ $$ 0~0~0~0~0~0~0~0 -1 +1 -1 +1 $$ $$ -1 -1 +1 +1~0~0~0~0~0~0~0~0 $$

How do I calculate the total number of such sequences?

If the n-elements had the same probability, their total number of r-permutations with repetitions would be $n^r = 3^{12}$, but cannot find any clear explanation of the case where they have different probabilities.

  • $\begingroup$ There are $3^{12}$ total number of possible sequences. Some of them have $\left(\frac{1}{6}\right)^{12}$ probability of occurring but that doesn't affect how many sequences there are. $\endgroup$ – John Habert Feb 20 '14 at 15:42

Here is a generalization of your question, if I understood it correctly. An alphabet $\sum$, and the probability of each symbol $a$ occurring in a word of length $n$, find out the number of such words.

Let us proceed by first calculating how many times each symbol must occur in the word. Each symbol must occur $Pr(a) \times n$ times. Then, the problem becomes the number of permutations of $n$ elements comprising $m$ classes, $n_i$ elements of class $i$ such that $\sum_{i} n_i = n$.

Hence, the number of words = $\frac{n!}{\prod_{a \in \sum} (Pr(a) \times n)!}$

So, for the given example, it is - $\frac{12!}{8! \times 4! \times 4!}$

  • $\begingroup$ Thanks for your answer! You understood precisely what I meant... the result of your solution is much smaller than $n^r$ as I expected. $\endgroup$ – emiguevara Feb 25 '14 at 10:46

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.