Pascal se emborracha y construye su triángulo. La mitad del tiempo escribe $0$ en lugar de sumar los dos números de arriba. ¿Cuál es el promedio de los números?

Question

Un día Pascal toma un poco más de lo debido, luego se sienta a construir su famoso triángulo. Escribe $1$'s bajando por los lados, sin problema. Luego comienza la ardua tarea de completar el triángulo. Se supone que cada número es la suma de los dos números arriba de él (y más cercanos a él). Pero está borracho, así que la mitad del tiempo (probabilidad $1/2$) simplemente escribe $0$, y la mitad del tiempo suma correctamente los dos números arriba de él.

¿Cuál es la expectativa del promedio (media aritmética) de todos los números, para un triángulo de tamaño infinito?

Simulaciones

Usé Excel para construir $5\times 10^6$ tales triángulos, con $20$ filas cada uno.

{ Promedio de los números en la fila $5$ } = $0.9998$
{ Promedio de los números en la fila $10$ } = $0.9963$
{ Promedio de los números en la fila $15$ } = $0.9940$
{ Promedio de los números en la fila $20$ } = $0.9913$

No estoy seguro de qué sugieren estos datos.

Probabilidad $1/2$ parece ser el valor crítico

También realicé algunas simulaciones donde la probabilidad de que Pascal escriba $0$ es algo distinto de $\frac12$. Parece que, si la probabilidad es mayor que $\frac12$ entonces el promedio de los números tiende a $0$, y si la probabilidad es menor que $\frac12$ entonces el promedio de los números tiende a infinito. La probabilidad $\frac12$ parece ser el valor crítico.

Answer 1

Sea $p$ la probabilidad de que Pascal escriba un cero en lugar de la suma en una de las entradas interiores del triángulo.

Sea la fila superior (con solo una entrada individual) la fila $0$. Si Pascal no escribe ceros, la suma de las entradas en la fila $n$ es $2^n$.

Supongamos que $0 < p < 1$ y supongamos que Pascal escribe un triángulo. Sea $X_n$ la suma de la fila $n$ en el triángulo y $X_{n+1}$ la suma de la fila $n+1$.

Si no hubiera ceros en la fila $n+1$, entonces tendríamos $X_{n+1} = 2X_n$. Pero la versión sin ceros de la fila $n+1$ contiene entradas con valor total $2X_n - 2$ (todas las entradas excluyendo el $1$ al inicio de la fila y el $1$ al final de la fila), cada una de las cuales puede eliminarse con probabilidad $p$, así que el valor esperado de la fila $n+1$ dado que la suma de la fila $n$ es $x_n$ es

$$\mathbb E(X_{n+1} \mid X_n = x_n) = 2x_n - (2x_n - 2)p = 2(1 - p)x_n + 2p.$$

Por lo tanto, $$\mathbb E(X_{n+1}) = 2(1 - p)\mathbb E(X_n) + 2p,$$ lo que nos da una relación de recurrencia con el caso base $\mathbb E(X_0) = 1.$

---

Para $p=\frac12$ la recurrencia es $$\mathbb E(X_{n+1}) = \mathbb E(X_n) + 1.$$ La solución de la recurrencia es entonces $\mathbb E(X_n) = n + 1$. Luego $$\mathbb E\left(\sum_{k=0}^n X_k\right) = \frac{(n + 1)(n + 2)}{2},$$ que también es el número total de entradas en las filas $0$ a $n$ (inclusive), por lo que la media aritmética esperada de los números en un triángulo cuya última fila es la fila $n$ es $1$.

Conforme $n \to \infty$, entonces, $1 \to 1$.

Sin embargo, la distribución de probabilidad de la media es muy sesgada, lo que puede hacer que sea difícil estimar la media con precisión utilizando muestreo aleatorio. Aquí están los resultados de un millón de repeticiones de una simulación de Python de la suma de entradas en un triángulo hasta la fila $5$. La suma teórica promedio es $21$, pero las sumas ligeramente menores que $21$ son más probables que las sumas ligeramente mayores. Creo que esto puede ayudar a explicar por qué tiendes a encontrar valores medios menores que $1$.

---

Para $p \neq \frac12$ la solución de la recurrencia es

$$\mathbb E(X_n) = \frac{(2 - 2p)^n - 2p}{1 - 2p}.$$

Entonces

