Matemáticas universitarias — Grado 2 · Bachelor Year 2

21Probabilidad en espacios contables

Los últimos tres capítulos desarrollan la teoría de la probabilidad de la programa MP* moderno: medidas de probabilidad en contable muestra espacios, variables aleatorias discretas y funciones generadoras. el La teoría finita del volumen de High School adquiere su plenitud. infraestructura: $\sigma$ -aditividad reemplaza la aditividad finita, y la maquinaria de la familia sumable de Capítulo 7 es exactamente lo que hace que el infinito espacios muestrales sea viable. el Los resultados centrales aquí son el continuidad de probabilidad a lo largo secuencias monótonas de eventos y el lema de Borel-Cantelli.

21.1 Espacios de probabilidad

Definición 21.1 (Espacio de probabilidad contable)

Sea $\Omega$ un finito no vacío o conjunto contable (el espacio muestral). Un probabilidad medida en $\Omega$ es un mapa $\P$ del conjunto $\mathcal{P}(\Omega)$ de todos los subconjuntos de $\Omega$ (eventos) a $[0, 1]$ tal que:

$\P(\Omega) = 1$ ;
( $\sigma$ -aditividad) para cada secuencia $(A_n)_{n\in\N}$ de eventos disjuntos por pares,

$\P\Bigl(\,\bigcup_{n \in \N} A_n\Bigr) = \sum_{n=0}^{\infty} \P(A_n) .$

El par $(\Omega, \P)$ es un (contable) probabilidad espacio.

Observación 21.2

En un contable $\Omega$ podemos tomar todos los subconjuntos como eventos; en espacios incontables (según sea necesario para los modelos continuo en el año 3) Esto ya no es posible y se restringe $\P$ a un número adecuado. colección de eventos, un $\sigma$ -algebra. Todas las fórmulas Los textos de este capítulo sobreviven textualmente a esa generalización.

Proposición 21.3 (reglas elementales)

Para eventos $A, B$ y medida de probabilidad $\P$ : $\P(\emptyset) = 0$ ; $\P$ es finitamente aditivo; $\P(A^c) = 1 - \P(A)$ ; si $A \subseteq B$ entonces $\P(A) \leq \P(B)$ ; y

\P(A \cup B) = \P(A) + \P(B) - \P(A \cap B) .

Demostración. Aplicando la aditividad $\sigma$ a $A_0 = \Omega$ , $A_n = \emptyset$ ( $n \geq 1$ ) da $1 = 1 + \sum_{n\geq1}\P(\emptyset)$ , entonces $\P(\emptyset) = 0$ ; rellenar una unión finita disjunta con vacío conjuntos entonces da aditividad finita. El resto sigue como en el caso finito (volumen de escuela secundaria): $1 = \P(A) + \P(A^c)$ de $\Omega = A \sqcup A^c$ ; $\P(B) = \P(A) + \P(B \setminus A) \geq \P(A)$ cuando $A \subseteq B$ ; y descomponerse en tres piezas separadas,

\begin{align*} \P(A \cup B) &= \P(A \setminus B) + \P(B \setminus A) + \P(A \cap B)\\ &= \bigl(\P(A) - \P(A\cap B)\bigr) + \bigl(\P(B) - \P(A\cap B)\bigr) + \P(A \cap B), \end{align*}

que es inclusión-exclusión; la versión general del conjunto $n$ es Ejercicio 21.4. ∎

Proposición 21.4 (Distribuciones en un contable espacio)

Dar un medida de probabilidad a un contable $\Omega = \{\omega_0, \omega_1, \dots\}$ equivale exactamente a dar pesos $p_i = \P(\{\omega_i\}) \geq 0$ con $\sum_i p_i = 1$ ; entonces para cada $A \subseteq \Omega$ ,

\P(A) = \sum_{\omega \in A} \P(\{\omega\}) ,

una subsuma (absolutamente convergente) de la familia $(p_i)$ .

Demostración. Dado $\P$ , los singletons $\{\omega\}$ , $\omega \in A$ , forman un contable cubierta separada de $A$ , por lo que $\sigma$ -fuerzas de aditividad

\P(A) = \sum_{\omega\in A}\P(\{\omega\}),

una subsuma incondicional del familia sumable no negativo $(p_i)$ — reordenar es inofensivo precisamente porque el los términos no son negativos (Capítulo 7); en particular $\sum_ip_i = \P(\Omega) = 1$ . Por el contrario, dados los pesos no negativos de la suma total $1$ , defina $\P(A) = \sum_{\omega \in A}p_\omega$ : la familia es sumable, y $\sigma$ -la aditividad es exactamente el teorema de la suma por paquetes de Capítulo 7 aplicado a la partición de $\bigcup A_n$ en el $A_n$ . ∎

Ejemplo 21.5 (Modelo geométrico: esperando el primero cabeza)

Lanza una moneda con probabilidad de cara $p \in \intoo{0}{1}$ repetidamente, y dejemos que $\Omega = \N^* \cup \{\infty\}$ registre el rango del primera cabeza. Los pesos naturales son

\P(\{k\}) = (1 - p)^{k-1}p \quad (k \in \N^*), \qquad \P(\{\infty\}) = 0 ,

a medida de probabilidad desde $\sum_{k\geq1}(1-p)^{k-1}p = \frac{p}{1 - (1-p)} = 1$ : con probabilidad $1$ el juego termina — pero el espacio muestral aún debe contener la posibilidad de que no lo hace. Contable la aditividad es lo que nos permite afirmar $\P(\text{the game ends}) = \sum_k \P(\{k\})$ .

Teorema 21.6 (Continuidad monótona)

Sea $(A_n)$ una secuencia de eventos.

