Simplifique $\sum\limits_{r=2}^{p+1} r(r-1)\frac{p!}{(p-r+1)!}\frac1{p^r}$

Question

Si un algoritmo muestrea un número entero aleatoriamente de $[1, p]$ en cada paso, y se detiene si el número generado se ha producido antes. ¿Cuál es el número esperado de pasos para que este algoritmo se detenga?

La expresión es fácil de averiguar, que es $$\sum_{r=2}^{p+1} \frac{r(r-1)\ p!}{(p-r+1)!\ p^r}$$ pero tengo problemas para simplificarlo. La suma se aproxima a $1.254\sqrt{p}$ .

Answer 1

Recapitulando la combinatoria vemos que para que el algoritmo se detenga en el paso $q+1$ debemos seleccionar ${p\choose q}$ diferentes valores y ordenarlos en uno de $q!$ formas para el prefijo y combinarlas con una repetición única para obtener una configuración admisible. Por lo tanto tenemos para el RV $X$ siendo el número de pasos que

$$P[X=q+1] = \frac{1}{p^{q+1}} {p\choose q} \times q! \times q.$$

Como control de sanidad debemos comprobar que para la suma de los probabilidades

$$\sum_{q=1}^p P[X=q+1] = 1.$$

Tenemos

$$q! = \sum_{k=1}^q {q\choose k} (-1)^{q-k} k^q.$$

y obtener por la suma

$$\sum_{q=1}^p \frac{1}{p^{q+1}} {p\choose q} q \sum_{k=1}^q {q\choose k} (-1)^{q-k} k^q \\ = \sum_{k=1}^p \sum_{q=k}^p \frac{1}{p^{q+1}} {p\choose q} q {q\choose k} (-1)^{q-k} k^q.$$

Tenga en cuenta que

$${p\choose q} {q\choose k} = \frac{p!}{(p-q)! k! (q-k)!} = {p\choose k} {p-k\choose q-k}$$

que da como resultado

$$\sum_{k=1}^p {p\choose k} \sum_{q=k}^p {p-k\choose q-k} \frac{1}{p^{q+1}} q (-1)^{q-k} k^q \\ = \sum_{k=1}^p {p\choose k} \frac{k^k}{p^{k+1}} \sum_{q=0}^{p-k} {p-k\choose q} \frac{1}{p^{q}} (q+k) (-1)^{q} k^q.$$

Hay dos piezas aquí, la primera es

$$\sum_{k=1}^p {p\choose k} \frac{k^{k+1}}{p^{k+1}} \sum_{q=0}^{p-k} {p-k\choose q} \frac{1}{p^{q}} (-1)^{q} k^q \\ = \sum_{k=1}^p {p\choose k} \frac{k^{k+1}}{p^{k+1}} \left(1-\frac{k}{p}\right)^{p-k} = \frac{1}{p^{p+1}} \sum_{k=1}^p {p\choose k} k^{k+1} (p-k)^{p-k}$$

y la segunda es

$$\sum_{k=1}^p {p\choose k} \frac{k^{k}}{p^{k+1}} \sum_{q=0}^{p-k} {p-k\choose q} q \frac{1}{p^{q}} (-1)^{q} k^q$$

Bajamos el índice superior a $k=p-1$ porque no hay contribución debida al factor ${0\choose 0} \times 0 = 1\times 0.$ Continuamos tenemos

$$\sum_{k=1}^{p-1} {p\choose k} \frac{k^k}{p^{k+1}} (p-k) \sum_{q=1}^{p-k} {p-k-1\choose q-1} \frac{1}{p^{q}} (-1)^{q} k^q \\ = - \sum_{k=1}^{p-1} {p\choose k} \frac{k^{k+1}}{p^{k+2}} (p-k) \sum_{q=1}^{p-k} {p-k-1\choose q-1} \frac{1}{p^{q-1}} (-1)^{q-1} k^{q-1} \\ = - \sum_{k=1}^{p-1} {p\choose k} \frac{k^{k+1}}{p^{k+2}} (p-k) \left(1-\frac{k}{p}\right)^{p-k-1}$$

que habría producido una división por cero si no hubiéramos bajado el índice. Así obtenemos

$$- \frac{1}{p^{p+1}} \sum_{k=1}^{p-1} {p\choose k} k^{k+1} (p-k)^{p-k} \\= \frac{1}{p^{p+1}} {p\choose p} p^{p+1} 0^0 - \frac{1}{p^{p+1}} \sum_{k=1}^{p} {p\choose k} k^{k+1} (p-k)^{p-k} \\ = 1 - \frac{1}{p^{p+1}} \sum_{k=1}^{p} {p\choose k} k^{k+1} (p-k)^{p-k}.$$

Sumando las dos contribuciones vemos que efectivamente suman uno como de una distribución de probabilidad.

