Promedio de tiradas

El problema de la semana es el siguiente:

Calcular el número esperado de lanzamientos de una moneda que hay que realizar para obtener $N(\geq 1)$ caras consecutivas.

A ver qué tal se os da.

Posts aleatorios

Autor: ^DiAmOnD^ | Publicado el 19 de May de 2009
Categorías: Juegos | Imprime este post

Sin comentarios

Trackback | 19 May, 2009

Bitacoras.com
Jones, Francisco | 19 de May de 2009 | 09:28

$2^N$ ?
^DiAmOnD^ | 19 de May de 2009 | 14:15

No .
pablo | 19 de May de 2009 | 14:54

¿ N * 2^N ?
^DiAmOnD^ | 19 de May de 2009 | 15:35

Pues tampoco.

¿Estáis probando al azar o vuestras respuestas tienen justificación? Supongo que es lo segundo, por lo que pienso que sería mejor explicar cómo habéis llegado a esos resultados porque el razonamiento podría ser interesante para llegar a la solución.
Conrado | 19 de May de 2009 | 16:33

2^{q}\,-1

Siendo q=num lanzamientos, cuando 2^{q-n+1}\,*(q-n+1) > 2^{q}\, entonces q es el número buscado.
hernan | 19 de May de 2009 | 17:52

Parecía fácil, pero no…
Llegué a la solución $\displaystyle 2 (2^N-1)$
(y lo verifiqué simulando) pero mi demostración es algo retorcida… veré si puedo emprolijarla… y generalizar a moneda cargada.
pablo | 19 de May de 2009 | 17:55

yo he agrupado los lanzamientos en grupos de N, hay 2^N combinaciones posibles de las que una es la que queremos (N caras).
no he tenido en cuenta que al juntar los grupos se crean otras combinaciones, por lo que supongo que seran menos.
M | 19 de May de 2009 | 18:20

Muy buena, Hernán.
hernan | 19 de May de 2009 | 18:54

Si la moneda tiene probabilidad $p$ de salir cara, entonces el número esperado de lanzamientos es (salvo error)

$\displaystyle \frac{1}{1-p} \left( \frac{1}{p^N}-1 \right)$

Después copio mi demostración.
hernan | 19 de May de 2009 | 19:27

Debe haber alguna manera más simple -tal vez por combinatoria (conteo) en lugar
de probabilidad- aunque el conteo difícilmente sea generalizable a monedas cargadas.

Yo consideré la tirada de monedas como una sucesión de v.a. iid (Bernoulli) ,
por ej ${x[n]} = ( 0 , 1, 0 , 0 ,1 \cdots\ )$ con $n=1,2, \cdots$ .

Llamemos $t_k$ el valor de $n$ (cantidad de tiradas) donde ocurre (termina) la primera
“racha” de $k$ caras consecutivas. En este planteo, $t_k$ es una variable aleatoria.
Consideremos su función de probabilidad condicionada al valor de $t_{k-1}$ .
Condicionando a su vez al valor de la próxima moneda ( $x[t_{k-1}+1]$ ) vemos que hay dos posibilidades:
o bien la nueva moneda es cara (probabilidad: $p$ ) con lo cual tengo la racha esperada y $t_k = t_{k-1}+1$ o bien tengo ceca; en este caso, es como si el experimento empezara de nuevo, y por lo tanto la funcion de probabilidad (condicionada a este suceso) es la misma que la no condicionada, pero con el origen desplazado en $t_{k-1}+1$ .
La probabilidad condicionada entonces es la “mezcla” de esos dos casos.

Consideremos las esperanzas, llamamemos $\widehat{t_k} = E[t_k]$ y $\widehat{t_k/t_{k-1}} = E[t_k/t_{k-1}]$

Entonces la esperanza condicionada se puede escribir

$\widehat{t_k/t_{k-1}} = p (t_{k-1}+1) + (1-p) ( \widehat{t_k} + t_{k-1}+1)$

Aplicamos ahora la propiedad de la esperanza-de-la-esperanza-condicionada $E[E[x/y]] = E[x]$ :