Si $A_n \subseteq A_{n+1}$ para todos $n$ (creciente), entonces $\P\bigl(\bigcup_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .
Si $A_n \supseteq A_{n+1}$ para todos $n$ (decreciente), entonces $\P\bigl(\bigcap_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .

Demostración. 1. Desunir: sean $B_0 = A_0$ y $B_n = A_n \setminus A_{n-1}$ . Los $B_n$ están separados por pares de $\bigcup_{k \leq n} B_k = A_n$ y $\bigcup_n B_n = \bigcup_n A_n$ . Por $\sigma$ -aditividad y aditividad finita,

\P\Bigl(\bigcup_n A_n\Bigr) = \sum_{n=0}^\infty \P(B_n) = \lim_{N\to\infty}\sum_{n=0}^N \P(B_n) = \lim_{N\to\infty}\P(A_N) .

2. Pase a complementos: $(A_n^c)$ es creciente con unión $\bigl(\bigcap A_n\bigr)^c$ y aplique la parte 1: $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$ . ∎

Corolario 21.7 (Subaditividad contable)

Para cualquier secuencia de eventos, $\P\bigl(\bigcup_n A_n\bigr) \leq \sum_{n=0}^\infty \P(A_n)$ .

Demostración. La subaditividad finita $\P(A_0 \cup \dots \cup A_N) \leq \sum_0^N \P(A_n)$ se deriva de la inclusión-exclusión por inducción (o de aditividad sobre el $B_n \subseteq A_n$ desarticulado). Sea $N \to \infty$ : el lado izquierdo converge a $\P(\bigcup_n A_n)$ por el monótono continuidad aplicado al secuencia creciente $C_N = A_0 \cup \dots \cup A_N$ . ∎

Ejemplo 21.8 (El sindicato obligado: crudo pero indestructible)

La subaditividad con un número finito de eventos — el unión atado — intercambia precisión por universalidad. Para el problema de cumpleaños con personas $23$ , delimitando la colisión probabilidad por la suma de pares da

\P(\text{collision}) \leq \binom{23}2\cdot\frac1{365} = \frac{253}{365} \approx 0.693 ,

contra el verdadero $0.507$ : lejos por un amplio margen, porque las colisiones se superponen. Sin embargo, el límite necesita no independencia, sin ley conjunta, nada más que la pareja probabilidades — razón por la cual, en el problema del fin de semana y a lo largo de Capítulo 22, el límite sindical es el primera herramienta dibujada: cuando resulta pequeña, la cuestión es resuelto sin más modelos.

Ejemplo 21.9 (Al final llega un seis)

Tira un dado justo para siempre y deja que $B_n = {}$ “al menos un seis entre los primeros rollos $n$ ”, una secuencia creciente de eventos con $\P(B_n) = 1 - (5/6)^n$ . Monótono continuidad da

\P(\text{a six eventually appears}) = \P\Bigl(\bigcup_nB_n\Bigr) = \lim_n\bigl(1 - (5/6)^n\bigr) = 1 .

La cuestión no es el límite (obvio) sino el paso lógico: “eventualmente” es un evento sobre infinitamente muchos rollos, fuera del alcance de la aditividad finita, y monótonos continuidad — es decir, $\sigma$ -aditividad — es precisamente el axioma que le asigna una probabilidad. Cada casi seguro declaración en el resto de este libro pasa por este mismo puerta estrecha.

21.2 Condicionamiento e independencia

Definición 21.10 (Probabilidad condicional)

Para eventos $A, B$ con $\P(B) > 0$ , el condicional probabilidad de $A$ dado $B$ es

\P(A \mid B) = \frac{\P(A \cap B)}{\P(B)} .

El mapa $A \mapsto \P(A \mid B)$ es en sí mismo un medida de probabilidad. en $\Omega$ .

Observación 21.11

Ese $A \mapsto \pcond BA$ es nuevamente un medida de probabilidad es Vale la pena un momento: $\pcond B\Omega = 1$ y $\sigma$ -aditividad pasar por el cociente porque intersección con $B$ respeta las uniones disjuntas. La consecuencia práctica: cada identidad de este capítulo — inclusión –exclusión, monótono continuidad, Borel–Cantelli — se puede aplicar después Acondicionamiento, sin nuevas pruebas. Probabilistas constantemente “funciona bajo $\pcond B{\cdot}$ ” exactamente por esta razón.

Ejemplo 21.12 (El condicionamiento puede crear uniformidad)

Tira dos dados justos y condiciona que la suma sea $7$ : para cada $k \in \intint16$ ,

\pcond{\{S = 7\}}{X = k} = \frac{\P(X = k,\ Y = 7 - k)}{\P(S = 7)} = \frac{1/36}{6/36} = \frac16 :

dada una suma de $7$ , el primer dado es exactamente uniforme — $7$ es el único totalmente compatible con todos los rostros, por lo que el El acondicionamiento borra toda la información sobre $X$ . cualquier otro total sesga la ley (dado $S = 4$ , el primer dado es uniforme en $\{1, 2, 3\}$ únicamente). Calcular una ley condicional significa Renormalizar los pesos de las articulaciones a lo largo del acondicionamiento. evento, nada más.

Ejemplo 21.13 (El segundo sorteo es tan bueno como el primero)

Una urna contiene bolas $3$ blancas y $2$ negras; dibujar dos sin reemplazo. Todos están de acuerdo $\P(W_1) = \frac35$ ; que es $\P(W_2)$ ? Probabilidad total en el primer sorteo:

\P(W_2) = \pcond{W_1}{W_2}\,\P(W_1) + \pcond{B_1}{W_2}\,\P(B_1) = \frac24\cdot\frac35 + \frac34\cdot\frac25 = \frac{12}{20} = \frac35 :

exactamente $\P(W_1)$ . No fue necesario ningún cálculo: por simetría, cada bola tiene la misma probabilidad de ser la segunda extraída, por lo que el segundo sorteo — incondicionalmente — tiene el mismo ley como la primera. El condicionamiento sobre el primer resultado cambia. las probabilidades; sin saberlo no es así. Esta intercambiabilidad El argumento regresa en el próximo capítulo para el muestreo sin reemplazo, donde da la media hipergeométrica $np$ sin ninguna identidad binomial.

Teorema 21.14 (Probabilidades compuestas, probabilidad total, Bayes)

(Regla de cadena) Si $\P(A_1 \cap \dots \cap A_{n-1}) > 0$ ,

$\P(A_1 \cap \dots \cap A_n) = \P(A_1)\,\P(A_2 \mid A_1)\cdots \P(A_n \mid A_1 \cap \dots \cap A_{n-1}) .$
(Probabilidad total) Si $(B_i)_{i \in I}$ es finito o contable partición de $\Omega$ con $\P(B_i) > 0$ , luego para cada evento $A$ :

$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$
(Bayes) Bajo las mismas hipótesis, si además $\P(A) > 0$ :

$\P(B_j \mid A) = \frac{\P(A \mid B_j)\,\P(B_j)} {\sum_{i \in I} \P(A \mid B_i)\,\P(B_i)} .$

Demostración. 1. Escribe cada probabilidad condicional como cociente: el lado derecho es

\P(A_1)\cdot\frac{\P(A_1 \cap A_2)}{\P(A_1)}\cdot \frac{\P(A_1 \cap A_2 \cap A_3)}{\P(A_1 \cap A_2)}\cdots \frac{\P(A_1 \cap \dots \cap A_n)}{\P(A_1 \cap \dots \cap A_{n-1})},

un producto telescópico: cada denominador cancela el numerador anterior, dejando $\P(A_1 \cap \dots \cap A_n)$ . Todos los denominadores son $\geq \P(A_1 \cap \dots \cap A_{n-1}) > 0$ por monotonía, por lo que nada desaparece. (La hipótesis protege exactamente esto: condicionado a un evento de probabilidad cero no está definido.) 2. Los conjuntos $A \cap B_i$ son disjuntos por pares con unión $A$ ; aplicar ( $\sigma$ -)la aditividad y la definición de acondicionamiento. 3. Ambos lados de $\P(B_j \mid A)\P(A) = \P(A \mid B_j)\P(B_j)$ son iguales a $\P(A \cap B_j)$ ; dividir por $\P(A)$ y expandir $\P(A)$ por probabilidad total. ∎

Ejemplo 21.15 (La colisión del cumpleaños, por la cadena. regla)

Con $n$ personas cuyos cumpleaños son independiente y uniformes durante $365$ días, deje que $D_n = {}$ “todos los cumpleaños de $n$ difieran”. Condicionamiento persona por persona (regla de la cadena):

\P(D_n) = \prod_{k=1}^{n-1}\Bigl(1 - \frac{k}{365}\Bigr),

cada nueva persona deberá evitar los $k$ días ya tomados. Para $n = 23$ : $\P(D_{23}) \approx 0.493$ — un compartido El cumpleaños ya es más probable que no. La heurística que explica la pequeñez de $23$ : tomando logaritmos, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$ y $\binom{23}2 = 253$ da $253/365 \approx 0.693 \approx \ln 2$ . Lo que importa es el número de pares, que crece cuadráticamente: colisión los problemas viven en la escala $n \sim \sqrt{365}$ , no en $n \sim 365$ — la paradoja del cumpleaños es una raíz cuadrada disfrazada.

Ejemplo 21.16 (Monty Hall, por Bayes)

Un premio se esconde detrás de una de las tres puertas, de manera uniforme. tu eliges puerta $1$ ; el anfitrión, que sabe dónde está el premio, abre uno de las demás puertas, siempre vacías (eligiendo uniformemente cuando tenga una opción), diga puerta $3$ . Deja el premio $B_i = {}$ “ detrás de la puerta. $i$ ” y $A = {}$ “el host abre la puerta $3$ ”. entonces $\pcond{B_1}{A} = \frac12$ , $\pcond{B_2}{A} = 1$ , $\pcond{B_3}{A} = 0$ , así por Bayes (Teorema 21.14),

\P(B_2 \mid A) = \frac{1\cdot\frac13} {\frac12\cdot\frac13 + 1\cdot\frac13 + 0\cdot\frac13} = \frac23 :

Cambiar de puerta gana dos de cada tres veces. el computo Localiza exactamente la confusión popular: la jugada del anfitrión es informativo (no podría abierto puerta $2$ si el premio estaban allí), y la fórmula de Bayes es el dispositivo de contabilidad que convierte esta asimetría en el $\frac23$ . Acondicionamiento en "lo que se vio" más que en "lo que es verdad", es la Todo el arte de la fórmula.

Ejemplo 21.17 (Los dos del Chevalier de Méré apuestas)

Dos apuestas del siglo XVII, resueltas por independencia. apuesta uno: al menos un seis en $4$ tiradas de un dado,

\P = 1 - \Bigl(\frac56\Bigr)^{\!4} \approx 0.518 > \frac12 .

Apuesta dos: al menos un doble seis en $24$ tiradas de dos dados,

\P = 1 - \Bigl(\frac{35}{36}\Bigr)^{\!24} \approx 0.491 < \frac12 .

De Méré razonó que $24$ rueda al azar $\frac1{36}$ debe coincidir con las tiradas $4$ al azar $\frac16$ (misma proporción $\frac{24}{36} = \frac46$ ); el fracaso de este proporcionalidad — las probabilidades de las uniones no escalan linealmente — se dice que motivó su carta a Pascal, y con ello el nacimiento de la teoría de la probabilidad. lo correcto la comparación es mediante logaritmos: $n$ ensayos al azar $p$ tener éxito al menos una vez con probabilidad $1 - (1-p)^n \approx 1 - \eu^{-np}$ , por lo que la invariante honesta es $np$ : aquí $4\cdot\frac16 = \frac23$ versus $24\cdot\frac1{36} = \frac23$ — ¡iguales! Las dos apuestas difieren sólo en el segundo orden en $p$ , y lo suficiente como para mover uno a través del línea del cincuenta por ciento: las probabilidades pequeñas son un dominio donde la intuición necesita el exponencial, no el gobernante.

Observación 21.18 (Falacias comunes del condicionamiento)

Tres confusiones recurrentes, todas visibles en los ejemplos. arriba. (i) inversión: $\pcond BA$ y $\pcond AB$ difieren por el factor $\P(A)/\P(B)$ — una prueba que es $99\%$ preciso sobre los enfermos aún puede dejar un positivo Es casi seguro que el paciente está sano cuando la enfermedad es rara. (Ejercicio 21.3); citar $\pcond{\text{sick}}{ \text{positive}}$ donde se refiere a $\pcond{\text{positive}}{ \text{sick}}$ es la falacia de la tasa base. (ii) Conditioning on the wrong evento: en Monty Hall, el El acondicionamiento correcto evento es "el host abrió la puerta $3$ ", no “el premio no está detrás de la puerta $3$ ”; los dos llevan información diferente, y todo el $\frac23$ cuelga en el diferencia. (iii) Disjoint versus independiente: eventos disjuntos de probabilidad positiva nunca son independiente ( $\P(A\cap B) = 0 \neq \P(A)\P(B)$ ) — independencia es compatibilidad de información, no ausencia de superposición.

Definición 21.19 (Independencia)

Eventos $A$ y $B$ son independiente si $\P(A \cap B) = \P(A)\P(B)$ . Una familia $(A_i)_{i \in I}$ de eventos es (mutuamente) independientes si para cada subconjunto finito $J \subseteq I$ ,

\P\Bigl(\bigcap_{i \in J} A_i\Bigr) = \prod_{i \in J} \P(A_i) .

Observación 21.20

Mutual independencia es estrictamente más fuerte que por pares independencia: con dos lanzamientos de moneda justos, el eventos “primero es un cabeza”, “la segunda es una cabeza”, “ambos de acuerdo” son pares independiente (cada par tiene probabilidad de intersección $\frac14 = \frac12\cdot\frac12$ ), pero la intersección triple tiene probabilidad $\frac14 \neq \frac18$ . Tenga en cuenta también que si $A, B$ es independiente, también lo son $A, B^c$ (calcular: $\P(A \cap B^c) = \P(A) - \P(A\cap B) = \P(A)(1 - \P(B))$ ), por lo tanto también $A^c, B^c$ .

Ejemplo 21.21 (Lectura de independencia de un producto estructura)

Tira dos dados justos: $\Omega = \intint16^2$ con uniforme pesos. Deje que $A = {}$ “primero muera incluso” y $B = {}$ “segundo morir al menos $5$ ”. Contando: $\abs A = 3\cdot6 = 18$ , $\abs B = 6\cdot2 = 12$ , $\abs{A\cap B} = 3\cdot2 = 6$ , entonces

\P(A\cap B) = \frac6{36} = \frac{18}{36}\cdot\frac{12}{36} = \P(A)\,\P(B) :

independiente, y el mecanismo es visible — $A$ limita sólo la primera coordenada, $B$ sólo la segunda, y la La medida uniforme en un conjunto de productos hace el recuento de coordenadas. multiplicar. Todo reclamo del tipo “eventos dependiendo de grupos disjuntos de lanzamientos son independiente” (usados masivamente en el problema del fin de semana) es este cálculo, usando más índices.

Ejemplo 21.22 (Análisis del primer paso)

Para el modelo geométrico de Ejemplo 21.5, ¿Cuál es la probabilidad $u$ de que la primera cara caiga en un XXXP0785Rango XXX? Condición en el primer lanzamiento: con probabilidad $p$ el rango es $1$ (impar); con probabilidad $q = 1 - p$ el el juego se reinicia con todas las paridades invertidas, por lo que

u = p\cdot0 + q\,(1 - u) \qquad\Longrightarrow\qquad u = \frac{q}{1 + q} .

Una línea, ninguna serie — y concuerda con el directo suma de Ejercicio 21.9, lo que da $1 - u = \frac1{1+q}$ . Esta técnica del "primer paso" (condición de el primer experimento, reconocer una copia desplazada del problema) es la forma probabilística de una recursividad, y es el motor detrás de las ecuaciones de duración del juego de Ejercicio 21.6 y los cálculos del primer paso de El problema del fin de semana.

21.3 El lema de Borel-Cantelli

Definición 21.23 (Límite superior de eventos)

Para una secuencia $(A_n)$ de eventos, el evento

\limsup_n A_n = \bigcap_{N=0}^{\infty}\ \bigcup_{n \geq N} A_n = \{\omega \in \Omega : \omega \in A_n \text{ for infinitely many } n\}

es el evento “ $A_n$ ocurre infinitamente con frecuencia”.

Ejemplo 21.24 (Traduciendo “infinitamente frecuente” y “eventualmente”)

El complemento de $\limsup_nA_n$ es, por de Morgan,

\Bigl(\bigcap_N\bigcup_{n\geq N}A_n\Bigr)^{\!c} = \bigcup_N\bigcap_{n\geq N}A_n^c = \{\omega : \omega \notin A_n \text{ for all large }n\},

el evento “eventualmente, $A_n$ falla” (escrito $\liminf_nA_n^c$ ). Entonces “ $A_n$ infinitamente frecuente” y “ $A_n^c$ eventualmente” son complementarios — manteniendo esto El diccionario directo previene la mayoría de los accidentes con cuantificadores. Ejemplos de traducciones para lanzar una moneda al aire: “infinitamente muchos cabezas” es $\limsup\{X_n = H\}$ ; “sólo un número finito de ejecuciones de $100$ cabezas” es el complemento de un limsup; “el La frecuencia de funcionamiento converge a $\frac12$ ” es $\bigcap_j\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - \tfrac12} < \tfrac1j\}$ — contable operaciones en todo momento, entonces todos estos son honestos eventos.