Asintótica de la expectativa. La expectativa viene dada por

$$\sum_{q=1}^p \frac{1}{p^{q+1}} {p\choose q} \times q! \times q (q+1) = 2 \sum_{q=1}^p \frac{1}{p^{q+1}} {p\choose q} \times q! \times \frac{1}{2} q (q+1).$$

Tenemos

$$q! \times \frac{1}{2} q(q+1) = \sum_{k=1}^q {q\choose k} (-1)^{q-k} k^{q+1}.$$

y obtener por la suma

$$2\sum_{q=1}^p \frac{1}{p^{q+1}} {p\choose q} \sum_{k=1}^q {q\choose k} (-1)^{q-k} k^{q+1} \\ = 2 \sum_{k=1}^p \sum_{q=k}^p \frac{1}{p^{q+1}} {p\choose q} {q\choose k} (-1)^{q-k} k^{q+1}.$$

Refactorizar como antes para obtener

$$2 \sum_{k=1}^p {p\choose k} \sum_{q=k}^p \frac{1}{p^{q+1}} {p-k\choose q-k} (-1)^{q-k} k^{q+1} \\ = 2 \sum_{k=1}^p {p\choose k} \frac{k^{k+1}}{p^{k+1}} \sum_{q=0}^{p-k} \frac{1}{p^q} {p-k\choose q} (-1)^{q} k^q \\ = 2 \sum_{k=1}^p {p\choose k} \frac{k^{k+1}}{p^{k+1}} \left(1-\frac{k}{p}\right)^{p-k} \\ = \frac{2}{p^{p+1}} \sum_{k=1}^p {p\choose k} k^{k+1} (p-k)^{p-k}.$$

Obsérvese que cuando multiplicamos dos funciones generadoras exponenciales de las secuencias $\{a_n\}$ y $\{b_n\}$ obtenemos que

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

es decir, el producto de las dos funciones generadoras es la función generadora de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

En el presente caso tenemos claramente

$$A(z) = \sum_{n\ge 1} n^{n+1} \frac{z^n}{n!} \quad\text{and}\quad B(z) = 1 + \sum_{n\ge 1} n^{n} \frac{z^n}{n!}.$$

Obsérvese que en la convolución obtenemos $0^1 = 0$ así que $A(z)$ no debe tener un término constante mientras que $0^0 = 1$ así que $B(z)$ debe tener una, a saber uno.

Recuerda el función de árbol etiquetado $T(z)$ de la combinatoria que cuenta árboles etiquetados enraizados y tiene las especies etiquetadas

$$\mathcal{T} = \mathcal{Z}\mathfrak{P}(\mathcal{T})$$

y, por tanto, la ecuación funcional

$$T(z) = z \exp T(z).$$

Utilizando la fórmula de Cayley o la inversión de Lagrange tenemos que

$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$

De ello se deduce que

$$ A(z) = z \frac{d}{dz} z \frac{d}{dz} T(z) \quad\text{and}\quad B(z) = 1+z \frac{d}{dz} T(z).$$

Tenga en cuenta además que

$$\frac{d}{dz} T(z) = \exp T(z) + z \exp T(z) T'(z)$$

para que $$T'(z) = \frac{T(z)/z}{1-T(z)} \quad\text{and}\quad z T'(z) = \frac{T(z)}{1-T(z)}.$$

Diferencie una vez más para obtener

$$z (z T'(z))' = \frac{z T'(z)}{1-T(z)} + \frac{T(z)}{(1-T(z))^2} z T'(z) \\ = \frac{T(z)}{(1-T(z))^2} + \frac{T(z)^2}{(1-T(z))^3} = \frac{T(z)}{(1-T(z))^3}.$$

Esto significa que tenemos la siguiente forma cerrada para la consulta consultada:

$$\frac{2}{p^{p+1}} \times p! \times [z^p] A(z) B(z) = \frac{2}{p^{p+1}} \times p! \times [z^p] \frac{T(z)}{(1-T(z))^4}.$$

El polo dominante aquí está en $z=1/e$ (tenemos $T(1/e)=1$ desde $1=(1/e)\exp(1)$ ). La expansión singular de $T(z)$ acerca de $1/e$ es conocida y dada por

$$T(z) = 1 - \sqrt{2}\sqrt{1-ez} + \frac{2}{3} (1-ez) -\cdots$$

El resultado es

$$\frac{T(z)}{(1-T(z))^4} = T(z) \frac{1}{\sqrt{2}^4 \sqrt{1-ez}^4} \frac{1}{(1-\frac{\sqrt{2}}{3}\sqrt{1-ez}+\cdots)^4}$$

Por lo tanto, la asíntota se origina con

$$\frac{1}{4}\frac{1}{(1-ez)^2}.$$

Extrayendo los coeficientes y volviendo a sustituir, obtenemos

$$\frac{2}{p^{p+1}} \times p! \times \frac{1}{4} \exp(p) {p+1\choose 1} \sim \frac{1}{2} \frac{1}{p^p} \times p! \times \exp(p).$$

La mayor parte se anula cuando utilizamos la aproximación de Stirling, es decir

$$p! \sim \sqrt{2\pi p} \frac{p^p}{e^p}$$

y nos quedamos con

$$\bbox[5px,border:2px solid #00A000]{\frac{1}{2}\sqrt{2\pi p}.}$$

La constante conjeturada es $\frac{1}{2}\sqrt{2\pi} \approx 1.253314137.$

Adenda. Una forma más rápida de obtener la integral es ver el archivo como la convolución de

$$A(z) = \sum_{q\ge 0} q(q+1) \times q! \times \frac{z^q}{q!} = \frac{2z}{(1-z)^3} \quad\text{and}\quad B(z) = \sum_{q\ge 0} \frac{z^q}{q!} = \exp(z).$$

Esto da como resultado para la expectativa

$$\frac{1}{p} \times p! [z^p] \exp(z) \frac{2z/p}{(1-z/p)^3}.$$

Obtenemos la integral de coeficientes

$$\frac{1}{p^2} \times \frac{p!}{2\pi i} \int_{|z|=\gamma_1} \frac{1}{z^{p+1}} \exp(z) \frac{2z}{(1-z/p)^3} \; dz.$$

Ahora pon $z=pv$ para obtener

$$\frac{1}{p^2} \times \frac{p}{p^{p+1}} \frac{p!}{2\pi i} \int_{|v|=\gamma_2} \frac{1}{v^{p+1}} \exp(pv) \frac{2pv}{(1-v)^3} \; dv \\ = \frac{1}{p^{p+1}} \frac{p!}{2\pi i} \int_{|v|=\gamma_2} \frac{1}{v^{p}} \exp(pv) \frac{2}{(1-v)^3} \; dv.$$

Poner a continuación $v/\exp(v) = w$ para que $v=T(w)$ y $dv=T'(w) \; dw$ para obtener

$$\frac{1}{p^{p+1}} \frac{p!}{2\pi i} \int_{|w|=\gamma_3} \frac{1}{w^{p}} \frac{2}{(1-T(w))^3} T'(w) \; dw \\ = \frac{1}{p^{p+1}} \frac{p!}{2\pi i} \int_{|w|=\gamma_3} \frac{1}{w^{p+1}} \frac{2T(w)}{(1-T(w))^4} \; dw.$$

Es lo mismo que obtuvimos antes.

Addendum, II. La prueba de que

$$q! \times \frac{1}{2} q(q+1) = \sum_{k=1}^q {q\choose k} (-1)^{q-k} k^{q+1}.$$

utiliza la integral

$$k^{q+1} = \frac{(q+1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+2}} \exp(kz) \; dz$$

Obtenemos para la suma

$$\frac{(q+1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+2}} \sum_{k=1}^q {q\choose k} (-1)^{q-k} \exp(kz) \; dz \\ = \frac{(q+1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+2}} \left(-(-1)^q + (\exp(z)-1)^q\right) \; dz.$$

Así pues, tenemos

$$(q+1)! [z^{q+1}] \left(-(-1)^q + (\exp(z)-1)^q\right) = (q+1)! [z^{q+1}] (\exp(z)-1)^q \\ = (q+1)! {q\choose 1} \frac{1}{2}$$

lo que prueba la afirmación.

Addendum, III. La tarea de verificar que las probabilidades suman uno también puede simplificarse utilizando una convolución de

$$A(z) = \sum_{q\ge 0} q \times q! \times \frac{z^q}{q!} = \frac{z}{(1-z)^2} \quad\text{and}\quad B(z) = \sum_{q\ge 0} \frac{z^q}{q!} = \exp(z).$$

Adaptamos el cálculo a partir de la expectativa y repetimos para obtener el integral

$$\frac{1}{p^{p+1}} \frac{p!}{2\pi i} \int_{|w|=\gamma_3} \frac{1}{w^{p+1}} \frac{T(w)}{(1-T(w))^3} \; dw.$$

Recordemos que antes calculamos que

$$\sum_{n\ge 1} n^{n+1} \frac{z^n}{n!} = z(zT'(z))' = \frac{T(z)}{(1-T(z))^3}$$ de modo que esta integral es

$$\frac{1}{p^{p+1}} \times p! \times [w^p] \sum_{n\ge 1} n^{n+1} \frac{w^n}{n!} = \frac{1}{p^{p+1}} p^{p+1} = 1$$

y las probabilidades suman uno como se afirma.

Consulte Estadísticas de mapas aleatorios de Flajolet y Odlyzko para lecturas de fondo.