$\widehat{t_k} = p (\widehat{t_{k-1}}+1) + (1-p) ( \widehat{t_k} + \widehat{t_{k-1}}+1)$

Reagrupando:

$\displaystyle \widehat{t_k} = \frac{1}{p} (\widehat{t_{k-1}}+1)$

Que corresponde a una ecuación en diferencias lineal de primer orden; para obtener la condición inicial, vemos que con $k=1$ tenemos una distribución geométrica, entonces $\widehat{t_1} = \frac{1}{p}$

Solucionando, se llega a

$\displaystyle \widehat{t_k} = \frac{1}{1-p} \left( \frac{1}{p^k} -1 \right)$
M | 19 de May de 2009 | 19:54

Sí señor, Hernán. Básicamente es la misma prueba que conocía. Resumiendo, si $f(N)$ es el número esperado de tiradas necesarias para obtener $N$ caras seguidas, y si la moneda está trucada de modo que la probabilidad de sacar cara es $p$ entonces se tiene por lo que has comentado que:

1) $f(1)=\frac{1}{p}$

2) $f(N)-f(N-1)=p\cdot f(1)+(1-p)\cdot f(N)$ , o bien

$f(N)=\frac{1}{p}\cdot f(N-1)+\frac{1}{p},\;N\geq 1$ ( $f(0):=0$ )

y esta recurrencia nos conduce a tu fórmula explícita: $f(N):=\frac{1-p^N}{(1-p)p^N}$
Àlex Llaó | 20 de May de 2009 | 09:49

Alguno puede explicar un poco mejor como resolver el problema¿? Soy informático y la verdad es que me cuesta entender como resolverlo.

muchas gracias.
M | 20 de May de 2009 | 13:50

Àlex Llaó, por simplificar un poco, hay que decir que se hace un razonamiento inductivo.

Toma $f(N)$ el número esperado de lanzamientos necesarios para obtener $N$ caras seguidas (este valor $f(N)$ es una esperanza matemática, como indicaba Hernán, y se asume que existe y es finito para cada $N$ )

Una vez que lleves $N-1$ caras seguidas, el número esperado de lanzamientos necesarios para obtener las $N$ caras será $f(N)-f(N-1)$ .

Por otro lado, una vez que lleves $N-1$ caras seguidas, debes distinguir si el siguiente lanzamiento sale otra vez cara (con probabilidad $1/2$ ) o, en caso contrario, debes volver a realizar $f(N)$ lanzamientos para volver a obtener las $N$ caras (más un lanzamiento inicial que te salió cruz).

Esto te conduce a la recurrencia $f(N)-f(N-1)=\frac{1}{2}\cdot 1+\frac{1}{2}(1+f(N))$ . O bien, $f(N)+2=2(f(N-1)+2)$ . Como $f(0):=0$ , obtienes lo que decía Hernán: $f(N)=2^{N+1}-2$ lanzamientos en promedio.
hernan | 20 de May de 2009 | 15:46

Una manera un poco menos rigurosa (espero que más intuitiva) de verlo:

1) Sabemos (espero) la esperanza de una distribución geométrica: en un ‘experimento’ con probabilidad de éxito P, la cantidad esperada de intentos hasta obtener el primer éxito es 1/P

http://en.wikipedia.org/wiki/Geometric_distribution

2) Nuestro ‘experimento individual’, en primer aproximación, podría pensarse como tirar N monedas seguidas y esperar que todas sean caras. Si pensamos en cada corrida de N monedas como un único experimento, la probabilidad de éxito es 1/2^N. Y entonces, la cantidad esperada de intentos sería 2^N.

3) Pero lo anterior requiere corrección: porque si pensamos cada iteración (la tirada de una moneda) como la realización de mi experimento (ver si la secuencia de las útlimas N monedas son todas caras), estas realizaciones no son independientes; de hecho, de las N monedas a examinar en este intento, N-1 ya fueron examinadas en la realización anterior (que, suponemos, fue un ‘fracaso’).

4) Esta dependencia ¿me perjudica o me beneficia (en comparación con el escenario 2, que correspondería a tirar N monedas nuevas cada vez)? Nos perjudica. Nos dicen que en las N monedas “anteriores” hubo al menos una ceca, lo cual ‘probablemente’ implique que ella se encuentre en las N-1 monedas a ‘re-examinar’.