Teorema 21.25 (Borel–Cantelli)

Si $\sum_{n} \P(A_n) < \infty$ , entonces $\P\bigl(\limsup_n A_n\bigr) = 0$ .
Si eventos $A_n$ son independiente y $\sum_n \P(A_n) = \infty$ , entonces $\P\bigl(\limsup_n A_n\bigr) = 1$ .

Demostración. 1. Dejar $C_N = \bigcup_{n \geq N}A_n$ ; la secuencia $(C_N)$ está disminuyendo con la intersección $\limsup A_n$ y por contable subaditividad (Corolario 21.7)

\P(C_N) \leq \sum_{n \geq N}\P(A_n) \xrightarrow[N\to\infty]{} 0

(cola de una serie convergente). Monótono continuidad (Teorema 21.6) concluye: $\P(\limsup A_n) = \lim_N \P(C_N) = 0$ .

2. Basta mostrar $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ por cada $N$ : efectivamente, si eventos $B_N$ todos tienen probabilidad $1$ , entonces

\P\Bigl(\Bigl(\bigcap_NB_N\Bigr)^{\!c}\Bigr) = \P\Bigl(\bigcup_NB_N^c\Bigr) \leq \sum_N\P(B_N^c) = 0

por contable subaditividad (Corolario 21.7), por lo que la intersección contable $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ todavía tiene probabilidad $1$ . Repare $N$ y considere para $M > N$ el complemento:

\P\Bigl(\bigcap_{n=N}^{M} A_n^c\Bigr) = \prod_{n=N}^{M}\bigl(1 - \P(A_n)\bigr) \leq \prod_{n=N}^{M} e^{-\P(A_n)} = \exp\Bigl(-\sum_{n=N}^M \P(A_n)\Bigr) ,

usando independencia de los complementos y la convexidad ligada a $1 - x \leq e^{-x}$ . Como $M \to \infty$ el exponente tiende a $-\infty$ por divergencia de la serie, por lo monótono continuidad (secuencia decreciente) $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$ , es decir, $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$ . ∎

Ejemplo 21.26 (Carreras infinitas de cabezas)

Lanza una moneda justa para siempre y deja que $A_n$ sea el evento “los lanzamientos $n, n+1, \dots, n + k - 1$ son todos caras” (una serie de $k$ caras). comenzando en el momento $n$ ), para fijo $k$ . Los eventos $A_{jk}$ ( $j = 1, 2, \dots$ ), dependiendo de bloques de lanzamientos separados, son independiente, cada uno de probabilidad $2^{-k}$ y $\sum_j 2^{-k} = \infty$ : por Borel–Cantelli 2, con probabilidad $1$ infinitamente muchos bloques son todos cabezas — cada se repite el patrón fijo infinitamente a menudo, casi con seguridad. Por el contrario, si dejamos correr longitud crece, $B_n = {}$ “una serie de cabezas $2\log_2 n$ comienza en $n$ ” tiene $\P(B_n) = n^{-2}$ sumable, por lo que casi seguramente solo un número finito de carreras largas de este tipo comienzan: Borel–Cantelli calibra Precisamente cuánto tiempo son los tramos más largos.

Ejemplo 21.27 (El mono infinito, cuantificado)

Un mono escribe independiente letras uniformes de un XXXP0282Alfabeto de letras XXX. Cortar el texto mecanografiado en bloques separados de cuatro letras; los hechizos eventos $A_j = {}$ “bloquear $j$ MATH” son independiente con $\P(A_j) = 26^{-4}$ , y $\sum_j\P(A_j) = \infty$ : por Borel–Cantelli 2 el mono escribe MATH infinitamente a menudo, casi con seguridad — y lo mismo es válido para cualquier texto fijo de cualquier longitud, bloques ajustados. La nota cuantitativa a pie de página desinfla el milagro: $26^4 = 456\,976$ , por lo que el primer MATH cuesta alrededor de medio millón pulsaciones de teclas en promedio, y una obra de Shakespeare de $10^5$ caracteres en espera de bloques de orden $26^{10^5}$ — casi seguro es una declaración sobre el horizonte $\infty$ , no sobre cualquier horizonte se encontrará un mono. Borel–Cantelli certifica la límite; El tamaño de los sumandos cuenta la historia a escalas humanas.

Observación 21.28

En Ejemplo 21.26 el espacio muestral subyacente (infinito secuencias de lanzamientos) es incontable, por lo que estrictamente hablando el ejemplo vive en el marco teórico de medidas del año 3; el cálculos, sin embargo, utilice sólo las reglas probadas en este capítulo, aplicado a eventos determinado por un número finito de lanzamientos y sus combinaciones contable. Esta es la convención MP* estándar: la teoría se establece en espacios contable y juego infinito Los ejemplos se tratan con el mismo conjunto de herramientas.

Observación 21.29 (Perspectivas dentro de este volumen)

La maquinaria de este capítulo se consume al por mayor en el próximo. dos. Los indicadores convierten eventos en variables aleatorias y La aditividad $\sigma$ se convierte en la sumabilidad que define expectativa (Capítulo 22); Borel–Cantelli más un sumable cola atada es exactamente como la fuerte ley de lo grande Los números de las monedas se demuestran allí. en Capítulo 23, monótono continuidad reaparece en el momento decisivo: la probabilidad de extinción de una ramificación El proceso es definido como límite monótono. $\lim\P(Z_n = 0)$ , y la ecuación de punto fijo que satisface se obtiene pasando al límite en ese sentido creciente secuencia — el teorema final del libro se basa en esto primer teorema del capítulo.

Observación 21.30 (Método: tres formas de obtener la probabilidad uno)

Las afirmaciones casi seguras se prueban con tres palancas, en orden creciente de fuerza. Monotone continuidad: exhibir el evento como una unión creciente (o decreciente intersección) del horizonte finito eventos con computable probabilidades (Ejemplo 21.9). Uniones nulas: una unión contable de probabilidad cero eventos es nulo (subaditividad contable), por lo que basta con elimine cada evento malo por separado — así es como “para cada $j$ , eventualmente $\abs{\widehat p_n - p} < 1/j$ ” se ensambla hacia la convergencia. Borel–Cantelli: cuando el evento es un limsup, suma las probabilidades; la convergencia lo mata (no se necesita independencia) y divergencia más independencia lo certifica. Elegir la palanca adecuada suele ser todo prueba; el problema del fin de semana ejecuta los tres en una sola argumento.

