Let $L = \{a_1,a_2,...a_m\}$ be a set of characters. We have a large population of strings, $S$ ,with strings of size $n$, consisting of the characters in $L$ i.e $S \subseteq L^{n} $. Now given a string in $S$, I can map it to a vector $V_{s} = [|a_1|,...,|a_m|]$ which is the vector that counts occurences of each character in a given string $s$. For example, if $L = \{a_1,a_2,a_3\}$ (m=3) and $n= 5$, then one such $s$ could be $a_1a_1a_2a_3a_1$ and $V_s$ would be $[3,1,1]$.

My goal is that given an arbitrary population of $S$ (strings of a fixed length from a given language $L$), I would like to estimate the probability distribution over the $V_s$ by sampling some of the strings from $S$.

What is the best and most efficient way I can do this? Specially when $n\gg m$, can I sample $s\in S$only partially, i.e. taking only a part of a string?

PS: notice that if $S $= $L^n$ then this can be easily done using multinomial coefficients.


1 Answer 1


I'm assuming you have free access to the population of strings and so your only concerns are computational. The only real speed up you can get is by trading memory for speed, which might be relevant when your population is large.

When the strings are long it takes you $O(n) $ to convert from the string to the number you are interested in.

You can, before starting, construct a binary tree where all possible strings are ordered lexicographically. Each leaf of the tree would contain the $V_s$ associated with a string. Traversing the tree is $O(ln (n)) $ which gives you a speed up. Then, it remains only to count how many times you reach each leaf after sampling many many times.

EDIT: Notice, that if you were interested in how to model the density there is no way to do so theoretically without having some further restriction on the distribution of letters. One such restriction might be to assume letters to be independently (though not necesserily identically) distributed which would greatly simplify the job, as in that case you can recover the $V_s$ density by estimating the probability of single letters.


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.