# Counting the number of identical sub-sequences in a larger sequence.

Suppose I am working with sequences like this (monotonic but not strictly monotonic where each member of the alphabet repeats an identical number of times):

$$x = \{1,1,1,1,2,2,2,2,3,3,3,3\}$$, then $$|x| = N = 12$$ and the alphabet is $$\Sigma = \{1,2,3\}$$

Ultimately I am interested in the contiguous identical sub-sequences in $$x$$ and a corrupted version of $$x$$ let's call it $$x'$$, and let's say it has a value:

$$x' = \{1,1,2,2,2,3,3,3,3\}$$.

With this I am hoping to measure the goodness-of-fit between the corrupted version and the reference version $$x$$ by looking at the distribution over the identical sub-sequences, instead of raw counts of the alphabet, since the sub-sequences carry information on the monotonic nature of both sequences. That is my intution at least (looking at the distribution of the alphabet would simply yield a uniform distribution, and so would loose the monotonic repeating trend).

As an example, suppose we simply just count the identical $$n-$$tuples (let's call these $$a_n$$) when $$n=2$$, then we simply count all the identical tuples which:

1. are exactly of length 2 i.e. $$|a_2| = 2$$.
2. have all symbols in $$a_2$$ identical i.e. $$a[0]=a[1]$$.

There are three 2-tuples (i.e. three 2-tuples which look like so: $$[1,1]$$) in the first sub-sequence of ones, three 2-tuples in the second sub-sequence of twos and the same for the 2-tuples in the last sub-sequence of threes. In total there are 9 2-tuples in $$x$$.

Thus the probability of finding an identical 2-tuple in $$x$$ is:

$$P[a_2] = \frac{1}{9}$$

(not entirely sure this is right, I am primarily interested in counting the number of identical $$n-$$tuples).

Hence, now I would like to extend this so that I get a PMF for all the available tuples i.e. for $$n \in \{2,3,4\}$$ as $$4$$ is the maximum identical tuple we can consider given what $$x$$ looks like.

The histogram for this problem:

$$n=2 : \#9$$ $$n=3 : \#6$$ $$n=4 : \#3$$

Possible solution:

$$f$$ : identical sub-sequence count

$$f(n) \triangleq N - (n-1)|\Sigma|$$

Is it as simple as this? Though of course, if you construct the PMF from this, it does not sum to 1.

• Where does probability come into the picture? What is being randomly chosen? – Mike Earnest Jan 18 at 21:07
• I may have formulated this the wrong way; I am trying to find the distribution over all possible identical $n-$tuples in $x$ for $n\geq2$. – Astrid Jan 18 at 21:11
• Well, your formula for $f(n)$ is correct. If you want a probability distribution, you can set $p(n) = f(n)/(\sum_{i=2}^{N/|\Sigma|}f(i))$. The interpretation is that you put all of the possible identical tuples in a bag, pull one out, and observe its length. – Mike Earnest Jan 18 at 21:23
• Hmm... Yeah I don't think that I am formulating this very well, since that does not sound very intelligent. In your bag example, it does not make sense since a 2-tuple is much more common than a 4-tuple so should have more weight. But letting only the normalising constant take care of that does not seem like the right way to go about it. – Astrid Jan 18 at 21:24
• Maybe give some more context? Why do you need this PMF? – Mike Earnest Jan 18 at 21:25