Limit of quotients of polynomials at fixed value

Question

Let $0<t<1$ be a parameter. Let $n\in\mathbb{Z}$, $n>0$. For $i\in\{0,1,\dots,2^n-1\}$, we always consider $i$ as having $n$ binary digits (positions $1$ to $n$), putting $0$s if necessary. Let $f(i)$ be the number of times the $j+1$-th binary digit of $i$ is different from the $j$-th digit, $1\leq j\leq n-1$. Let $g(i)$ be the number of $1$s in the binary expansion of $i$. We consider $$ p(t,n)=\frac{\sum_{\substack{i=0\\i\equiv 1 \bmod 2}}^{2^n-1}(1/2)(1-t)^{n+f(i)-g(i)}(t)^{n-1-f(i)+g(i)}}{\sum_{i=0}^{2^n-1}(1/2)(1-t)^{n+f(i)-g(i)}(t)^{n-1-f(i)+g(i)}}. $$ Numerical evidence shows that $p(3/4,n) \rightarrow \sqrt{3}/2$ as $n\rightarrow \infty$. May it be possible to inquire on how to prove it? Thanks very much.

(Perhaps this is similar to various limits involving binomial coefficients such as in the question "A limit involving binomial coefficients?" , but I don't know much about this subject. Thanks!)

Answer 1

First, cancelling common factors we get $$p(t,n) = \frac{ \sum_{i=0\atop i\equiv 1\pmod{2}}^{2^n-1} \left(\frac{t}{1-t}\right)^{g(i)-f(i)} }{ \sum_{i=0}^{2^n-1} \left(\frac{t}{1-t}\right)^{g(i)-f(i)} }$$

Clearly, $f(i)$ is the number of 2-mers "01" and "10", while $g(i)$ is the number of 2-mers $10$ and $11$ in the binary representation of $i$. Then $g(i)-f(i)$ is the number of $11$ minus the number of $01$.

Let $w = \frac{t}{1-t}$. Consider the de Bruijn graph $G$ on the nodes $\{ 00, 01, 10, 11\}$, where all the arcs are weighted as follows:

• arcs incoming to $11$ have weight $w$;
• arcs incoming to $01$ have weight $w^{-1}$;
• the other arcs have weight 1.

That is, the adjacency matrix of $G$ is $$A = \begin{bmatrix} 1 & w^{-1} & 0 & 0 \\ 0 & 0 & 1 & w \\ 1 & w^{-1} & 0 & 0 \\ 0 & 0 & 1 & w \end{bmatrix}. $$

We interpret each $n$-bit integer (prepended and appended by "0") as a walk of length $n$ in $G$ starting at nodes $00$ or $01$ and ending at nodes $00$ or $10$.

Then the numerator of $p(t,n)$ is the total weight of all walks of length $n$ from node $01$ to node $00$ or $10$, while the denominator of $p(t,n)$ is the total weight of all walks of length $n$ from node $00$ or $01$ to node $00$ or $10$. That is, $$p(t,n) = \frac{[0,1,0,0]\cdot A^n\cdot [1,0,1,0]^T}{[1,1,0,0]\cdot A^n\cdot [1,0,1,0]^T}.$$

From here, one can get an explicit formula for $p(t,n)$, but for the purpose of the question it's enough to consider $t=\frac{3}{4}$ and $w=3$. It follows that $$p(\frac{3}{4},n) = \frac{\sqrt{3}}{2}\cdot \left(1+O\left(\left(\frac{3-\sqrt{3}}{3+\sqrt{3}}\right)^n\right)\right).$$