Observación 21.31 (donde se utiliza)

Monotone continuidad y Borel–Cantelli son las dos palancas de cada afirmación "casi segura": impulsan la recurrencia de el paseo aleatorio en el problema de fin de semana de este capítulo, el lado casi seguro de la ley de los grandes números (Capítulo 22), y el análisis de extinción de procesos de ramificación (Capítulo 23). El volumen del año 3 reconstruye la teoría sobre $\sigma$ -álgebras y Lebesgue integración, donde se utilizó el incontable espacios muestrales informalmente aquí se vuelven completamente rigurosos.

21.4 Ceremonias

Ejercicio 21.1 ★

Una urna contiene bolas numeradas $n$ . Las bolas se extraen una a una. sin reemplazo. Calcule la probabilidad de que la bola número $1$ se sortea antes de la bola número $2$ . Generalizar: la probabilidad de que La bola $1$ se extrae primero entre las bolas $1, \dots, k$ .

Solución

Solución de Ejercicio 21.1.

Por simetría: el orden de dibujo induce un relativo uniformemente aleatorio ordene las bolas $1$ y $2$ , por lo que $\P(1 \text{ before } 2) = \frac12$ . Formalmente: intercambiando las posiciones de las bolas $1$ y $2$ en una secuencia de dibujo es una biyección del (equiprobable) resultados que intercambia el evento con su complemento. entre bolas $1, \dots, k$ : el orden relativo de estas bolas $k$ es uniforme entre los pedidos $k!$ , y la bola $1$ es la primera en $(k-1)!$ de ellos: probabilidad $\frac{(k-1)!}{k!} = \frac1k$ .

Ejercicio 21.2 ★

Muestre que en $\Omega = \N^*$ los pesos $p_k = \frac{1}{k(k+1)}$ defina un medida de probabilidad y calcule $\P(2\N^*)$ (incluso resultados) como una serie; demuestre que es igual a $1 - \ln 2$ . (Telescope $\frac{1}{2j(2j+1)} = \frac{1}{2j} - \frac{1}{2j+1}$ and use the alternating harmonic series, Capítulo 7.)

Solución

Solución de Ejercicio 21.2.

$\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$ , entonces $\sum_{k\geq1} p_k$ telescopios a $1$ : a medida de probabilidad. Resultados pares:

\P(2\N^*) = \sum_{j=1}^{\infty}\frac{1}{2j(2j+1)} = \sum_{j=1}^{\infty}\Bigl(\frac{1}{2j} - \frac{1}{2j+1}\Bigr) = \frac12 - \frac13 + \frac14 - \frac15 + \cdots

Esta es la serie armónica alterna con su primer término. eliminado y signos volteados: desde $\ln 2 = 1 - \frac12 + \frac13 - \frac14 + \cdots$ (Capítulo 7),

\P(2\N^*) = -\bigl(\ln 2 - 1\bigr) = 1 - \ln 2 \approx 0.307 .

Ejercicio 21.3 ★

(Falsos positivos) Una enfermedad afecta a una persona en $10\,000$ . un La prueba lo detecta con probabilidad $0.99$ en los enfermos y da un falso positivo con probabilidad $0.01$ en sanos. calcular la probabilidad de estar enfermo en caso de una prueba positiva y comentar.

Solución

Solución de Ejercicio 21.3.

Sea $S$ = enfermo, $+$ = prueba positiva. Bayes (Teorema 21.14) con la partición $\{S, S^c\}$ :

\P(S \mid +) = \frac{0.99 \times 10^{-4}} {0.99 \times 10^{-4} + 0.01 \times 0.9999} = \frac{0.000099}{0.000099 + 0.009999} \approx 0.0098 ,

debajo de $1\%$ . Aunque la prueba es "99% precisa", un resultado positivo resultado le deja aproximadamente $99\%$ probablemente saludable: el falso Los aspectos positivos entre la gran mayoría sana inundan la verdadera aspectos positivos de la pequeña minoría enferma. Pruebas de detección para casos raros Las condiciones siempre deben leerse a través de esta tarifa base. cálculo.

Ejercicio 21.4 ★★

Sea $A_1, \dots, A_n$ eventos. Demostrar la inclusión-exclusión fórmula

\P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\,\P\Bigl(\bigcap_{i \in J}A_i\Bigr)

integrando la identidad $1 - \prod_{i=1}^n(1 - \mathbf{1}_{A_i}) = \mathbf{1}_{\bigcup A_i}$ sobre $\Omega$ (es decir, suma ponderada por $\P(\{\omega\})$ ).

Solución

Solución de Ejercicio 21.4.

Puntualmente en $\Omega$ : $\omega \in \bigcup A_i$ si hay algún factor $1 - \mathbf{1}_{A_i}(\omega)$ desaparece, entonces

\mathbf{1}_{\bigcup A_i} = 1 - \prod_{i=1}^n\bigl(1 - \mathbf{1}_{A_i}\bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\prod_{i \in J}\mathbf{1}_{A_i} ,

expandiendo el producto y moviendo el $1$ . ahora $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J} A_i}$ , y sumando contra los pesos $\P(\{\omega\})$ — legítimo: un número finito de términos acotados, cada familia sumable — convierte cada indicador en la probabilidad de su evento, dando la fórmula.

Ejercicio 21.5 ★★

(Problema de coincidencia, vía inclusión–exclusión) $n$ se ponen letras uniformemente al azar en sobres $n$ , uno cada uno. Usando Ejercicio 21.4, muestra que la probabilidad de no la coincidencia correcta es $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$ , y deducir la probabilidad de exactamente una coincidencia.

Solución

Solución de Ejercicio 21.5.

Sea $A_i$ = “la letra $i$ está en el sobre correcto”. Para $J$ de tamaño $k$ , $\P\bigl(\bigcap_{i\in J}A_i\bigr) = \frac{(n-k)!}{n!}$ (arregle las letras $k$ , permute el resto). Por inclusión-exclusión,

\P\Bigl(\bigcup A_i\Bigr) = \sum_{k=1}^n (-1)^{k+1}\binom nk \frac{(n-k)!}{n!} = \sum_{k=1}^n \frac{(-1)^{k+1}}{k!} ,

entonces

\P(\text{no match}) = 1 - \P\Bigl(\bigcup A_i\Bigr) = \sum_{k=0}^{n}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} \approx 0.368 .

Exactamente una coincidencia: una permutación con exactamente un punto fijo es determinado por la elección de la letra fija ( $n$ formas) y una trastorno mental (acuerdo sin coincidencia) del otro $n - 1$ ; escribiendo $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ para el número de trastornos (la primera parte, escalada por $(n-1)!$ ),

\P(\text{exactly one match}) = \frac{n\,D_{n-1}}{n!} = \frac{D_{n-1}}{(n-1)!} = \sum_{k=0}^{n-1}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} :

en el límite, "ninguna coincidencia" y "exactamente una coincidencia" son igualmente probable, cada uno con probabilidad $e^{-1}$ .

Ejercicio 21.6 ★★

Se lanza una moneda sesgada (probabilidad de cara $p \in \intoo{0}{1}$ ) hasta que aparezcan dos cabezas consecutivas. Sea $q_n$ la probabilidad que el juego dure más de $n$ lanzamientos. Mostrar, acondicionar los primeros lanzamientos, ese $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ para $n \geq 2$ , y deducir que el juego termina con probabilidad $1$ . (Show $q_n \to 0$ by comparing with a geometric sequence: both roots of the characteristic equation lie in $\intoo{0}{1}$ in absolute value.)

Solución

Solución de Ejercicio 21.6.

Condición al inicio (regla de la cadena / Teorema 21.14):

primer lanzamiento T (probabilidad $1 - p$ ): el juego se reinicia de nuevo; que dure más de $n$ significa que dure más de $n - 1$ desde allí: contribución $(1-p)\,q_{n-1}$ ;
primeros lanzamientos HT (probabilidad $p(1-p)$ ): reinicio después de dos lanzamientos: contribución $p(1-p)\,q_{n-2}$ ;
primeros lanzamientos HH: el juego ha finalizado (dentro de $n$ lanzamientos, $n \geq 2$ ): aporta $0$ .

Por lo tanto $q_n = (1-p)q_{n-1} + p(1-p)q_{n-2}$ . la caracteristica la ecuación $r^2 = (1-p)r + p(1-p)$ tiene raíces

r_\pm = \frac{(1-p) \pm \sqrt{(1-p)^2 + 4p(1-p)}}{2},

con $\abs{r_\pm} < 1$ : efectivamente el polinomio $\chi(r) = r^2 - (1-p)r - p(1-p)$ satisface $\chi(1) = 1 - (1-p) - p(1-p) = p^2 > 0$ y $\chi(-1) = 1 + (1-p) - p(1-p) > 0$ , mientras que $\chi(0) = -p(1-p) < 0$ : una raíz en $\intoo{-1}{0}$ , una en $\intoo{0}{1}$ . Entonces $q_n = \alpha r_+^n + \beta r_-^n \to 0$ . El juego eventos “ dura más de $n$ ” disminuye a “el juego nunca termina”; monótono continuidad (Teorema 21.6) da $\P(\text{never ends}) = \lim q_n = 0$ : el juego casi termina seguramente.

Ejercicio 21.7 ★★★

(Registros) Dibuja una secuencia infinita de uniforme independiente clasificaciones, en el siguiente sentido combinatorio: para cada $n$ , el El orden relativo de los primeros sorteos $n$ es uniforme entre los $n!$ . posibilidades, y $R_n = {}$ “el sorteo $n$ es un récord (más grande que todos los anteriores)”. Admitiendo que los eventos $R_n$ son independiente con $\P(R_n) = 1/n$ (acreditar al menos este último igualdad por simetría), muestran usando Borel–Cantelli que infinitamente Muchos registros ocurren casi con seguridad, pero que los registros en consecutivo veces $n, n+1$ ocurren infinitamente con probabilidad — calcular $\sum_n \P(R_n \cap R_{n+1})$ y concluir lo que da Borel-Cantelli 1.

