Supongamos que calcular la generación de la función de cadenas binarias, teniendo a la
la mayoría de las $q$ consecutivos cabezas. Hay cuatro casos, según se trate de
la cadena comienza con los jefes o de las colas y termina con cara o cruz.
Tenemos
$$G_{HH}(z) =
z\frac{1-z^{p}}{1-z}
\sum_{k=0}^\infty
\left(\frac{z}{1-z}z\frac{1-z^{p}}{1-z}\right)^k.$$
Continuando llegamos
$$G_{HT}(z) = G_{HH}(z) \frac{z}{1-z}.$$
Además
$$G_{TT}(z) =
\frac{z}{1-z}
\sum_{k=0}^\infty
\left(z\frac{1-z^{p}}{1-z}\frac{z}{1-z}\right)^k.$$
Finalmente tenemos
$$G_{TH}(z) = G_{TT}(z) z\frac{1-z^{q}}{1-z}.$$
La suma plazo es
$$\frac{1}{1-z^2(1-z^q)/(1-z)^2}
= \frac{1-2z+z^2}{1-2z+z^2-z^2(1-z^q)}
= \frac{1-2z+z^2}{1-2z+z^{q+2}}.$$
El factor en esta es
$a$z\frac{1-z^{p}}{1-z} \left(1+\frac{z}{1-z}\right)
+ \frac{z}{1-z} \left(1+z\frac{1-z^{p}}{1-z}\right)$$
que es
$a$z\frac{1-z^{p}}{(1-z)^2}
+ \frac{z}{(1-z)^2} (1-z^{q+1})
= \frac{2z-z^{q+1} z^{q+2}}{(1-z)^2}.$$
La multiplicación se obtiene la generación de la función
$$G_q(z) = \frac{2z-z^{q+1}-z^{q+2}}{1-2z+z^{q+2}}.$$
De ello se desprende que la expectativa de los tiempos de $2^n$ está dado por
$$ [z^n]
\left(0\times G_0(z) + \sum_{q=1}^n q (G_q(z)-G_{q-1}(z)) \right).$$
La suma que se simplifica a
$$\sum_{q=1}^n q G_q(z)
- \sum_{q=0}^{n-1} (q+1) G_q(z)
= \sum_{q=0}^n q G_q(z)
- \sum_{q=0}^{n-1} (q+1) G_q(z)
\\ = n G_n(z)
- \sum_{q=0}^{n-1} G_q(z).$$
y, por tanto, la expectativa es
$$\frac{1}{2^n} [z^n]
\left( n G_n(z)
- \sum_{q=0}^{n-1} G_q(z) \right).$$
Esto le da a la secuencia
$$1/2,1,{\frac {11}{8}},{\frac {27}{16}},{\frac {31}{16}},{
\frac {69}{32}},{\frac {75}{32}},{\frac {643}{256}},{\frac {
1363}{512}},{\frac {1433}{512}},\ldots$$
Multiplicando por $2^n$ obtenemos
$$1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, \ldots$$
que es OEIS A119706
donde el cálculo anterior es confirmado.
El siguiente Arce código puede ser utilizado para explorar la generación de estos
funciones. El procedimiento v calcula la generación de la función de la
la máxima longitud de una cadena de $n$ bits por el total de la enumeración. El
procedimiento de w se calcula a partir de la generación de la función $G_q(z).$
v :=
proc(n)
opción de recordar;
local gf, k, d, mxrun, len;
gf := 0;
para k de 2^n 2^(n+1)-1 ¿
d := convert(k, base, 2);
mxrun := 0;
pos a n do
si d[pos] = 1 entonces
len := 1;
pos := pos+1;
mientras pos <= n hacer
si d[pos] = 1 entonces
len := len+1;
pos := pos+1;
otra cosa
break;
fi;
od;
si len>mxrun, a continuación,
mxrun := len;
fi;
fi;
od;
gf := gf + z^mxrun;
od;
gf;
end;
G := q -> (2*z-z^(q+1)-z^(q+2))/(1-2*z+z^(q+2));
w :=
proc(n)
opción de recordar;
local gf, mxrun;
gf := 1;
para mxrun a n do
gf := gf +
coeftayl(G(mxrun)-G(mxrun-1), z=0, n)*z^mxrun;
od;
gf;
end;
X := n -> coeftayl(n*G(n)-agregar(G(q), q=0..n-1), z=0, n)/2^n;
Aquí hay dos ejemplos.
> v(4);
4 3 2
z + 2 z + 5 z + 7 z + 1
> w(4);
4 3 2
z + 2 z + 5 z + 7 z + 1
Adenda. Respondiendo a la pregunta del OP, la máxima longitud de la distribución de $n=50$ es
> w(50);
50 49 48 47 46 45 44 43 42
z + 2 z + 5 z + 12 z + 28 z + 64 z + 144 z + 320 z + z 704
41 40 39 38 37 36
+ 1536 z + 3328 z + 7168 z + 15360 z + 32768 z + 69632 z
35 34 33 32 31
+ 147456 z + 311296 z + 655360 z + 1376256 z + 2883584 z
30 29 28 27 26
+ 6029312 z + 12582912 z + 26214400 z + 54525952 z + 113246208 z
25 24 23 22
+ 234881024 z + 486539259 z + 1006632909 z + 2080374408 z
21 20 19 18
+ 4294964912 z + 8858356224 z + 18253535488 z + 37580568576 z
17 16 15 14
+ 77307408384 z + 158903894017 z + 326369607799 z + 669786836360 z
13 12 11
+ 1373319005440 z + 2812533538048 z + 5749650288420 z
10 9 8
+ 11716183298140 z + 23723022576779 z + 47402584528885 z
7 6 5
+ 92066138963408 z + 168050756947888 z + 267156803852044 z
4 3 2
+ 310228979841119 z + 174887581402185 z + 19394019617001 z
+ 32951280098 z + 1
