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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

22 Comentarios

  1. 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.

    Publica una respuesta
  2. 2^{q}\,-1

    Siendo q=num lanzamientos, cuando 2^{q-n+1}\,*(q-n+1) > 2^{q}\, entonces q es el número buscado.

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. 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)

    Publica una respuesta
  7. 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}

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. À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.

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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…

    Publica una respuesta
  12. Vaya, parece que errè en la prueba. Si alguien tuviese alguna lo agradecerìa mucho.

    Publica una respuesta
  13. 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

    Publica una respuesta
  14. 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…

    Publica una respuesta
  15. 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 🙂

    Publica una respuesta
  16. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: El problema de la semana es el siguiente: Calcular el número esperado de lanzamientos…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *