# Estimate asymptotic behaviour by looking on ordinary generating function

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?

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}.$

• 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? – N. Younger Aug 8 '17 at 7:40
• For the limit see this at Wikipedia. The coefficients are indeed exponential in $1/\beta^m$ times a coefficient in front. – Marko Riedel Aug 8 '17 at 12:17