2
$\begingroup$

I am interested on the asymptotic behaviour ($m \rightarrow \infty$) of the number of $q$-ary strings of length $m$, which do not contain $k$ consecutive zeros.

The link Number of q-ary strings of length m which do not contain k consecutive zeros gives some derivations for that number.

In particular, the ordinary generating function of this number is $$ F(z) = \frac{1-z^k}{1-qz+(q-1)z^{k+1}} $$ where $q$ is the size of the alphabet $\{ 0,1,...,q-1 \}$.

Now I hope, there is some simpler expression $g(q,m,k)$ for the asymptotic behaviour of this number, i.e. $f_m \sim g(q,m,k)$ for $m \rightarrow \infty$. We state $k<m$ and assume that $k$ is very small relatively to $m$.

Can someone help me with my problem?

$\endgroup$
4
$\begingroup$

Fixing $q$ and $k$ we ask about the asymptotics of $[z^m] F(z)$ where

$$F(z) = \frac{1-z^k}{1-qz+(q-1)z^{k+1}}.$$

We will suppose that $m\ge k$ since the answer is $q^m$ otherwise. First verify that the poles $\rho$ are all simple. We get with $\rho$ a root of the denominator

$$\lim_{z\to\rho} \frac{z-\rho}{1-qz+(q-1)z^{k+1}} = \lim_{z\to\rho} \frac{1}{-q + (q-1)(k+1)z^{k}}.$$

Now we have

$$-q + (q-1)(k+1)\rho^{k} = -q + (q-1)(k+1)\rho^{k+1}/\rho \\ = -q + (k+1)(q\rho-1)/\rho.$$

If this were zero we would get

$$\rho = \frac{k+1}{kq}.$$

which is rational. Applying the rational root theorem to the denominator of $F(z)$ we must have

$$\frac{k+1}{kq} = \frac{1}{r}$$

where $r|(q-1).$ This requires $q=p(k+1)$ where $kp|(q-1).$ There are two cases. The first is $kp=q-1$ which implies $q=q-1+p$ i.e. $p=1.$ We get $\rho = 1/k$ however for $1-(k+1)/k + k / k^{k+1} = 0,$ we would need $1/k^k = 1/k$ so no contribution from this case (here we have assumed that $k\ge 2$ since the answer is $(q-1)^m$ trivially otherwise). Second case is that $kp$ is a proper divisor of $q-1$ which gives the bound $q\le (q-1)/2 + (q-1)/4$, a contradiction. Hence all poles are simple.

Working with

$$G(z) = \frac{1}{1-qz+(q-1)z^{k+1}}.$$

we have under these conditions

$$G(z) = \sum_\rho \frac{1}{z-\rho} \mathrm{Res}_{z=\rho} G(z) = - \sum_\rho \frac{1}{\rho} \frac{1}{1-z/\rho} \mathrm{Res}_{z=\rho} G(z).$$

This last expression tells us that we need the pole closest to the origin for the asymptotics. Observe that with $|z|\lt 1$ the term $1-qz+(q-1)z^{k+1}$ is dominated by $1-qz$ and hence there must be a pole in the vicinity of $z=1/q$, which it will require numerics to approximate (e.g. start Newton's method at $1/q$) and which we will call $\beta.$ The complex poles come in pairs so if we can show that it is real and that there are no others with $|z|<1/q$ we have that the contribution from $\beta$ yields the asymptotics. At this time we will show that there is one zero from the denominator inside $|z|=(1/q)\times q/(q-1) = 1/(q-1)$ by Rouche's Theorem, taking $f(z) = 1-qz+(q-1)z^{k+1}$ and $g(z) = - qz$ where

$$|f(z)-g(z)| = |1+(q-1)z^{k+1}| \le 1 + \frac{1}{(q-1)^k} \quad\text{and}\quad |g(z)| = \frac{q}{q-1} = 1 + \frac{1}{q-1}.$$

The conditions for the theorem hold (i.e. $|f(z)-g(z)| \lt |g(z)|$ on $|z|=1/(q-1)$) when $k\ge 2$ which we assumed so $f(z)$ has the same number of zeros inside the contour as $g(z)$ and $g(z)$ has just one root there, so $f(z)$ does as well and this is our pole $\beta.$ As there is just one it must be real.

To conclude here it remains to extract coefficients which yields

$$-\frac{1}{\beta} \left(\frac{1}{\beta^m}-\frac{1}{\beta^{m-k}}\right) \times \frac{1}{-q+(k+1)(q\beta-1)/\beta}.$$

We factorize to obtain the constant and find

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{(k+1)(q\beta-1)-q\beta} \left(\beta^k-1\right) \times \frac{1}{\beta^{m}}.}$$

This formula was verified numerically where $\beta$ was computed and the evidence indicates rapid convergence with $m.$

Addendum. To help OP we also include the closed form which requires

$$[z^m] \frac{1}{1-qz+(q-1)z^{k+1}} = [z^m] \sum_{p\ge 0} z^p (q-(q-1) z^k)^p \\ = \sum_{p=0}^m [z^{m-p}] (q-(q-1) z^k)^p = \sum_{p=0}^m [z^p] (q-(q-1) z^k)^{m-p} \\ = \sum_{p=0}^{\lfloor m/k\rfloor} [z^{kp}] (q-(q-1) z^k)^{m-kp}.$$

Here we must have $m-kp\ge p$ and we find

$$[z^m] G(z) = g_m = \sum_{p=0}^{\lfloor m/(k+1)\rfloor} {m-kp\choose p} (1-q)^p q^{m-(k+1)p}$$

and the closed form is given by $f_m = [z^m] F(z) = g_m-g_{m-k}.$

$\endgroup$
  • $\begingroup$ Thank You for your answer. I am trying to follow it. Does it mean, that the coefficients behaves proportional to $\frac{1}{\beta^m}$ where $\beta$ is the dominant pole of the o.g.f? My intuitive thought was, that the coefficients would grow exponential with the length $m$. In the lim-equation, are you just ignoring the nominator of the o.g.f., since it doesn't have an impact of the asymptotics? How do you come from the left-hand side to the right-hand side of the lim-equation? $\endgroup$ – N. Younger Aug 8 '17 at 7:40
  • $\begingroup$ For the limit see this at Wikipedia. The coefficients are indeed exponential in $1/\beta^m$ times a coefficient in front. $\endgroup$ – Marko Riedel Aug 8 '17 at 12:17

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.