4
$\begingroup$

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the complement. I am interested in values like, say, $N_{21,8,4}$.

Can we compute $N_{n,k,b}$ efficiently? Is there a reasonable formula for it?

It is analogous to a person whose circle of closest friends is changing at a reasonable rate; there is never too long between times when someone enters or leaves the circle.


Example 1. $R_{5,3,2}$ is the number of binary strings of length 5 that contain some unary run of length 3: these are of the form 000XY, 00111, 01000, 0111X (if start with a 0) so $$ R_{5,3,2} = 16. $$ Example 2. $R_{5,4,3}$: the complement (no run of length 4 from any 2-ary subalphabet) can be analyzed by looking at the middle 3 letters:

  1. There are $3!\cdot 3^2=54$ patterns of the form $AXYZB$ where $\{X,Y,Z\}=\{0,1,2\}$.

  2. If $XYZ$ is from a 2-ary alphabet (but not unary) then $A$ and $B$ have to be the missing letter in $XYZ$, so there are $\binom{3}{2} (2^3-2) = 18$ of this form.

Total $N_{5,4,3}=72$ and $R_{5,4,3}=3^5-72=171$.

$\endgroup$
  • $\begingroup$ When k=b I get k! for the complement. It might start a nice recurrence for the complement. $\endgroup$ – The Masked Avenger May 16 '15 at 0:53
  • $\begingroup$ I'm not sure why you are using $R_{n,k,b}$ for the sequences with a run rather than the sequences without a run. For fixed $k, b$, as $n\to\infty,~R_{n,k,b} \sim b^n$. So, are you interested in other asymptotics where $k$ and $b$ grow with $n$, and if so, which growth rates do you think are interesting? Otherwise it seems more interesting to look at $N_{n,k,b} = b^n - R_{n,k,b}$, where you might expect a nice formula for $k$ slightly greater than $b$, but where the growth rate is unclear. $\endgroup$ – Douglas Zare May 16 '15 at 11:07
  • $\begingroup$ Your example 2 is wrong. $2^5-2\cdot 17 = -2$. I guess you meant something like $3^5 - 3*7 - 3$ according to those patterns but some of the patterns are wrong, such as $0112X$ which allows $01121$ and $01122$. $\endgroup$ – Douglas Zare May 16 '15 at 11:13
  • 1
    $\begingroup$ There is some recurrence that has $k$ choose $b$ terms for $N_{n,k,b}$ with fixed $b,k$ and varying $n$. You choose the distance from the most recent appearance of each of the $b$ letters to the end of the string, and consider what happens when you add one more letter. So there is some kind of asymptotic... $\endgroup$ – Will Sawin May 16 '15 at 16:40
3
$\begingroup$

Here is a dynamic programming approach to compute $N_{n,k,b}$ in time $O_{k,b}(n)$. You can extract from it a recurrence for $N_{n,k,b}$ in the $n$ variable.

Given a suitable sequence, for each of the $b$ letters, we can count the number of steps from the last occurrence of each letter to the end, which is a number $1$ to $k$. So we get a list of $b$ numbers $1$ to $k$. These numbers are clearly distinct, and $1$ is included, so there are $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ possibilities.

Store at each step the number of length $n$ sequence satisfying your condition for each of the $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ possible ending types. Then we can compute from this the number of length $n+1$ sequences satisfying your conditon for each of the possible ending types.

The way to do this is pretty simple. Given a list of numbers, we know that adding one letter at the end increases all the numbers by $1$, except the number corresponding to the letter we add, which goes to $1$. So there are usually $b$ possibilities for the next type, which are given by picking one of the numbers and setting it to $1$ and adding $1$ to the rest. The only exception is if one of the numbers is $k$, in which case we have to set that one to $1$ and increment the rest.

This tells us how to update the information at each step, and finally how to compute $N_{n,k,b}$ by adding up over all the different ending types.

It also gives us a recurrence relation for $N_{n,k,b}$ in the variable $n$. The updating step corresponds to multiplying by a certain $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}\times \begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ matrix. By Cayley-Hamilton, the sequence we generate satisfies the recurrence relation defined by the characteristic polynomial of the matrix. In particular, the growth rate in $n$ is exponential by the largest eigenvalue of the matrix.

In the case $N_{21,8,4}$, we have $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}=\begin{pmatrix} 7 \\ 3 \end{pmatrix}=35$, which is not too big, so the algorithm should not take too long to run and give the exact answer, nor should it be too difficult to compute the matrix and find the growth rate.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So if we fix $k=8$ and $b=4$ and let $N_{n,S}$ denote the number of sequences for ending type $S$, then $N_{n,\{7,5,4,1\}}$ contributes to $N_{n+1,\{8,6,5,1\}}$, $N_{n+1,\{8,1,5,2\}}$, $N_{n+1,\{8,6,1,2\}}$, and $N_{n+1,\{1,6,5,2\}}$. Whereas $N_{n,\{8,7,6,1\}}$ only contributes to $N_{n+1,\{1,8,7,2\}}$. Very nice -- although there is quite a bit to store. $\endgroup$ – Bjørn Kjos-Hanssen May 20 '15 at 20:24
  • $\begingroup$ I should add that, of course, a randomized algorithm is trivial to implement, and that may be all that is needed depending on the purpose. $\endgroup$ – Bjørn Kjos-Hanssen May 28 '15 at 20:37

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.