Solución

Solución de Ejercicio 21.7.

$\P(R_n) = 1/n$ : entre los primeros sorteos $n$ , cada uno de los $n$ posiciones relativas del último sorteo es igualmente probable (uniformidad del orden relativo), y $R_n$ es el evento que es el mayor: probabilidad $1/n$ .

Infinitos registros: $\sum_n \P(R_n) = \sum 1/n = \infty$ y $R_n$ son independiente (admitido), por lo que Borel–Cantelli 2 (Teorema 21.25) da $\P(\limsup R_n) = 1$ : los registros nunca paran, casi con seguridad — pero se adelgazan logarítmicamente.

Registros consecutivos: por independencia,

\sum_n \P(R_n \cap R_{n+1}) = \sum_n \frac{1}{n(n+1)} < \infty ,

entonces se aplica Borel–Cantelli 1: casi con seguridad, sólo un número finito times es un registro seguido inmediatamente por otro registro. los dos Las mitades del lema funcionan en conjunto: infinitos registros, pero (a.s.) eventualmente nunca dos seguidos.

Ejercicio 21.8 ★★★

(Kochen - Sabor a piedra, versión más fácil) Sea $(A_n)$ independiente eventos con $\P(A_n) = \frac{1}{n+1}$ . mostrar eso $\P(\limsup A_n) = 1$ , aunque $\P(A_n) \to 0$ : “individualmente raro, colectivamente cierto”. Por el contrario, exhibe una secuencia de (dependiente) eventos con $\sum\P(A_n) = \infty$ y $\P(\limsup A_n) = 0$ , que muestra independencia no se puede colocar Borel–Cantelli 2.

Solución

Solución de Ejercicio 21.8.

Primera parte: $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ con independencia: Borel–Cantelli 2 da $\P(\limsup A_n) = 1$ . Cada $A_n$ individual es cada vez más improbable, sin embargo, casi todos $\omega$ pertenece a una infinidad de ellos.

Counterexample without independencia: toma $\Omega = \N^*$ con los pesos $p_k = \frac{1}{k(k+1)}$ de Ejercicio 21.2 y $A_n = \{k \in \N^* : k \geq n\}$ . entonces

\P(A_n) = \sum_{k \geq n}\Bigl(\frac1k - \frac1{k+1}\Bigr) = \frac1n , \qquad \sum_n \P(A_n) = \infty ,

pero los $A_n$ están disminuyendo, por lo que $\limsup_n A_n = \bigcap_n A_n = \emptyset$ : $\P(\limsup A_n) = 0$ . Divergencia de $\sum\P(A_n)$ por sí solo no garantiza nada cuando los eventos se acumulan en un espacio cada vez más reducido. parte del espacio — independencia es lo que prohíbe eso conspiración.

Ejercicio 21.9 ★

Se lanza una moneda con probabilidad de cara $p \in \intoo01$ hasta que la primera cabeza. Calcule la probabilidad de que esto suceda en un rango impar y evaluarlo para ver si es una moneda justa.

Solución

Solución de Ejercicio 21.9.

Con $q = 1 - p$ , la primera cabeza cae en el rango $2j + 1$ con probabilidad $q^{2j}p$ , entonces

\P(\text{odd rank}) = \sum_{j\geq0}q^{2j}p = \frac{p}{1 - q^2} = \frac{1}{1 + q} .

Por una moneda justa: $\frac1{1 + 1/2} = \frac23$ . (Comprobación de cordura: los rangos impares deberían ser más probables, ya que el rango $1$ es el primero — y de hecho $\frac1{1+q} > \frac12$ siempre.)

Ejercicio 21.10 ★★

Sea $(A_n)_{n\geq1}$ eventos independientes con $\P(A_n) = p_n < 1$ . mostrar eso

\P\Bigl(\bigcap_{n\geq1}A_n^c\Bigr) = \prod_{n\geq1}(1 - p_n) := \lim_{N\to\infty}\prod_{n=1}^N(1 - p_n),

y que este límite es $> 0$ si y sólo si $\sum p_n < \infty$ . Reconciliarse con Borel–Cantelli: cuando $\sum p_n = \infty$ , no solo ocurre algo de $A_n$ casi con seguridad — infinitas personas lo hacen.

Solución

Solución de Ejercicio 21.10.

El eventos $B_N = \bigcap_{n=1}^N A_n^c$ disminuye a $\bigcap_nA_n^c$ , y por independencia de los complementos $\P(B_N) = \prod_{n=1}^N(1 - p_n)$ ; monótono continuidad (Teorema 21.6) proporciona el límite mostrado. Tomando logaritmos, $\prod(1 - p_n) > 0$ y si $\sum-\ln(1 - p_n) < \infty$ . Si $\sum p_n < \infty$ entonces $p_n \to 0$ y $-\ln(1 - p_n) \sim p_n$ : la serie logarítmica converge. si $\sum p_n = \infty$ , luego $-\ln(1 - p_n) \geq p_n$ fuerzas divergencia, por lo que el producto es $0$ . Esto coincide Borel–Cantelli 2: para $\sum p_n = \infty$ , no sólo es $\P(\text{no }A_n\text{ occurs}) = 0$ , pero casi seguro Se producen infinitos $A_n$ .

Ejercicio 21.11 ★★

(Caja de cerillas de Banach) Un fumador guarda una caja de cerillas $n$ en cada bolsillo y mete la mano en un bolsillo uniformemente aleatorio cada tiempo. Cuando encuentra por primera vez una caja vacía, ¿cuál es la probabilidad? que la otra caja contiene exactamente coincidencias $k$ ? mostrar el la respuesta es $\binom{2n-k}{n}2^{-(2n-k)}$ y verifique que estos las probabilidades suman $1$ para $n = 1$ .

Solución

Solución de Ejercicio 21.11.

Digamos que el cuadro $A$ es el primero que se descubre vacío, y el otro caja que contiene $k$ . Esto significa: entre los primeros $2n - k$ alcanza, exactamente $n$ fue a $A$ y $n - k$ a $B$ (en algunos pedido), y alcanzar el número $2n - k + 1$ fue a $A$ nuevamente, encontrándolo vacío. Los alcances son independiente elecciones justas, entonces este evento tiene probabilidad $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$ ; duplicando (el vacío cuadro puede ser cualquiera de los dos) da

\P(\text{other box has }k) = \binom{2n-k}{n}\,2^{-(2n-k)} .

Para $n = 1$ : $k = 1$ da $\binom11 2^{-1} = \frac12$ y $k = 0$ da $\binom21 2^{-2} = \frac12$ : total $1$ , como debe ser.

Ejercicio 21.12 ★★★

( $\sigma$ -la aditividad es un axioma real) (a) Demuestre que no hay ningún medida de probabilidad en $(\N, \mathcal P(\N))$ que dé a todos los singleton el mismo peso. (b) Para $A \subseteq \N^*$ , sea $d(A) = \lim_n\frac{\abs{A\cap\intint1n}}{n}$ cuando exista el límite. (el densidad natural). Mostrar $d$ es finitamente aditivo en pares donde existen las tres densidades, da cada densidad singleton $0$ y densidad $\N^*$ $1$ — y concluir que $d$ no es el aditivo $\sigma$ . (c) Exhibir un conjunto sin densidad. (Alternate blocks $\intint{2^{2k}}{2^{2k+1}-1}$ in and out.)

Solución

Solución de Ejercicio 21.12.

(a) Si $\P(\{n\}) = c$ para todos los $n$ , $\sigma$ -aditividad fuerzas $1 = \sum_nc$ : imposible, ya sea $c = 0$ (suma $0$ ) o $c > 0$ (suma infinita). No existe una probabilidad uniforme en $\N$ .

(b) Si existen $A \cap B = \emptyset$ y $d(A)$ , $d(B)$ , entonces $\abs{(A \sqcup B)\cap\intint1n} = \abs{A\cap\intint1n} + \abs{B\cap\intint1n}$ , entonces $d(A \sqcup B) = d(A) + d(B)$ : aditividad finita en tales pares. Cada singleton tiene conteo función eventualmente constante, por lo que la densidad $0$ , mientras $d(\N^*) = 1$ . Si $d$ fuera el aditivo $\sigma$ , $\N^* = \bigsqcup_k\{k\}$ daría $1 = \sum_k 0 = 0$ : la densidad es finitamente aditivo pero no $\sigma$ -aditivo — el axioma tiene contenido.

(c) Sea $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (bloques de $4^k$ a $2\cdot4^k - 1$ ). En $n = 2\cdot4^K - 1$ el recuento es $\sum_{k\leq K}4^k \sim \frac43 4^K$ , lo que da relación $\to \frac23$ ; en $n = 4^{K+1} - 1$ el conteo es sin cambios, dando la relación $\to \frac13$ . La relación oscila entre los límites $\frac13$ y $\frac23$ : sin densidad.

21.5 Problema: el paseo aleatorio simple sobre $\Z$ es recurrente

Veinticuatro pasos de un paseo aleatorio simple; el rojo los puntos marcan los retornos al origen. El problema muestra que, con probabilidad 1, estos puntos nunca dejan de aparecer — todavía el tiempo de espera entre ellos tiene media divergente. — Veinticuatro pasos de un paseo aleatorio simple; el rojo los puntos marcan los retornos al origen. El problema muestra que, con probabilidad $1$ , estos puntos nunca dejan de aparecer — todavía el tiempo de espera entre ellos tiene media divergente.

Problema 21.1

Problema del fin de semana — recurrencia de Pólya teorema de $\Z$ , con el problema de la papeleta y el arcoseno sabor en camino

Lanza una moneda justa para siempre; deje que $X_i = \pm1$ sea el paso $i$ y $S_n = X_1 + \dots + X_n$ el simple aleatorio caminar en $\Z$ , $S_0 = 0$ . Como en Ejemplo 21.26, todos los eventos siguientes están determinados por un número finito de lanzamientos o son contable combinaciones de tales eventos y independencia de eventos dependiendo de disjuntos bloques de lanzamientos es parte del modelo. Escribimos $u_n = \P(S_{2n} = 0)$ y $N_n(k)$ para el número de rutas $\pm1$ de longitud $n$ de $0$ a $k$ .

Parte I — Counting paths.

Mostrar que $N_n(k) = \binom{n}{(n+k)/2}$ cuando $n + k$ es par y $\abs k \leq n$ , y $0$ en caso contrario; deducir $\P(S_n = k) = N_n(k)\,2^{-n}$ . ¿Por qué cada ¿La ruta individual de longitud $n$ es igualmente probable?
Muestra $S_{2n+1} \neq 0$ , $u_n = \binom{2n}{n}4^{-n}$ y calcula $u_1, u_2, u_3$ .
Demuestre $u_n = \frac{2n-1}{2n}\,u_{n-1}$ ; deducir que $(u_n)$ disminuye a $0$ , y de Ejemplo 6.14 que

$u_n \sim \frac{1}{\sqrt{\pi n}}, \qquad\text{so}\qquad \sum_n u_n = \infty .$
(Principio de reflexión) Para $k \geq 1$ , demuestre que el caminos de longitud $n$ de $1$ a $k$ que tocan $0$ están en biyección con los caminos de $-1$ a $k$ ; deducir que el número de caminos de $0$ a $k$ que permanezca $> 0$ después de que el tiempo $0$ sea $N_{n-1}(k-1) - N_{n-1}(k+1)$ .
(Teorema de la papeleta) Deduce que

$\P\bigl(S_1 > 0, \dots, S_{n-1} > 0 \bigm| S_n = k\bigr) = \frac kn \qquad (k \geq 1) :$

en un conteo donde el ganador lidera por $k$ de $n$ boletas, la probabilidad de que el ganador liderara en todas partes el recuento es $k/n$ . Verifique manualmente para $n = 3$ , $k = 1$ .

Parte II — Return to the origin.

Demostrar la identidad de la clave

$\P(S_1 \neq 0,\ S_2 \neq 0,\ \dots,\ S_{2n} \neq 0) = u_n$

(condition on the first step, sum the counts of question 4 over the endpoint, and telescope; finish with $2\binom{2n-1}{n} = \binom{2n}{n}$ ).
Deducir de monótono continuidad (Teorema 21.6) que el paseo regresa a $0$ al menos una vez con probabilidad $1$ , y que $f_n := \P(\text{first return at time }2n)$ satisface

$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1}, \qquad \sum_{n\geq1}f_n = 1 .$
Demuestre que $\sum_n 2n\,f_n = \infty$ : la devolución es seguro, pero la serie que calcularía la media el tiempo de espera diverge (en el vocabulario de Capítulo 22, el tiempo de retorno tiene infinito expectativa).
Demuestre que por cada $k \geq 1$ , $\P(\text{at least } k\text{ returns to }0) = 1$ (decompose over the times of the first $k$ returns: the corresponding toss blocks are disjoint, so the probabilities multiply and sum to $(\sum_nf_n)^k$ ); concluir con monótono continuidad:

$\P(S_n = 0 \text{ for infinitely many } n) = 1 :$

el paseo aleatorio simple en $\Z$ es recurrente.
Demuestra que la caminata visita todos los sitios $k \in \Z$ casi seguramente, por lo tanto (por recurrencia, reiniciado en el primera visita) infinitamente a menudo. (The signs of the successive excursions from $0$ are independiente fair coins; a positive excursion visits $1$ .)

Parte III — Borel–Cantelli and the biased walk.

El eventos $A_n = \{S_{2n} = 0\}$ satisface $\sum\P(A_n) = \infty$ ; explica por qué Borel–Cantelli 2 no no se aplican a ellos, y lo que Borel–Cantelli 1 daría si la serie convergiera. (Este es el estrategia de toda la Parte.)
Ahora deja que la moneda tenga sesgo $p \neq \frac12$ , $q = 1 - p$ . Mostrar $\P(S_{2n} = 0) = \binom{2n}n(pq)^n = u_n\,(4pq)^n$ con $4pq < 1$ , deducir $\sum_n\P(S_{2n} = 0) < \infty$ , y concluir con Borel–Cantelli 1 que el paseo sesgado regresa a $0$ sólo un número finito de veces, casi con seguridad.
Fotograma de $p \neq \frac12$ : mostrar $\P(S_n = k) \leq \binom{n}{\floor{n/2}}\,(pq)^{n/2}\,(p/q)^{k/2}$ para cada $k$ fijo, deduzca que cada sitio es visitado finitamente a menudo casi con seguridad, y concluimos $\abs{S_n} \to \infty$ casi seguro: el paseo sesgado es transitorio.
Volviendo a la moneda justa: utilizando la pregunta 6, calcule el probabilidad de que los lanzamientos $200$ produzcan un empate no ( $S_n \neq 0$ para $1 \leq n \leq 200$ ), numéricamente $u_{100} \approx 0.056$ . Comenta sobre lo lento $1/\sqrt{\pi n}$ decadencia: los lazos son seguros a largo plazo correr pero más raro de lo que sugiere la intuición.
(Primer pasaje) Que $T_1$ sea la primera vez que caminamos. llega a $1$ . Utilizando el principio de reflexión para máximo $M_n = \max_{i\leq n}S_i$ (probado en cuestión 16, que no depende de éste), o directamente de la pregunta 7 condicionando el primer paso, mostrar $\P(T_1 = 2n - 1) = f_n$ ; deducir $\P(T_1 < \infty) = 1$ mientras la serie de tiempo medio $\sum(2n-1)f_n$ diverge.

Parte IV — Maxima, last zero, long leads.

(Reflexión para el máximo) Para $k \geq 1$ , demostrar

$\P(M_n \geq k) = 2\,\P(S_n > k) + \P(S_n = k)$

reflejando el camino tras su primera visita a nivel $k$ .
Deducir $\P(M_{2n} \geq 1) = 1 - u_n$ , es decir $\P(S_i \leq 0 \text{ for all } i \leq 2n) = u_n$ : la probabilidad de nunca estar adelante es igual a la probabilidad de nunca estar en cero (pregunta 6) — dos eventos diferentes, una probabilidad.
(Último cero) Deje $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (par). Combinando la pregunta 6 con independencia de bloques de lanzamiento desunidos, mostrar

$\P(L_{2n} = 2k) = u_k\,u_{n-k} \qquad (0 \leq k \leq n),$

y deducir, sin más cálculos, el binomio identidad $\sum_{k=0}^n u_ku_{n-k} = 1$ .
Demuestre que la ley de $L_{2n}$ es simétrico ( $\P(L = 2k) = \P(L = 2n - 2k)$ ) y, utilizando $u_j \sim 1/\sqrt{\pi j}$ , que sus extremos son los más valores probables. Tabule para $n = 5$ : $\P(L_{10} = 0) = u_5 \approx 0.246$ versus $\P(L_{10} = 4) = u_2u_3 \approx 0.117$ . Interpretar: en un juego limpio y largo, el El último empate tiende a ser muy temprano o muy tarde — Las pistas largas son la regla, no la excepción.
Reúna las preguntas 16 a 19 en un párrafo sobre imagen de fluctuación del paseo justo: la difusión escala sugerida por la pregunta 3, la certeza de retorno contra el tiempo de espera medio divergente, y la persistencia de los cables con sabor a arcoseno.

Part V — The renewal identity and Pólya’s theorem.

Demuestre, dividiendo $\{S_{2n} = 0\}$ a lo largo del tiempo de la primera devolución, el renovación de identidad

$u_n = \sum_{k=1}^n f_k\,u_{n-k} \quad (n \geq 1), \qquad\text{hence}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 \quad (0 \leq x < 1),$

donde $U(x) = \sum_{n\geq0}u_nx^n$ y $F(x) = \sum_{n\geq1}f_nx^n$ (justificar los radios y el producto de serie con Capítulo 11).
Deducir el dicotomía de recurrencia: dejando $x \to 1^-$ (límites monótonos de series con no negativos coeficientes),

$\sum_n u_n = \infty \iff \sum_n f_n = 1 ,$

y compárelo con las preguntas 3, 7 (camino justo) y 12 (paseo sesgado).
(Dimensión $2$ ) El simple paseo por $\Z^2$ requiere pasos $(\pm1, 0)$ , $(0, \pm1)$ uniformemente. Demuestre que el Las coordenadas rotadas $U_n = X_n + Y_n$ y $V_n = X_n - Y_n$ realizan paseos justos independiente en $\Z$ , deducir

$\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_n u_n^2 = \infty ,$

y concluir con las preguntas 21–22 (cuyas pruebas transferir textualmente) que el paseo por $\Z^2$ es recurrente.
(Dimensión $3$ ) Para el simple paseo por $\Z^3$ , admita la estimación local $\P(S^{(3)}_{2n} = 0) \leq C\,n^{-3/2}$ (probada con el teorema del límite local en el volumen del año 3). Deducir de Borel–Cantelli 1 que el paseo por $\Z^3$ es transitorio e indique la resultado completo: Pólya’s theorem — el sencillo paseo aleatorio es recurrente en las dimensiones $1$ y $2$ , transitorio en dimensión $3$ y superior.
Síntesis. Enumere el papel exacto desempeñado por: ruta contar y reflexionar; monótono continuidad; independencia de bloques de lanzamiento desunidos; Borel–Cantelli 1; la renovación de la identidad. cual soltero Hecho analítico ( $u_n \sim 1/\sqrt{\pi n}$ , por lo tanto $\sum u_n = \infty$ pero $\sum u_n^2 = \infty$ y $\sum n^{-3/2} < \infty$ ) decide entre recurrencia y fugacidad en cada dimensión?

