Seguir iterando con una probabilidad de 0.95. ¿Cuantas iteraciones da?

[derkenuke]

Hola:

Se me ha ocurrido este código:

Código PHP:

  for( var i=Math.random(); i<prob; i=Math.random() ) { 
}  
   

Como podéis ver, Se producen iteraciones mientras el número generado esté por debajo de prob. Ésto, si no me equivoco, quiere decir que se seguirá iterando con una probabilidad de prob. Es decir, si prob=0.95 se seguirá iterando si un número aleatorio entre 0 y 1 es menor que 0.95, osea, con una probabilidad del 0.95.


Entonces quería ver cuantas iteraciones haría de media una probabilidad del 0.95, hice esta función:

Código PHP:

  function iterar(prob) { 
    for( var i=Math.random(), cont=0; i<prob; i=Math.random() ) { 
        //document.write("Una iteración ("+i+") <br/>"); 
        cont++; 
    } 
    return cont; 
}  
   

Y este simple código para llamar a iterar() nIteraciones veces. Almaceno en iteraciones cuántas veces se itera cada vez, y luego hago la media entre todos los elementos de iteraciones.

Código PHP:

  var iteraciones = []; 
var nIteraciones = 10000; 
var prob = 0.95; 
for(var i=0; i<nIteraciones; i++) { 
    iteraciones.push( iterar(prob) ); 
} 
document.write("Media de iteraciones "+(eval(iteraciones.join("+"))/nIteraciones) + ".");  
   

La salida para este código es, por ejemplo (variará por ser el número de iteraciones aleatorio):

Media de iteraciones 18.8814.

Lo que me llama la atención es que este número siempre suele estar entre 18.5 y 19.3 o así.


No soy muy ducho en las matemáticas. ¿Cómo puedo llegar a esos valores de 18.5 y 19.3 sabida la probabilidad de 0.95? ¿Cómo se puede saber también al revés? Creo que estoy pidiéndo una fórmula matemática...


Dejo una tabla de datos, asombroso cómo crece al final. También es curioso la media de iteraciones con 0.5 de probabilidad: está muy cerca de la unidad:

