Una torcedura en un problema de escuela secundaria clásica

Question

$$\text{"Toss a fair coin, if heads: stop; if tails: toss again."}$$

No especialmente divertido juego, pero un clásico de la probabilidad de ejercicio, sin embargo; la probabilidad de que este proceso final es fácilmente demostrado ser $1:$

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots =1$$

Esto me hizo preguntarme, ¿qué sucede si en lugar de los dos resultados, tenemos tres? En mejores términos, supongamos que tenemos de generar de forma aleatoria un número de $\{0,1,2\}$ (cada uno elija, es equiprobables); si $0:$ de paro, si $1:$ elegir nuevamente, si $2:$ elegir dos veces $($incluso si la primera selección es $0)$. En el último caso, la suma de los resultados de ambas selecciones, que nos da el número de hilos necesarios para la siguiente ronda. Aquí está un ejemplo de un juego:

$$\text{start}\to(1)\to(2)\to (1,2)\to (0,2,1)\to (0,1,0)\to (0)\to\text{end}$$

(los números entre paréntesis representan los resultados de cada recogida)

De nuevo, la probabilidad de que este proceso va a terminar es $1$ (justificación de abajo). Después de descubrir esto, yo estaba un poco desconcertado. Seguramente, esta probabilidad no puede ser $1$ si el número de resultados posibles es lo suficientemente grande?

Resulta que falla para dar a $1$ en el próximo número entero. De hecho, si queremos generar aleatoriamente de $\{0,1,2,3\}$, las mismas reglas que el anterior, con el añadido de la "si $3:$ elegir tres veces", la probabilidad de que el proceso final se inclina a $\sqrt{2}-1$.

$$\star$$

Yo estaba interesado en encontrar una expresión que nos da esta probabilidad en términos de la mayor entero en el conjunto inicial (sólo mirar los conjuntos de la forma $\{0,1,\cdots \,n\}$ por ahora); creo que he encontrado un polinomio cuyas soluciones de la probabilidad. Hay varias cuestiones que no he podido resolver:

• el mencionado polinomio tiene dos raíces en $[0,1]$: una es $1$ (cuando el conjunto se $\{0,1\}$ (sorteo caso) o $\{0,1,2\}$, las raíces no son distintas). Estoy casi seguro de que la probabilidad deseada es la más baja de la raíz. Sin embargo, no he encontrado una manera decente de apoyar esta afirmación.
• Me gustaría algunas críticas sobre mi trabajo; yo nunca he estudiado la licenciatura de matemáticas, y menos aún participado en un curso de probabilidad, por lo que bien puede haber abusado de algunos de notación y de hecho algunos supuestos que no debería ser permitido hacer. Siéntase libre de critise lo que usted siente es necesario!

$$\textbf{Problem}$$

Deje $\Omega$ ser un conjunto de $\alpha\geq 2$ enteros consecutivos con el elemento más pequeño $0:\;\Omega=\{0,1,\cdots\,\alpha-1\}$

Proceso:

Al azar e independientemente de generar elementos de $\Omega$ $r_n$ veces. Si la suma de los resultados es $r_{n+1}=0$ termina el proceso. Si la suma de los resultados es $r_{n+1}\geq 1$, al azar e independientemente de generar elementos de $\Omega\;r_{n+1}$ tiempos, etc. El proceso comienza con $r_1=1$.

¿Cuál es la probabilidad de que este proceso termina?

$$\textbf{Attempted solution}$$

$\phi:$ final del proceso , $r_n:$ número de selecciones requeridas en la etapa de $n$

Observe que para $n>1:$

$$ \left\{ \begin{array}{l l} p(\phi|r_n=0)=0 &\\ p(\phi|r_n=1)=p(\phi|r_1)=p(\phi) & \; (r_n=1\;\text{returns us to the initial conditions}) \end{array} \right.$$

Para $r_n\geq 1$ caso $(\phi|r_n)$ es equivalente a:

$$\left(\bigcap_{k=1}^{r_n}\phi|i_k\right)$$

donde $(i_k)$ requiere de un único e independiente de pick es decir $(i_k)\Leftrightarrow (r_1)$

Por lo tanto, podemos escribir para $n>1,r_n\geq 1:$

$$p(\phi|r_n)=p\left(\bigcap_{k=1}^{r_n}\phi|i_k\right)=\prod_{k=1}^{r_n}p(\phi|i_k)=p(\phi|r_1)^{r_n}=p(\phi)^{r_n}$$

Además, dado que todos los resultados son equipossible, $p(r_n=k\in\Omega)=\dfrac{1}{\alpha}$

La ley de total probabilidad se obtiene:

$$\begin{align*}p(\phi)&=p(\phi|r_n=1)\\&=\sum_{k=0}^{\alpha-1}p(r_{n+1}=k)p(\phi|r_{n+1}=k)\\&=\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}p(\phi|r_{n+1}=k)\\&=\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}p(\phi)^k\end{align*}$$

Para mayor claridad, denotan $\lambda$ la probabilidad deseada $p(\phi)$. Estamos izquierda a resolver:

