Posibles Duplicados:
La probabilidad de un aleatorias de cadena que contiene una larga lista de 1s?EDIT: Cocopuffs a continuación parcialmente ha respondido a la pregunta, pero la crítica del caso base $L=2$ a su argumento inductivo es falta y no es obvio cómo llenar el vacío.
Este problema original se describe en este hilo en community.wizards.com.
Se originó como una pregunta acerca de una de Magic: the Gathering escenario, pero he de decir que aquí en la audiencia general de los términos.
Supongamos que tienes \$0, and your friend has \$L. de empezar a tirar monedas. Cada vez que voltear cabezas, usted gana \$2 and your friend wins \$1. Cada vez que usted tira de las colas, usted perderá todo su dinero. ¿Cuál es la probabilidad de que finalmente se tiene (al menos) tanto dinero como su amigo?
Como se indica en el hilo anterior, la probabilidad de $p(L)$ de que finalmente la coincidencia de que su amigo está dada por la relación de recurrencia
$$p(L) = \frac{1}{2^{L-1}} + \sum_{i=1}^{L-1} \frac{p(L+i)}{2^i}.$$
Distinta de la trivial observación de que $p(L) = 1$ es una solución para esta recurrencia, no he sido capaz de avanzar. ¿Cómo puedo probar esta solución es única (y por lo tanto de la derecha)?
Respuestas
¿Demasiados anuncios?
Edit: Este es mi (incorrecto) intento de solución. La inducción de paso no es válido en $L=2$.
Claramente $p(0) = 1$.
El uso de la inducción en $L$ y asumir que $p(0),...,p(L-1) = 1$.
Caso 1: $L$ es impar, $L = 2m-1.$ $$1 = p(m) = \frac{1}{2^{m-1}} + \sum_{i=1}^{m-1} \frac{p(m+i)}{2^i} = \frac{p(L)}{2^{m-1}} + \frac{1}{2^{m-1}} + \underbrace{\sum_{i=1}^{m-2} \frac{1}{2^i}}_{1 - 2^{2-m}}$$ and $p(L) = 1$ de la siguiente manera después de multiplicar a través de.
Caso 2: $L = 2m-2$ es incluso. Entonces $$1 = p(m) = \frac{1}{2^{m-1}} + \sum_{i=1}^{m-1} \frac{p(m+i)}{2^i} = \frac{p(L)}{2^{m-2}} + \frac{p(L+1)}{2^{m-1}} + \frac{1}{2^{m-1}} + (1 - 2^{3-m})$$ and so $$2p(L) + p(L+1) = 3.$$ On the other hand, the inequalities $0 \le p(L) p(L+1) \le 1$ imply immediately $p(L) = 1$.
Definir $Q(L) = P(L)/2^{L+1}$, de modo que su relación de recurrencia es : $Q(L) = 4^{-L} + \sum_{i=1}^{L-1} Q(L+i)$.
Entonces usted consigue $Q(L+1) - Q(L) = (1-4).4^{-L-1} + Q(2L) + Q(2L+1) - Q(L+1)$, lo $2Q(L+1) - Q(L) = -3.4^{-L-1} + Q(2L) + Q(2L+1)$. Junto con $Q(2) = 4^{-2} + Q(3)$, tenemos un sistema equivalente.
El espacio de soluciones del sistema de ecuaciones es un verdadero espacio afín de dimensión infinita : usted puede simplemente elegir arbitrariamente los valores de cada $Q(2L)$, después de deducir los valores de las $Q(2L+1)$. Sin embargo no hay muchas soluciones con $Q(L) \in [0 ; 2^{-L-1}]$, y usted está buscando para los más pequeños :
suponiendo que tienes una solución positiva, $Q(2) = 4^{-2} + P(3) \\ = 4^{-2} + 4^{-3} + P(4) + P(5) \\ = 4^{-2} + 4^{-3} + 4^{-4} + 2Q(5) + P(6) + P(7) \\ \ldots \\ \ge 4^{-2} + 4^{-3} + 4^{-4} + 2.4^{-5} + 3.4^{-6} + 6.4^{-7} + 11.4^{-8} + 22.4^{-9} + 42.4^{-10} + \ldots \\ = \sum a_2(n)4^{-n} = Q_0(2)$
Podemos hacer lo mismo para mayor $L$ y definir una serie de $Q_0(L) = \sum a_L(n)4^{-n}$. Ya tenemos una solución positiva $Q_1(L) = 2^{-1-L}$, los que la serie converge y $0 < Q_0(L) \le Q_1(L)$. La secuencia de $Q_0(L)$ es una solución del sistema de ecuaciones, y de hecho, es estrictamente menor que la solución trivial $Q_1(L)$
Después de observar que los coeficientes de no crecer demasiado rápido, nos puede dar una mejor obligado para $Q_0(L)$ : por cada $L$ tenemos para $n$ lo suficientemente grande como $a_L(2n+1) = 2a_L(2n)$$a_L(2n) = 2a_L(2n-1)-a_L(n) < 2a_L(2n-1)$. Por ejemplo, con $L=2$, $Q_0(2) < 4^{-2} + 4^{-3} + 4^{-4} + 2.4^{-5} + 4.4^{-6} + 8.4^{-7} \ldots = 11.2^{-7} < 2^{-3} = Q_1(2)$, y por lo tanto $P_0(2) < 11/16$
Para que vea que usted está, de hecho, buscando $P_0$, usted sólo tiene que comprobar que la probabilidad de obtener tanto dinero como su amigo es el límite de $n \mapsto \infty$ de la probabilidad de hacerlo en menos de $n$ lanza, que da se eleva a la esencia de la misma serie.
El problema de dar una forma cerrada de expresión para $P_0(2)$ y los otros $P_0(L)$ aún no está resuelto.
Para agregar a mjqxxxx la respuesta:
La probabilidad de falla $P_f(L)=P(X_1<L ; X_2<L+X_1;X_3<L+X_1+X_2; \dots)$ puede ser limitada por el otro lado por
$$P_f(L) \le P(X_1<L) \, P(X_2<L + X_1 ) \, P(X_3<L + X_1+X_2 ) \cdots $$
(el signo de la desigualdad proviene de la observación de que si se para añadir el encadenado acondicionado obtener el exacto probabilidades, cada probabilidad disminuiría). Pero
$$P(X_n < L + X_1 + X_2 + \cdots + X_{n-1})=\\ = \sum_{X_1=1}^\infty 2^{-X_{1}} \sum_{X_2=1}^\infty 2^{-X_{2}} \cdots \ \sum_{X_{n-1}=1}^\infty 2^{-X_{n-1}}\sum_{X_{n}=1}^{L+X_1+\cdots X_{n-1}-1} 2^{-X_n}=\\ = 1 - 2^{-L+1} (1/3)^{n-1}$$
Por lo tanto
$$P_f(L) \le \prod_{k=0}^{\infty } \left(1- 2^{-L+1} (1/3)^{n}\right)=(a;q)_{\infty}$$
donde $(a;q)_{\infty}$ es el q-símbolo de Pochhammer, con $a=2^{-L+1}$, $q=1/3$
Algunos de los valores de $P_f(2) \le 0.3826$ , $P_f(3) \le 0.659$, $P_f(4) \le 0.82116$ En particular, la probabilidad de éxito de $L=2$ es mayor que $0.61740$ (y, según mjqxxxx la respuesta de menos de $0.66666$)
La solución no es la correcta; de hecho, usted tiene una probabilidad muy pequeña de que nunca la captura de su amigo como $L$ se hace más grande.
Deje $X_{i}$ $i=1,2,3,\ldots$ ser yo.yo.d. discretas variables aleatorias que representan las longitudes de su no-cero carreras de la cabeza. (Tenga en cuenta que hay una.s. infinitamente muchas de estas pistas.) La distribución de probabilidad de cada variable es $P[X=k]=2^{-k}$$k\ge 1$. Por lo $P[X \ge k]=2^{1-k},$$P[X<k]=1-2^{1-k}$. Después de su $n$-th no-cero de ejecución de cabezas, ha $2X_n$ y su amigo ha $L+\sum_{i=1}^{n}X_{i}$; usted tiene tanto dinero como tu amigo si $$ X_{n}\ge L + \sum_{i=1}^{n-1}X_{i}, $$ lo que implica que $X_{n} \ge L + (n-1)$. Es decir, cada vez que voltear al menos una cabeza y no coger tu amigo, tu amigo tiene al menos un dólar más para usted para que coincida con la siguiente vez. Por lo tanto, la probabilidad de éxito es en la mayoría de los $$ P[X \ge L] + P[X < L]P[X \ge L+1]+P[X<L]^2P[X\ge L+2] + ...,$$ que es $$ P[X\ge L]\left(1 + \frac{1}{2}P[X<L]+\frac{1}{4}P[X<L]^2+...\right)=\frac{P[X\ge L]}{1-\frac{1}{2}P[X<L]}=\frac{2^{1-L}}{\frac{1}{2}+\frac{1}{2}2^{1-L}}=\frac{2^{2-L}}{1+2^{1-L}}. $$ Para $L=0$ o $L=1$, la probabilidad de éxito es, obviamente,$1$. El de arriba enlazado muestra que la probabilidad de éxito de $L=2$ es en la mayoría de las $2/3$, y disminuye exponencialmente con la $L$.
