Para obtener una relación de recurrencia conviene considerar en lugar de $p_n$, la función $P_n(t)$ que da la probabilidad de que $X_i + X_{i+1} \le 1$ para toda $i=1, \ldots, n-1$ condicionada a que $X_n = t$. Entonces $p_n = \int_0^1 P_n(t) \; dt$ y las funciones $P_n$ satisfacen la relación de recurrencia $P_{n+1}(t) = \int_0^{1-t} P_n(s) \; ds$ (porque si $X_{n+1}=t$, $X_n$ puede tomar cualquier valor entre $0$ y $1-t$) con condición inicial $P_1(t) = 1$ (si solo hay una variable aleatoria la condición $X_i+X_{i+1}\le 1$ es vacua). Nótese, por la relación de recurrencia que $p_n = P_{n+1}(0)$.
Ahora tenemos que resolver esta relación de recurrencia. Como no se me ocurría como resolverla, calculé los primeros varios $P_n$ a mano (bueno, en la computadora…). Como integra uno $n$ veces, salen factoriales en los denominadores, así que consulté $p_n n! = P_{n+1}(0) n!$ en la Online Encyclopedia of Integer Sequences. Como pueden ver siguiendo la liga, parece que $p_n$ es el coeficiente de $x^n$ en la serie de potencias de $\sec x + \tan x$. Eso lo probaré más abajo, pero por lo pronto, suponiendo que es cierto terminemos el problema:
Pensando en $x$ como una variable compleja, $f(x) := \sec x + \tan x$ es una función meromorfa con únicamente polos simples cuyos polos más cercanos al origen son en $\pi/2$ y $-3\pi/2$. Esto ya nos dice $p_n$ crece como $(2/\pi)^n$, de modo que $\lim_{n\to\infty} (p_n)^{1/n}$ existe y es igual a $\frac{2}{\pi}$ (¡qué para nada me esperaba cuando leí el problema!).
Para probar eso, sea $c$ es el residuo de la función en $\pi/2$ (es fácil de calcular que $c = -2$, pero el valor no importa). Tenemos que la función $g(x) := \sec x + \tan x - \frac{c}{x-\pi/2}$ tiene su polo más cercano al origen en $-3\pi/2$. Eso implica que la serie de Taylor en $x=0$ de $g(x)$ tiene radio de convergencia $3\pi/2$, así que el coeficiente de $x^n$ en $g(x)$ es $O\left((2/3\pi)^n\right)$. Como suponemos que $p_n$ es el coeficiente de $x^n$ en $f(x)$, el coeficiente en $g(x)$ está dado por $p_n - C \left(2/\pi\right)^n$ (donde $C$ es fácil de calcular en términos de $c$, pero su valor no importa), por lo que $p_n = C \left(2/\pi\right)^n + O\left((2/3\pi)^n\right)$.
Para terminar tenemos que probar lo que dijimos sobre $p_n$. Pongo dos pruebas:
Método 1. Sea $F(x,t) = \sum_{n=0}^\infty P_{n+1}(t) x^n$, la función generatriz de las funciones $P_n(t)$. La relación de recurrencia de los $P_n(t)$ equivale a la relación $F(x,t) - 1 = x \int_{0}^{1-t} F(x,s) \; ds$. Habiendo calculado los primeros valores de $P_n(t)$, sabiendo que la solución involcura $\sec x$ y que al hacer las integrales convertimos potencias de $t$ en potencias de $1-t$ y viceversa, no fue muy difícil adivinar que la solución es $F(x,t) = \sec x \left( \cos(tx) + \sin ((1-t) x) \right)$. Es fácil verificar que $F(x,t)$ cumple la relación de recurrencia y que cumple la condición inicial correcta, $F(0,t) = 1 = P_1(t)$. Entonces obtenemos que $\sum_{n=0}^\infty p_n x^n = \sum_{n=0}^\infty P_{n+1}(0) x^n = F(x,0) = \sec x (1 + \sin x) = \sec x + \tan x$, como queríamos.
Método 2. Ya conocía la serie de Taylor de $\sec x + \tan x$: el coeficiente de $x^n$ es $A_n/n!$ donde $A_n$ es el número de permutaciones $a_1, a_2, \ldots, a_n$ de los números del $1$ al $n$ que cumplen que $a_1 > a_2 < a_3 > a_4 < a_5 > \cdots$ (conocidas como permutaciones alternantes o “zig-zag permutations” en inglés). Podemos probar directamente que $p_n = A_n/n!$ olvidándonos de los $P_n(t)$ y su relación de recurrencia. Para eso consideremos nuevas variables aleatorias $Y_1, \ldots, Y_n$ dadas por $Y_i = 1-X_i$ si $i$ es impar y $Y_i = X_i$ si $i$ es par. Entonces,
-
Las $Y_i$ son variables aleatorias uniformemente distribuidas en $[0,1]$ y ¡también son independientes¡
-
El evento $X_i + X_{i+1} \le 1$ para $i=1,2,\ldots,n-1$ corresponde al evento $Y_1 \ge Y_2 \le Y_3 \ge Y_4 \le Y_5 \ge \cdots$.
Que dos de las $Y_i$ sean iguales tiene probabilidad cero. Cuando son todas distintas, si nos fijamos en la permutación que las pone en orden, las $n!$ permutaciones son igualmente probables. Por lo tanto, la probabilidad del evento descrito arriba es justo $A_n / n!$ como queríamos.