$$\lambda =\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}\lambda^k\Rightarrow\alpha\lambda =\sum_{k=0}^{\alpha-1}\lambda^k$$ $$\Rightarrow\lambda^{\alpha}-\alpha\lambda^2+\alpha\lambda-1 =0$$

Observe que para $\alpha=2$ esto se reduce a $(\lambda-1)^2=0\Rightarrow \lambda=1$ que está de acuerdo con el sorteo escenario, y $\alpha=3$ da $(\lambda-1)^3=0\Rightarrow\lambda=1$ cual es la razón de mi inicial giro en el problema también tiene probabilidad de $1$.

Por Descartes' regla de los signos de este polinomio tiene exactamente tres raíces positivas. Es fácil mostrar que la estas raíces se encuentran en la $[0,1]$. De hecho, dos de ellos se $1$, y el otro es $<1$ al $\alpha\geq 4$. Por esta razón, para $\alpha=4$, creo que la probabilidad es de los más bajos de la solución:

$$(\lambda-1)^2(\lambda^2+2\lambda-1)=0\Rightarrow\lambda=\sqrt{2}-1\;\;\text{if}\;\;\lambda\neq 1$$

Podemos observar que esta otra solución enfoques $0$ al $\alpha\to\infty$ que está de acuerdo con la intuición. Si lo que he hecho hasta ahora es correcto, y mi intuición es correcta, ¿cómo puedo justificar que la solución es la más pequeña solución positiva a las $\lambda^{\alpha}-\alpha\lambda^2+\alpha\lambda-1 =0?$

$$\star$$

Muchas gracias a cualquiera que poner el esfuerzo en la lectura de este medio. Si los que responden desea incluir cualquier teoría de la probabilidad que está más allá de las herramientas básicas que he utilizado, estaría muy agradecida de que se podría explícitamente el nombre de las herramientas que utilice, de manera que puedo estudiar para comprender plenamente sus respuestas.

Answer 1

Yo voy a darles un enfoque diferente para la obtención de la misma ecuación polinomial, entonces será fácil ver por qué la probabilidad debe ser el menor de la raíz al $\alpha \geq 4$.

Deje $s_n$ ser la variable aleatoria que representa la suma de todos los "picks" en la etapa de $n$ $n \geq 0$ ( $n=0$ , la tratamos como $s_0$ siempre $1$, ya que tenemos 1 recogida en la etapa 1. En comparación a su enfoque, $s_n=r_{n+1}$) se examina la probabilidad de generación de función $f_n(x)=E(x^{s_n})$.

Desde $s_0$ siempre $1$, por definición, $f_0(x)=E(x^{s_0})=x$.

Tenga en cuenta que si dejamos $X$ ser la variable aleatoria que representa el 1 pick, a continuación, $s_{n+1}$ es la suma de $s_n$ copias idénticas de $X$. Por lo tanto $E(x^{s_{n+1}}|s_n=k)=\left(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}\right)^k$, por lo que por la ley de la total expectativa, $f_{n+1}(x)=E(x^{s_{n+1}})=E(E(x^{s_{n+1}}|s_n=k))=E(\left(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}\right)^{s_n})=f_n(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha})$.

Deje $P(x)=\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}$, entonces tenemos que la inducción por $f_n(x)=P^n(x)$ donde $P^n(x)$ indica el $n^{\text{th}}$ itera $P(x)$. Ahora $P(s_n=0)=f_n(0)=P^n(0)$.

La ecuación de $P(x)=x$ tiene exactamente 2 raíces, una raíz en $x=1$, y una pequeña raíz de $0<x=c<1$. ( Para ver esto, observe que Descartes' regla de los signos da en la mayoría de los 2 raíces, a continuación, $x=1$ es una raíz, y $P'(x)>1$ $x=1- \epsilon$ para las pequeñas suficiente $\epsilon>0$, por lo que el$P(a)<0$$1-\epsilon<a<1$, e $P(0)>0$, por lo que por medio del teorema del valor, ya que $P(x)$ es continua, tiene una raíz entre $0$ $1$.)

Desde $P(0)=\frac{1}{\alpha}>0, P(c)=c$, $P(x) \not =x$ para $0<x<c$, e $P(x)$ es continua y estrictamente creciente en función de $0 \leq x$,$x<P(x)<c$$0 \leq x<c$.

Nota:$P^0(0)=0<c$, así que por inducción podemos mostrar a $P^n(x)<c$, y por lo tanto $P^n(x)<P^{n+1}(x)$, por lo que la secuencia de $P_n(x)$ es estrictamente creciente y acotada desde arriba por $c$, y por lo tanto tiene un límite $0<p\leq c$. $p$ también debe ser una raíz de $P(x)=x$, lo $p=c$.

Tenemos $c=\lim_{n \to \infty}{P^n(0)}=\lim_{n \to \infty}{P(s_n=0)}=P(\phi)$ donde $P(\phi)$ es la probabilidad de terminar, de acuerdo a su notación.