Solución

Solución de Problema 21.1.

1. Un camino de longitud $n$ está determinado por el conjunto de sus avances; terminar en $k$ significa $u$ pasos ascendentes y $n - u$ pasos hacia abajo con $u - (n - u) = k$ , es decir, $u = \frac{n+k}2$ : posible si $n + k$ es par y $\abs k \leq n$ , en $\binom{n}{(n+k)/2}$ maneras. Cada camino específico es un punto de la medida justa del producto en los lanzamientos $n$ : probabilidad $2^{-n}$ . Por lo tanto $\P(S_n = k) = N_n(k)2^{-n}$ .

2. $S_n$ tiene la paridad de $n$ , por lo que $S_{2n+1} \neq 0$ ; y $u_n = N_{2n}(0)4^{-n} = \binom{2n}n4^{-n}$ . Valores: $u_1 = \frac12$ , $u_2 = \frac6{16} = \frac38$ , $u_3 = \frac{20}{64} = \frac5{16}$ .

3. $\dfrac{u_n}{u_{n-1}} = \dfrac{\binom{2n}n}{4\binom{2n-2}{n-1}} = \dfrac{(2n)(2n-1)}{4n^2} = \dfrac{2n-1}{2n} < 1$ : decreciente. Por Ejemplo 6.14, $\binom{2n}n \sim \frac{4^n}{\sqrt{\pi n}}$ , por lo que $u_n \sim \frac1{\sqrt{\pi n}} \to 0$ y $\sum u_n$ divergen en comparación con $\sum n^{-1/2}$ .

4. Dada una ruta desde $1$ a $k$ tocando $0$ , reflejar su segmento inicial (hasta la visita primero a $0$ ) a través del eje horizontal: el resultado es un camino desde $-1$ a $k$ , y la operación es una involución — cada La ruta de $-1$ a $k \geq 1$ debe cruzar $0$ y reflejar su segmento inicial recupera el original. De ahí el tocando los caminos número $N_{n-1}(k + 1)$ (de $-1$ a $k$ el el desplazamiento es $k + 1$ ). Un camino de $0$ a $k$ quedando $> 0$ después del tiempo $0$ comienza con un paso hacia arriba y luego va desde $1$ a $k$ en pasos $n - 1$ sin tocar $0$ : hay $N_{n-1}(k-1) - N_{n-1}(k+1)$ de ellos.

5. Con $m = \frac{n+k}2$ , usando $\binom{n-1}{m-1} = \frac mn\binom nm$ y $\binom{n-1}{m} = \frac{n-m}n\binom nm$ :

\frac{N_{n-1}(k-1) - N_{n-1}(k+1)}{N_n(k)} = \frac{\binom{n-1}{m-1} - \binom{n-1}{m}}{\binom nm} = \frac{m - (n - m)}{n} = \frac kn .

Para $n = 3$ , $k = 1$ : rutas $N_3(1) = 3$ ( $++-$ , $+-+$ , $-++$ ), de los cuales sólo $++-$ permanece positivo ( $+-+$ vuelve a $0$ en el momento $2$ ): uno de cada tres, y $\frac kn = \frac13$ .

6. Por simetría la probabilidad es $2\P(S_i > 0\ \forall i \leq 2n)$ . Sumando el punto final $2k$ y usando pregunta 4 (con $n$ reemplazado por $2n$ ):

\P(S_i > 0\ \forall i) = 2^{-2n}\sum_{k\geq1} \bigl(N_{2n-1}(2k-1) - N_{2n-1}(2k+1)\bigr) = 2^{-2n}\,N_{2n-1}(1),

una suma telescópica. Ahora $N_{2n-1}(1) = \binom{2n-1}{n}$ y $2\binom{2n-1}n = \binom{2n}n$ (Pascal), por lo que se muestra la probabilidad es $2\cdot2^{-2n}\binom{2n-1}n = \binom{2n}n4^{-n} = u_n$ .

7. El eventos $D_n = \{S_i \neq 0,\ i \leq 2n\}$ disminución, con intersección “sin retorno jamás”; por monótono continuidad y pregunta 6, $\P(\text{no return}) = \lim u_n = 0$ : la caminata regresa casi con seguridad. Además $f_n = \P(D_{n-1}) - \P(D_n) = u_{n-1} - u_n$ , y por pregunta 3

u_{n-1} - u_n = u_n\Bigl(\frac{2n}{2n-1} - 1\Bigr) = \frac{u_n}{2n-1}; \qquad \sum_{n\geq1}f_n = u_0 - \lim u_n = 1 .

8. $2n\,f_n = \frac{2n}{2n-1}u_n \geq u_n$ , y $\sum u_n = \infty$ (pregunta 3): la serie $\sum 2nf_n$ diverge. El primer retorno es seguro pero no tiene media finita. tiempo de espera — la caminata es nulo recurrente, en el vocabulario que Capítulo 22 le proporcionará.

9. El evento “al menos $k$ devuelve” es el unión disjunta contable, sobre $0 < n_1 < \dots < n_k$ , de el eventos “las primeras devoluciones $k$ ocurren exactamente a veces $2n_1, \dots, 2n_k$ ”. Tal evento es la intersección de $k$ eventos dependiendo de los bloques de lanzamiento desunidos $\intint1{2n_1}$ , $\intint{2n_1+1}{2n_2}$ , …, cada bloque requiriendo una nueva caminata para hacer su primer regreso después exactamente el número de pasos asignado; por independencia del bloquea su probabilidad es $f_{n_1}f_{n_2-n_1}\cdots f_{n_k-n_{k-1}}$ . Suma por paquetes (Capítulo 7, todos los términos no negativos):

\P(\text{at least }k\text{ returns}) = \Bigl(\sum_{n\geq1}f_n\Bigr)^{\!k} = 1^k = 1 .

El eventos disminuye en $k$ , por lo que es monótono continuidad. $\P(\text{infinitely many returns}) = 1$ : recurrencia.

10. Por la pregunta 9 el paseo hace infinitos excursiones fuera de $0$ . El primer paso de cada excursión es una moneda nueva, independiente de todo lo anterior: la probabilidad de que las primeras excursiones $m$ comiencen todas hacia abajo es $2^{-m}$ . Para llegar a $1$ la caminata solo necesita una subida inicio de excursión (desde $<0$ debe pasar por $0$ antes llegando a $1$ , siendo los pasos $\pm1$ ), entonces $\P(\text{never hit }1) \leq 2^{-m}$ por cada $m$ : la caminata llega a $1$ casi con seguridad. Descomponiendo el tiempo de golpe (casi seguramente finito), el caminata reiniciada hay una nueva caminata iniciada en $1$ : por inducción llega a cada $k \geq 1$ casi con seguridad, y por simetría cada $k \leq -1$ . Finalmente, reiniciando en la primera visita a $k$ , la pregunta 9 se aplica al paseo fresco: cada El sitio es visitado infinitamente a menudo, casi con seguridad.

11. Los eventos $A_n = \{S_{2n} = 0\}$ están lejos de independiente (estar en $0$ en el momento $2n$ hace que estar en $0$ en tiempo $2n + 2$ mucho más probable que $u_{n+1}$ ), por lo que Borel–Cantelli 2 no está disponible y, de hecho, toda la obra de la Parte II debía sustituirlo. La otra dirección no necesita independencia: if $\sum\P(A_n)$ converge, Borel–Cantelli 1 produce un número finito de rendimientos casi con seguridad. Esa implicación es el motor de toda prueba de fugacidad. abajo.

12. Una devolución en el momento $2n$ requiere $n$ up- y $n$ pasos descendentes: $\P(S_{2n} = 0) = \binom{2n}np^nq^n = u_n(4pq)^n$ y $4pq = 1 - (p - q)^2 < 1$ para $p \neq \frac12$ . Desde $u_n \leq 1$ , la serie $\sum\P(S_{2n} = 0)$ Está dominado por el geométrico $\sum(4pq)^n$ : convergente. Por Borel–Cantelli 1, $\P(S_{2n} = 0 \text{ infinitely often}) = 0$ : un número finito de retornos, casi con seguridad.

13. Para $n + k$ incluso, $\P(S_n = k) = \binom{n}{\frac{n+k}2}p^{\frac{n+k}2}q^{\frac{n-k}2}$ ; el el coeficiente binomial es como máximo el central, y $p^{\frac{n+k}2}q^{\frac{n-k}2} = (pq)^{n/2}(p/q)^{k/2}$ , dando el límite indicado $\leq 2^n(pq)^{n/2}(p/q)^{k/2} = (4pq)^{n/2}(p/q)^{k/2}$ , sumable en $n$ desde $\sqrt{4pq} < 1$ . Borel–Cantelli 1: el sitio $k$ es visitado con una frecuencia finita, casi con seguridad; la unión sobre $k \in \Z$ del excepcional nulo eventos sigue siendo nula (contable subaditividad). Es casi seguro que todos los sitios se visitan de forma limitada. a menudo, por lo que la secuencia entera $(S_n)$ deja cada acotado ventana para siempre: $\abs{S_n} \to \infty$ .

14. $\P(S_n \neq 0,\ 1 \leq n \leq 200) = u_{100} = \binom{200}{100}4^{-100} \approx \frac1{\sqrt{100\pi}} \approx 0.056$ : más de una probabilidad entre veinte de que $200$ los lanzamientos justos nunca empatan. La decadencia $1/\sqrt{\pi n}$ es terriblemente lento: la certeza de un empate (pregunta 7) es compatible con tramos muy largos sin ataduras — una primera sabor de los fenómenos arcoseno de la Parte IV.