$$\begin{align} \mathbb E\left(\sum_{k=0}^n X_k\right) &= \sum_{k=0}^n \frac{(2 - 2p)^n - 2p}{1 - 2p} \\ &= -\frac{2(n+1)p}{1 - 2p} + \frac1{1 - 2p} \sum_{k=0}^n (2 - 2p)^n \\ &= -\frac{2(n+1)p}{1 - 2p} + \frac1{1 - 2p}\cdot\frac{(2-2p)^{n+1} - 1}{(2-2p) - 1} \\ &= \frac{(2-2p)^{n+1} - 1}{(1-2p)^2} - \frac{2(n+1)p}{1 - 2p}. \end{align}$$

Por lo tanto, el valor promedio de las entradas en las filas $0$ a $n$ es

$$\begin{multline} \frac{2}{(n+1)(n+2)} \left(\frac{(2-2p)^{n+1} - 1}{(1-2p)^2} - \frac{2(n+1)p}{1 - 2p} \right) \\ = \frac{2(2-2p)^{n+1} - 2}{(n+1)(n+2)(1-2p)^2} - \frac{4p}{(n+2)(1 - 2p)}. \end{multline}$$

Si $p < \frac12$ entonces $2 - 2p > 1$ y la función exponencial en el numerador del primer término, $(2-2p)^{n+1}$, domina al polinomio en su denominador; así que conforme $n \to +\infty$, $$\begin{align} \frac{2(2-2p)^{n+1} - 2}{(n+1)(n+2)(1-2p)^2} &\to +\infty, \\ \frac{4p}{(n+2)(1 - 2p)} &\to 0, \end{align}$$ por lo que el valor promedio tiende a $+\infty$ conforme $n$ tiende a $+\infty$.

Si $p > \frac12$ entonces $0 \leq 2 - 2p < 1$ y $(2-2p)^{n+1} \to 0$ conforme $n \to +\infty$. Entonces conforme $n\to\infty$, $$\frac{2(2-2p)^{n+1} - 2}{(n+1)(n+2)(1-2p)^2} \to 0,$$ por lo que el valor promedio tiende a $0$ conforme $n$ tiende a $+\infty$.

Answer 2

(Esto se basa en el comentario de @Karl al OP.)

La expectativa de cada número en la fila $2$ (que tiene tres números, incluyendo el lado $1$), es $1$.

Entonces, la expectativa de cada número en la fila $3$, también es $1$. Esto se debe a que la expectativa de cada número es el promedio de las expectativas de los dos números encima de él.

Y así sucesivamente.

Por lo tanto, la expectativa del promedio de todos los números es $1$.

¿Es tan simple?

---

Editar: Para demostrar que este método no siempre funciona (ver comentarios), considera el siguiente problema. Cada número dentro del triángulo es la suma de los dos números encima de él con probabilidad $1/2$, y es el valor absoluto de la diferencia entre los dos números encima de él con probabilidad $1/2$. Usando el método anterior, concluiríamos que la expectativa del valor promedio de todos los números es $1$, pero los resultados experimentales sugieren fuertemente que la expectativa del promedio se acerca a infinito a medida que el número de filas se acerca a infinito.

Answer 3

EDITAR: Tenía $p$ como la probabilidad de mantener distinto de cero, lo cual va en contra de otra respuesta. Ahora tengo

$p$ es la probabilidad de escribir 0.

Pero mi motivo para editar es señalar que, si $2p\gt1$, entonces los primeros promedios en cada fila, (y los últimos, al revés), se acercan a $$1,q,q^2,q^3,\ldots\\q=\frac{1-p}p$$ Suponiendo que hay un límite, $q$ debe cumplir $q=(1-p)(1+q)$. Luego cada límite es $q$ veces el anterior.

Fin de la edición

Hay una contribución de cada $1$ en los lados, cuando son lo suficientemente altos.

$$\sum_{k=r-1}^{n-2}{k\choose r-1}(1-p)^{k+1}+\sum_{k=n-r-1}^{n-2}{k\choose n-r-1}(1-p)^{k+1}$$

La suma hasta la fila $n$, excluyendo los $1$s, es
$$\sum_{k=1}^{n-1} k(2-2p)^{n-k}\\=\frac{(2-2p)^{n+1}-4n(1-p)^2+2(n-1)(1-p)}{(2p-1)^2}$$

Así que la suma de cada fila se promedia en $2(1-p)/(2p-1)$ siempre que $2p\gt1$, o $2p/(2p-1)$ incluyendo los $1$s.