Media de iteraciones con probabilidad 0.00 en 10000 iteraciones = 0.
Media de iteraciones con probabilidad 0.03 en 10000 iteraciones = 0.0304.
Media de iteraciones con probabilidad 0.05 en 10000 iteraciones = 0.0574.
Media de iteraciones con probabilidad 0.08 en 10000 iteraciones = 0.0838.
Media de iteraciones con probabilidad 0.10 en 10000 iteraciones = 0.1149.
Media de iteraciones con probabilidad 0.13 en 10000 iteraciones = 0.1487.
Media de iteraciones con probabilidad 0.15 en 10000 iteraciones = 0.1854.
Media de iteraciones con probabilidad 0.18 en 10000 iteraciones = 0.2166.
Media de iteraciones con probabilidad 0.20 en 10000 iteraciones = 0.2615.
Media de iteraciones con probabilidad 0.22 en 10000 iteraciones = 0.2873.
Media de iteraciones con probabilidad 0.25 en 10000 iteraciones = 0.3318.
Media de iteraciones con probabilidad 0.27 en 10000 iteraciones = 0.3815.
Media de iteraciones con probabilidad 0.30 en 10000 iteraciones = 0.4323.
Media de iteraciones con probabilidad 0.33 en 10000 iteraciones = 0.4995.
Media de iteraciones con probabilidad 0.35 en 10000 iteraciones = 0.5442.
Media de iteraciones con probabilidad 0.38 en 10000 iteraciones = 0.6051.
Media de iteraciones con probabilidad 0.40 en 10000 iteraciones = 0.6778.
Media de iteraciones con probabilidad 0.43 en 10000 iteraciones = 0.7526.
Media de iteraciones con probabilidad 0.45 en 10000 iteraciones = 0.825.
Media de iteraciones con probabilidad 0.48 en 10000 iteraciones = 0.9412.
Media de iteraciones con probabilidad 0.50 en 10000 iteraciones = 1.0025.
Media de iteraciones con probabilidad 0.53 en 10000 iteraciones = 1.1115.
Media de iteraciones con probabilidad 0.55 en 10000 iteraciones = 1.2107.
Media de iteraciones con probabilidad 0.58 en 10000 iteraciones = 1.3876.
Media de iteraciones con probabilidad 0.60 en 10000 iteraciones = 1.5018.
Media de iteraciones con probabilidad 0.63 en 10000 iteraciones = 1.7111.
Media de iteraciones con probabilidad 0.65 en 10000 iteraciones = 1.8557.
Media de iteraciones con probabilidad 0.68 en 10000 iteraciones = 2.095.
Media de iteraciones con probabilidad 0.70 en 10000 iteraciones = 2.3204.
Media de iteraciones con probabilidad 0.73 en 10000 iteraciones = 2.7343.
Media de iteraciones con probabilidad 0.75 en 10000 iteraciones = 3.0131.
Media de iteraciones con probabilidad 0.78 en 10000 iteraciones = 3.4826.
Media de iteraciones con probabilidad 0.80 en 10000 iteraciones = 4.0523.
Media de iteraciones con probabilidad 0.83 en 10000 iteraciones = 4.8373.
Media de iteraciones con probabilidad 0.85 en 10000 iteraciones = 5.6319.
Media de iteraciones con probabilidad 0.88 en 10000 iteraciones = 7.382.
Media de iteraciones con probabilidad 0.90 en 10000 iteraciones = 9.1932.
Media de iteraciones con probabilidad 0.93 en 10000 iteraciones = 13.2168.
Media de iteraciones con probabilidad 0.95 en 10000 iteraciones = 19.2286.
Media de iteraciones con probabilidad 0.98 en 10000 iteraciones = 49.1258.

Un saludo.

[Kelpie]

Quizá te ha faltado hacerte la gran pregunta: ¿Cuántas iteraciones debería dar?

En realidad hay una pequeña falta en el planteamiento. Tu bucle dejará de dar vueltas en cuanto se encuentre un valor menor que 0.95. La cantidad de vueltas que da es un valor aleatorio dentro del rango marcado por otro valor aleatorio, por lo que evoluciona junto con la probabilidad que le marcas, pero dentro de ella es aleatorio.
Para saber la probabilidad de sacar una pica de una baraja se mide contando las veces que se saca una pica en un montón de intentos, no contando las cartas que se han sacado hasta logar una pica en esos intentos...

Para comprobar probabilidades deberías seguir el axioma de 'tantas veces en tantos intentos'. Este código quizá se explique mejor que yo:

Código:

function itera(probabilidad){
  cont=0;
  vueltas=1000;
  for(i=0;i<vueltas;i++){
    r=Math.random();
    if (r<probabilidad) cont++;
  }
  return(cont*100/vueltas);
}

De todas maneras es un tema muy interesante. Te felicito por la claridad de tu planteamiento , algo tan raro de ver por aquí.

[derkenuke]

Hola Kelpie, gracias por responderme.

Iniciado por Kelpie

En realidad hay una pequeña falta en el planteamiento. Tu bucle dejará de dar vueltas en cuanto se encuentre un valor menor que 0.95.

¿No será un numero mayor a 0.95? Bueno, creo que ha sido una falta al escribir nada más



Creo que entiendo lo que me quieres decir, pero no sé yo hasta qué punto me sirve. Del código que me das, llamando a itera(0.5), el resultado me da el porcentaje de Math.random() que han sido menores de 0.5, esto es, aproximadamente el 50%. Obviamente cuantas más iteraciones (vueltas) hagamos, más acercamiento tendremos al 50%.


Lo que no consigo captar del todo es esta línea:

Iniciado por Kelpie

La cantidad de vueltas que da es un valor aleatorio dentro del rango marcado por otro valor aleatorio, por lo que evoluciona junto con la probabilidad que le marcas, pero dentro de ella es aleatorio.

Lo que me gusta de mi código es que este bucle:

Código PHP:

  for( var i=Math.random(); i<0.95; i=Math.random() ) { 
}  
   

Puede iterar 0 veces, 10 veces, o incluso un millón de veces, aunque sabemos que si hacemos 10.000 veces el bucle, la media de iteraciones será de unas 19. Esa sería la diferencia a generar el número máximo de iteraciones con un número aleatorio.

La pregunta es cómo deducir el 19 a partir del 0.95. ¿Hay forma?

[Kelpie]

Para simplificar supongo que rnd nos va a devolver un número entre 0 y 1 con dos decimales

En realidad lo que estamos buscando es cuántas vueltas hay que dar para obtener un número menor que "márgen" (tomamos 0.90 para el planteamiento)
Haciendo 10000 llamadas

Estudiamos la probabilidad de que salga el primero...: 90% -> En 9000 llamadas no da vueltas
Nos quedan 1000 llamadas
De esas 1000, en un 90% saldrá el segundo y se dará una vuelta...
En 900 se dará una vuelta -->900 vueltas
Nos quedan 100 llamadas
De esas 100, en un 90% se darán dos vueltas
En 90 se darán dos vueltas -->180 vueltas
Nos quedan 10 llamadas
De esas 10, en un 90% se darán tres vueltas
En 9 se darán tres vueltas --> 27 vueltas
Nos queda 1 vuelta
De ella, en un 90% se darán 4 vueltas
En 0,9 se darán 4 vueltas --> 3,6 vueltas

Hasta ahora tenemos 1.110,6 vuelyas, lo que hace una media de 0.11106 vueltas

En realidad, para 0,9 la media matemática será de 0,111111.

Algunos valores más:

Para 0,80 --> 0,25 (Lo que en tu cuadro sería la probabilidad de 0.20)
Para 0,70 --> 0,428571429 (Lo que en tu cuadro sería la probabilidad de 0.30)
Para 0,60 --> 0,6666 (Lo que en tu cuadro sería la probabilidad de 0.40)

Mañana te pongo un cuadro completo que ahora me tengo que ir...

[derkenuke]

Hola Kelpie:

Gracias por la respuesta, me he hecho yo mismo el script que genera cuadro para ver que los resultados son prácticamente los que puse en el primer post con algún que otro desvío. Efectivamente para 0.50 sale de resultado la unidad.


De todas maneras sigo sin comprender por qué funciona tu algoritmo. No entiendo la frase Estudiamos la probabilidad de que salga el primero. Qué quiere decir que en 9000 llamadas no da vuelta, por qué aumentas cada vez las vueltas (una vuelta para 900, dos para 90, tres para 9, cuatro para 0.9... ¿A qué te refieres con vuelta exactamente?)

En fin, son muchas dudas a las que espero que me des respuesta.



Un saludo

[Kelpie]

Yo soy muy malo explicando....

Lo primero: tienes razón. Me he liado y estoy haciéndolo al revés . estoy contando la posibilidad de sacar uno menor y debería ser mayor, por lo que los valores me dan al revés (lo que a ti te da para el 0.40 a mí me da para el 0.60).

Tomando como umbral el 0.90 y el bucle metido en una función. Hay que tener en cuenta que al meter la llamada a random() en la cabecera del bucle for, si obtenemos el número menor de 0.90 a la primera, nunca pasaremos por la instrucción cont++ porque el bucle no va a ejecutarse. Esto nos lleva a que la cantidad de iteraciones (vueltas) del for es siempre una unidad menor que las llamadas a random().

Hay un 90% de probabilidades de que el primer número que te devuelva random() sea menor que 0,90. Eso significa que en el 90% de los casos obtendrás a la primera un i<0.90 y el for no se ejecutará. Si vamos a llamar 10000 veces a la función, esto significa que en 9000 llamadas (el 90% de 10000) el bucle for no se ejecutará ("No dará ninguna vuelta").

Nos queda por estudiar lo que va a pasar en las 1000 llamadas restantes en las que no obtenemos un número menor que 0.90 a la primera.
La probabilidad de obtenerlo a la segunda es también de un 90% (Los números pueden repetirse). Esto es, que en un 90% de los casos, el bucle for tendrá que iterar una vez ("Dar una vuelta") hasta conseguir el número menor de 0.90. Esto nos deja que en 900 llamadas (El 90% de 1000) iterará 1 vez.

Nos quedan 100 llamadas en las que no sabemos qué pasa, pero sabemos que no vamos a obtener un menor de 0.90 a la segunda (eso ocurre en las 900 que ya hemos contado antes). Tenemos un 90% de probabilidades de obtenerlo a la tercera, caso en el que el for itera 2 veces. Por ello, en 90 llamadas (el 90% de 100) el bucle hará 2 iteraciones. Ya llevamos 900 de antes más 180 de ahora (90 veces 2): 1080 iteraciones.

El resto es así. Cada vez nos quedan menos llamadas por estudiar y las que nos quedan son en las que más iteraciones se da.

En resumen y para cada llamada, hay un 90% de probabilidades de que no se ejecute el bucle
un 9% de que se ejecute y haga una iteración
un 0.9% de que haga dos iteraciones
un 0.09% de que haga tres iteraciones
...

La fórmula no se cómo ponértela sin poner una imágen. Sería:


"Sumatorio entre i=0 e i=100 de: probabilidad por 10 elevado a menos i por i"

Esta fórmula está mal. La buena es:
media= sumatorio de (1-probabilidad) por probabilidad elevada a n por n
Ver unos post más adelante....

En realidad no habría que llegar a i=100 ya que mucho antes los resultados son casi despreciables.

Vaya rollo que he metido Lo siento pero cuando me meto en matemáticas no tengo medida...

[derkenuke]

Bueno, espero que no hayas pensado, Kelpie, que abandoné el post. He estado dándole vueltas, me cuesta bastante ver el concepto.


Pero ahora sí creo que lo entiendo


Entonces lo que hay que hacer es estudiar lo que va a pasar en todas y cada una de las iteraciones (si hacemos 10 000, hay que estudiar qué pasa en los 10 000 casos).

Iniciado por Kelpie

En resumen y para cada llamada, hay un 90% de probabilidades de que no se ejecute el bucle
un 9% de que se ejecute y haga una iteración
un 0.9% de que haga dos iteraciones
un 0.09% de que haga tres iteraciones...

La fórmula no se cómo ponértela sin poner una imágen. Sería:

"Sumatorio entre i=0 e i=100 de: probabilidad por 10 elevado a menos i por i"

Veo bien los porcentajes de probabilidad que hay en cada caso. Pero entonces ¿con la fórmula esa lo que hallamos es la suma de las probabilidades de que haga n iteraciones? El resultado para probabilidad = 0.90 sería 0.11111... ¿Por qué a mí en la primera tabla que posteé ese valor coincide con su complementario 0.10? Creo que es porque has dicho que hay un 90% de probabilidades de que no se ejecute el bucle y en realidad el código hace referencia a: hay un 90% de probabilidades de que sí se ejecute el bucle.
Pero con el script éste he hecho la tabla de datos..

Código PHP:

  for(var probabilidad=0; probabilidad<=1; probabilidad+=0.1 ) {
    // "Sumatorio entre i=0 e i=100 de: probabilidad por 10 elevado a menos i por i"
    var resultado = 0;
    for(var i=0; i<10; i++) {
        resultado += probabilidad * Math.pow(10,-i) * i;
    }
    document.write("Para una probabilidad de "+probabilidad.toFixed(2)+" se producirán "+resultado.toFixed(6)+" iteraciones de media.<br/>");
}  
   

Para una probabilidad de 0.00 se producirán 0.000000 iteraciones de media.
Para una probabilidad de 0.10 se producirán 0.012346 iteraciones de media.
Para una probabilidad de 0.20 se producirán 0.024691 iteraciones de media.
Para una probabilidad de 0.30 se producirán 0.037037 iteraciones de media.
Para una probabilidad de 0.40 se producirán 0.049383 iteraciones de media.
Para una probabilidad de 0.50 se producirán 0.061728 iteraciones de media.
Para una probabilidad de 0.60 se producirán 0.074074 iteraciones de media.
Para una probabilidad de 0.70 se producirán 0.086420 iteraciones de media.
Para una probabilidad de 0.80 se producirán 0.098765 iteraciones de media.
Para una probabilidad de 0.90 se producirán 0.111111 iteraciones de media.
Para una probabilidad de 1.00 se producirán 0.123457 iteraciones de media.

Yo creo que hay algo mal...

La tabla sería entonces así si no me he equivocado y he cogido el concepto bien (10 000 iteraciones):
Hay un 90% de probabilidades de que sí se ejecute el bucle, un 10% de que no. -> En 1 000 iteraciones no se ejecutará.
Vamos a ver qué pasa con las 9 000 iteraciones restantes por estudiar:
Un 90% de 9 000 (8100, 81% del total) de que se ejecute y haga una iteración -> En 8100 iteraciones haría una iteración.
Nos quedan 9000 - 8100 = 900 por estudiar:
Un 90% de 900 (810, 8.1% del total) de que se ejecute y haga 2 iteraciones -> En 810 iteraciones haría 2 iteraciones.
Nos quedan 90 por estudiar:
En 81 iteraciones (0.81%) haría 3 iteraciones
Nos quedan 9 iteraciones.
En 8.1(0.081%) iteraciones haría 4 iteraciones
en 0.81(0.0081%) haría 5
en 0.081(0.00081%) haría 6
...
En resumen:
Hay un 10% de probabilidades de que no se ejecute.
Un 81% de que se ejecute y haga una iteración
Un 8.1% de que haga dos
Un 0.81% de que haga tres
...
Y todo eso sumado 10% + 81% + 8.1% + 0.81% + 0.081% + ... = 100%
Como en tu ejemplo.


Aquí me vuelvo a perder entonces, porque no comprendo la fórmula. ¿Cómo deduzco el 9.1932 para 0.90 de mi tabla desde aquí?


Jo, ya siento ser tan duro, pero es que no son fáciles para mi estos conceptos...


Un saludo y espero que no tardes tanto como yo en responder el post. Lo siento!

[Kelpie]

Puedes deducirlo de la fórmula:

media= sumatorio de (1-probabilidad) por probabilidad elevada a n por n

La fórmula anterior tenía un error de deducción. (Ya he editado el Post)

Puedes ver aquí una imágen de esa fórmula.

Un javascript que te lo calcula es (tienes un ejemplo en la página donde está la imágen):

Código:

function pon(prob){
	//Esta función admite un segundo parámtero opcional para la aproximación. 
	//La aproximación es el márgen de error que queremos. Cuánta más aproximación, menos error.
	//Por defecto voy a poner 600 
	aproximacion=arguments[1]?arguments[1]:600; //Por defecto un valor de 600 para la aproximación está bien... Menos de 100 es temerario ;-) 
	sbt=0;
	for (r=0;r<aproximacion;r++){	sbt+=(1-prob)*Math.pow(prob,r)*r;}
	return(sbt);
}

Hay diferencias entre la "teoría" y tus datos, y habría que limar un pcoco el tema de decimales...

[derkenuke]

SiiiI!! Perfecto Kelpie, eres un genio en esto de los números!



Bueno, la fórmula funciona perfectamente. Y no se me va a ocurrir preguntarte cómo se saca jajaja.

Sin tu ayuda no me habría podido ni imaginar que ésto era posible.
Mira que es improbable encontrar a alguien que controle de ésto y que esté rondando por los foros de javascript jaja.


Bueno, que muchas gracias amigo, todo zanjado.
Un saludo, nos leemos.