15. Condición en el primer paso. Si $X_1 = +1$ entonces Coincidencias $T_1 = 1$ y $f_1 = \frac12$ . Si $X_1 = -1$ , el el paseo debe subir desde $-1$ hasta $1$ ; por la descomposición del bloque, volviendo a $0$ por primera vez en el momento $2n$ se divide como: un paso hacia abajo, luego comenzó una nueva caminata en $-1$ primero llegando a $0$ — equivalente a una nueva caminata primero llegando $+1$ — en pasos $2n - 1$ , o el evento simétrico hacia arriba. Ambos signos contribuyen por igual:

f_n = 2\cdot\tfrac12\,\P(T_1 = 2n - 1) = \P(T_1 = 2n-1) .

De ahí $\P(T_1 < \infty) = \sum f_n = 1$ , mientras que $\sum_n(2n - 1)f_n = \sum_n u_n = \infty$ por la pregunta 7: la caminata llega $1$ casi con toda seguridad, en un tiempo medio infinito.

16. Partición $\{M_n \geq k\}$ por el valor del terminal $S_n = m$ . Para $m \geq k$ la condición $M_n \geq k$ es automático. Para $m < k$ , refleje la ruta después de su primero visita al nivel $k$ : esta es una biyección entre $\{M_n \geq k, S_n = m\}$ y $\{S_n = 2k - m\}$ (cada ruta terminando en $2k - m > k$ visitas $k$ ; Reflejar hacia atrás es el inversa). Por lo tanto

\P(M_n \geq k) = \sum_{m > k}\P(S_n = m) + \P(S_n = k) + \sum_{m < k}\P(S_n = 2k - m) = 2\P(S_n > k) + \P(S_n = k).

17. En tiempo par $2n$ con $k = 1$ : $\P(S_{2n} = 1) = 0$ y $\P(S_{2n} > 1) = \P(S_{2n} \geq 2)$ , por lo que

\P(M_{2n} \geq 1) = 2\P(S_{2n} \geq 2) = \P(S_{2n} \geq 2) + \P(S_{2n} \leq -2) = 1 - u_n .

Así $\P(S_i \leq 0\ \forall i \leq 2n) = u_n$ : el paseo nunca conduce en los primeros pasos $2n$ exactamente con tanta frecuencia como nunca empata (pregunta 6) — dos eventos bastante diferentes, llevado por el mismo $u_n$ .

18. $\{L_{2n} = 2k\} = \{S_{2k} = 0\} \cap \{\text{the walk of the tosses } 2k+1, \dots, 2n \text{ has no zero}\}$ . Los dos eventos dependen de bloques de lanzamiento separados, entonces son independiente; el primero tiene probabilidad $u_k$ , el segundo $u_{n-k}$ por la pregunta 6 aplicada al fresco $(2n-2k)$ caminata de pasos. Por lo tanto $\P(L_{2n} = 2k) = u_ku_{n-k}$ . Dado que $L_{2n}$ toma exactamente los valores $0, 2, \dots, 2n$ , estas probabilidades suman $1$ : $\sum_{k=0}^nu_ku_{n-k} = 1$ , una identidad binomial entregada por una partición probabilística.

19. La simetría es inmediata: $u_ku_{n-k} = u_{n-k}u_k$ . A medida que $u_j$ disminuye en $j$ , el producto $u_ku_{n-k}$ es el más pequeño para $k$ central y el más grande en el extremos $k \in \{0, n\}$ , donde es igual a $u_n$ ; cuantitativamente $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ en masa, contra $u_n \approx \frac1{\sqrt{\pi n}}$ en los bordes. Para $n = 5$ : $\P(L_{10} = 0) = \P(L_{10} = 10) = u_5 = \frac{63}{256} \approx 0.246$ , mientras que $\P(L_{10} = 4) = u_2u_3 = \frac38\cdot\frac5{16} = \frac{15}{128} \approx 0.117$ . En un juego limpio y largo, el último empate es más probablemente cerca del principio o del final: un jugador normalmente conduce por tramos enormes, sin sesgo en el moneda.

20. La imagen: en el momento $n$ el paseo vive a escala $\sqrt n$ (la extensión binomial de la pregunta 3 — $u_n \sim 1/\sqrt{\pi n}$ es la altura del pico central); eso regresa a $0$ infinitamente a menudo con probabilidad $1$ (Parte II), sin embargo, el tiempo de espera entre devoluciones tiene medias divergentes (pregunta 8), por lo que las excursiones individuales pueden ocupar un fracción positiva de cualquier horizonte; correspondientemente el último El empate de un juego de pasos $2n$ se distribuye con valores extremos. lo más probable (preguntas 18 y 19), y nunca liderar tiene la misma probabilidad que decae lentamente $u_n$ que nunca atar (pregunta 17). Certeza en el límite, perseverancia en cada horizonte finito: ese es el camino justo.

21. Partición $\{S_{2n} = 0\}$ ( $n \geq 1$ ) por el primer tiempo de retorno $2k$ , $1 \leq k \leq n$ : el primer bloque de Los lanzamientos $2k$ realizan una primera devolución, los restantes $2n - 2k$ Los lanzamientos logran el regreso de una nueva caminata, y los bloques son independiente: $u_n = \sum_{k=1}^nf_ku_{n-k}$ . Ambas series $U(x) = \sum u_nx^n$ , $F(x) = \sum f_nx^n$ tienen radio $\geq 1$ (coeficientes en $\intcc01$ ) y producto cauchy (Capítulo 11) da, para $0 \leq x < 1$ ,

U(x) - 1 = \sum_{n\geq1}\Bigl(\sum_{k=1}^n f_ku_{n-k}\Bigr)x^n = F(x)\,U(x), \qquad\text{i.e.}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 .

22. A medida que aumentan $x \uparrow 1$ , $U(x)$ y $F(x)$ (coeficientes no negativos); cada suma parcial $\sum_{n\leq N}u_n$ es un límite de $\sum_{n\leq N}u_nx^n \leq U(x)$ , por lo que $U(x) \uparrow \sum u_n \in \intoc0{+\infty}$ , y asimismo $F(x) \uparrow f = \sum f_n$ . Si $\sum u_n = \infty$ : $1 - F(x) = 1/U(x) \to 0$ , entonces $f = 1$ . Si $\sum u_n = S < \infty$ : $1 - f = 1/S > 0$ , entonces $f < 1$ . Verificaciones: paseo justo, $\sum u_n = \infty$ y $f = 1$ (preguntas 3, 7); caminata sesgada, $\sum u_n(4pq)^n < \infty$ y correspondientemente $f = 1 - 1/\sum_{n\geq0}u_n(4pq)^n < 1$ , consistente con el finitud casi segura del número de rendimientos (pregunta 12).

23. Para los cuatro pasos $(\pm1, 0), (0, \pm1)$ del Caminata $\Z^2$ , los incrementos de $U = X + Y$ y $V = X - Y$ son: $(+,+)$ para $(1,0)$ , $(+,-)$ para $(0,1)$ , $(-,+)$ para $(0,-1)$ , $(-,-)$ para $(-1,0)$ — cada par de signos con probabilidad $\frac14 = \frac12\cdot\frac12$ : los dos Los paseos coordinados $(U_n)$ y $(V_n)$ son justos independiente. camina por $\Z$ . Desde $S^{(2)}_{2n} = (0,0)$ y si $U_{2n} = 0$ y $V_{2n} = 0$ ,

\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_nu_n^2 = \infty .

La identidad renovadora de la pregunta 21 y la dicotomía de La pregunta 22 no utilizó nada unidimensional (sólo el descomposición sobre el primer retorno y bloque disjunto independencia), por lo que $\sum u_n^{(2)} = \infty$ da $f^{(2)} = 1$ , y el argumento de la pregunta 9 lo actualiza: el camino sigue $\Z^2$ vuelve al origen infinitas veces casi con seguridad.

24. Con el límite admitido $\P(S^{(3)}_{2n} = 0) \leq Cn^{-3/2}$ , la serie converge y Borel–Cantelli 1 da un número finito de retornos casi con seguridad: el caminar sobre $\Z^3$ es transitorio (y el mismo límite con el exponente $-d/2$ maneja cada $d \geq 3$ ). En total: Pólya’s theorem — el paseo aleatorio simple es recurrente en $\Z$ y $\Z^2$ , transitorio en $\Z^d$ para $d \geq 3$ . Un borracho encuentra su camino a casa; un pájaro borracho puede que no.

25. El conteo de rutas y la reflexión produjeron el resultado exacto. leyes ( $u_n$ , el teorema de la papeleta, $f_n$ , el máximo, el último cero); monótono continuidad convirtió cada límite declaración (“devuelve al menos una vez”, “infinitamente frecuente”) en un límite de probabilidades de horizonte finito; bloque disjunto independencia impulsó la renovación descomposiciones (preguntas 9, 18, 21) — es el contable esqueleto de la propiedad de Markov; Borel–Cantelli 1 fue el arma de fugacidad (preguntas 12–13, 24), que no necesita independencia; La identidad renovadora organizó todo en la dicotomía $\sum u_n = \infty \iff$ recurrencia. el soltero La entrada analítico es la estimación local $u_n \sim 1/\sqrt{\pi n}$ : su cuadrado $1/(\pi n)$ aún diverge (dimensión $2$ , recurrente), mientras que $n^{-3/2}$ converge (dimensión $3$ , transitorio) — El teorema de Pólya es, al final, una declaración sobre la divergencia de $\sum n^{-d/2}$ .

21.1 Espacios de probabilidad

21.2 Condicionamiento e independencia

21.3 El lema de Borel-Cantelli

21.4 Ceremonias

21.5 Problema: el paseo aleatorio simple sobre Z\ZZ es recurrente

21.5 Problema: el paseo aleatorio simple sobre $\Z$ es recurrente