5) El dato (condicion) que tengo al intentar una nueva tirada sería : ‘las N monedas anteriores tienen al menos una ceca’. Descomponemos ese evento en dos alternativas: A) la moneda ‘màs antigua’ (la que no examinaré ahora) es ceca, y B) esa moneda es cara (no asumo nada respecto del resto).
A y B tienen igual probabilidad.
Si asumimos el caso A, el dato ‘las N monedas anteriores tienen al menos una ceca’ se torna irrelevante (ya lo sè!), y mi probabilidad de éxito es la misma que tenía originalmente (1/2^N)
Si asumimos el caso B, el dato es muy relevante, y mi probabilidad de èxito se hace 0.

6) Ponderando ambas probabilidades (igualmente), tengo una probabilidad de èxito para cada iteración de 1/2^(N+1), y entonces mi cantidad de intentos esperada es 2^(N+1)

Que es buena aproximación (sobre todo para N grande) al resultado exacto.
Jose | 20 de May de 2009 | 23:31

Hola, les agradecerìa que me ayudaran en esto. Lo he intentado, pero nada:
Supongamos que A (subconjunto de los reales) cumple la siguiente propiedad:
Si una sucesiòn converge a un punto de A, entonces sus elementos estàn en A para todo n lo suficientemente grande.

Se pide probar que necesariamente es un abierto.
Gracias de antemano…
Jose | 21 de May de 2009 | 01:46

Bueno, ya me saliò. Disculpen las molestias, jeje.
Jose | 21 de May de 2009 | 03:15

Vaya, parece que errè en la prueba. Si alguien tuviese alguna lo agradecerìa mucho.
Dani | 21 de May de 2009 | 09:02

Supongamos que A no fuese abierto. Es decir, $\exists x \in A$ tal que $\forall \varepsilon$ >0, $B_{\epsilon}(x)$ no está contenido en A (la bola de centro x y radio epsilon). Entonces esto quiere decir que para todo $\varepsilon$ la intersección de $B_{\epsilon}(x)$ y $A^c$ (el complementario de A) $\neq$ al vacío. Definamos pues, una sucesión $\{x_n\}_{n \in \mathbf{N}}$ donde $\forall n,\quad x_n \in B_{\frac{1}{n}}(x)$ y $x_n \in A^c$ . Claramente $\lim_{n \rightarrow \infty} x_n = x$ , pero $x_n$ nunca está en A por construcción, lo cual contradice a nuestra suposición de que los elementos de una sucesión convergente a un punto de A deben terminar estando en A. Con esto obtenemos la contradicción que queríamos y concluimos que A debe ser abierto.
Q.E.D
Jose | 21 de May de 2009 | 11:32

Hola Dani, gracias por tu respuesta. Pero tengo una inquietud. ¿La existencia de tal sucesiòn esta garantizada?. Tengo la impresiòn de que intrìnsecamente se ha utilizado el axioma de elecciòn. Si es asì, ¿No es este axioma aún controversial?. Si me equivoco en mi suposición apreciarìa mucho que me ilustren…
Àlex Llaó | 21 de May de 2009 | 22:59

Muchas gracias a todos por la explicación!!!!!
Dani | 22 de May de 2009 | 19:08

Sinceramente no estoy seguro. Creo que formalmente sí que es necesario el axioma de elección para dar validez a la demostración, pero quizás te debiera contestar ^DiAmOnD^ o uno de los compañeros con más conocimiento sobre el tema para aclarar la cuestión. De todas maneras muy poca matemática seria de hoy en día se sostendría en pie sin el axioma de elección, y aunque haya mucha controversia en la práctica el porcentaje de matemáticos que no lo usan es bastante pequeño… yo que tú no me preocuparía mucho por eso, aunque siempre está bien saber lo que usas y lo que no
Jose | 23 de May de 2009 | 00:24

Serìa interesante que abrieran un tema concerniente al axioma de elecciòn y su correcto uso. Aun no se que tan cierto es. La verdad que cada vez que lo uso, hasta donde lo se manejar, poco me convence.