si lanzamos una moneda 5 veces seguidas la probabilidad de que aparezca una racha de longitud mayor o igual que tres (ya sean tres caras o tres cruces), es un medio (16 configuraciones con rachas sobre 32 posibles). Si lanzamos la moneda 6 veces la probabilidad es de 38/64.
Las preguntas que se derivan de esto son varias:
1) Si es un problema que, por ejemplo, tenga nombre propio. Si se sabe quién estudió por primera vez estas rachas "críticas".
(creo que si..., pero no encontré referencias)
2) La fórmula general para responder las dos preguntas:
a) Si lanzo una moneda n veces, cuál es la cantidad de configuraciones distintas con rachas de longitud mayor o igual que k?
b) Si lanzo una moneda n veces, cuál es la mayor longitud k tal que la probabilidad de obtener una racha de longitud mayor o igual que k supere a 1/2?
(está claro que rachas de longitud k=1 siempre habrá, digamos que su probabilidad es 1; que k=n, esto es que todas salgan cara o ceca, son sólo dos posibilidades en 2^n, muy pequeña; cuando k va creciendo desde 1 hasta n, esa probabilidad cae de 1 a 1/2^(n-1)... ¿cuándo pasa por 1/2?)
3) Si alguien intentó una reflexión filosófica sobre estos "sesgos" del azar.
Menciona en el mail una historia divertida: "un maestro divide a su curso en dos grupos. A los del grupo A les pide que traigan de sus casas una hoja con los resultados de lanzar una moneda 100 veces. A los del grupo B les pide que en vez de hacer los lanzamientos imaginen y escriban cómo les parece que sería una secuencia así. Al día siguiente el maestro mezcla las hojas y puede ir diciendo con sólo mirar las secuencias a qué grupo pertenece cada una, si a la real o a la imaginada. Lo que ocurre, por supuesto, es que la idea intuitiva de azar está asociada a la alternancia más que a las rachas. Pero cuando n es suficientemente grande, aparecen rachas cada vez más largas. El maestro elige como reales a las secuencias que tengan al menos una racha de longitud 6."
El pedido de GM es si alguien aporta mas info sobre el problema. Se escuchan ideas, soluciones, soluciones parciales, reflexiones varias. Mis opiniones también van a los comentarios.
21 comentarios:
La última historia me recuerda los chequeos vía la ley de Benford de declaraciones de impuestos o balances: uno cree que los dígitos estarán repartidos 'al azar', pero en ese azar, la proporción de 1's es mayor a la de otros números, y una equidistribución es signo de datos dibujados.
Me gustan estos problemas...
Se trata de averiguar Q(n,k), la cantidad de secuencias binarias de largo n distintas (sobre un total de 2^n) que tienen por lo menos una "corrida" (racha de valores iguales) de longitud k o mayor.
Por comodidad, prefiero calcular P(n,k), cantidad de secuencias -etc- con rachas de largo MENOR O IGUAL a k (teniendo una, obtengo la otra: Q(n,k) = 2^n - P(n,k-1) )
Conjeturo (a confirmar! tengo la demostracion en el margen del cuaderno!) que
P(n,k) = 2 B(n,k)
donde B(n,k) es una especie de numero de Fibonacci generalizado de la siguiente manera:
B(n,2) son los numeros de fibonacci comunes ( bah, casi; habria que cambiar correr el indice) :
n 0 1 2 3 4 5 6
B2 1 1 2 3 5 8 13 .....
Para k>2 son similares, sumando los k valores anteriores:
B(n,3) = B(n-1,3) + B(n-2,3) + B(n-3,3) para n >= 1
n 0 1 2 3 4 5 6
B3 1 1 2 4 7 13 24 .....
No se si "existen" estos numeros, si no es así los acabo de inventar (je)
y no sé si tendrán una forma cerrada simple (sospecho que no).
Reviso todo y mañana te confirmo.
http://indigo.ie/~peter/Fib8.htm
http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
Aagghh.... en el link de Wolfram no sòlo están los números, también está la aplicación a nuestro problema:
The probability that no runs of k consecutive tails will occur in n coin tosses is given by F_(n+2)^((k))/2^n, where F_l^((k)) is a Fibonacci k-step number.
Bueh, me duró quince minutos la ilusión de haber descubierto algo :-)
capo!
supongo que se puede calcular una forma cerrada vía matrices, igual que se hace en Fibonnacci, y de ahí a buscar para qué k vale 1/2, debería haber apenas un paso.
ehmmm ... forma cerrada... no creo
Porque, viendolo así, k determina el tamaño de la matriz, y entonces necesitariamos una formula cerrada para tener los autovalores de esas matrices (y en funcion de k!).
Me fijé recién en el libro de Feller: atacan el problema mediante funciones generatrices y expansiones en fracciones (polos de la transformada Z, diría uno) y encuentran que en aproximacion asintótica (para n tendiendo a infinito y k fijo) P(n,k) ~ p1/s1^n donde s1 es la raiz de modulo mínimo (supongo que tendrá una relación directa con el autovalor maximo de la matriz que decíamos) y p1 es algo así como el residuo... Pero no creo que haya una manera simple/cerrada de expresar esos valores en funcion de k (tal vez al menos una ley de crecimiento?)
Ahi van (obtenidos a fuerza bruta) algunos pares n-k para los cuales
la probabilidad da (cerca de) 1/2:
n=6 k=2
n=11 k=3
n=23 k=4
n=45 k=5
n=90 k=6
n=179 k=7
n=357 k=8
n=712 k=9
acá pueden probar otros valores.
La aproximacion k = log_2(n) - 1/2 funciona bien (sorprendentemente bien) para estos valores, supongo que es casualidad.
es que casi la tenemos! el polinomio característico es x^k - (x^(k-1)+x^(k-2)+...+x^2+x+1)
me voy a fijar en el feller, a ver qué hace
Explico al menos cómo se puede llegar al resultado. Queremos. por ejemplo, calcular P(10,3), cantidad de secuencias de largo 10 con rachas no mayores a 3.
Particionemos todas esas posibles secuencias segùn la LONGITUD DE LA ULTIMA RACHA: esta puede ser de largo 1 2 o 3.
Contemos las de largo 1: pensándolo un poquito vemos que estas se corresponden uno a uno con todas las secuencias de largo 9 (o sea: hay P(9,3) secuencias de largo 10 cuya ultima racha es de largo 1)
De igual modo, hay tanta que tienen una racha final de largo 2 como total de secuencias de largo 8.
En resumen: P(10,3) = P(9,3)+ P(8,3) + P(7,3) (Con la condicion inicial P(1,k) = 2).
Si en lugar de tomar 3 tomáramos k, tendríamos k sumandos.
Faltarían afinar detalles, pero con esto se ve, creo, cómo aparecen los números de Fibonacci generalizados.
Gracias Juan por el post! Muy interesantes las respuestas, pero el problema propuesto inicialmente se refiere a rachas de caras o cruces, y no a rachas de solamente caras o solamente cruces. Por esto en el ejemplo de n=5, k=3 yo cuento 16 rachas posibles. La dificultad del problema hasta donde lo pensé yo es que cuando k es menor o igual que n/2 hay configuraciones "repetidas" que deben descontarse. No sé si el método propuesto por Hernán puede adaptarse a esta situación. En todo caso me parece fantástica esta vinculación inesperada con los números tipo Fibonacci.
Guillermo: la solución dada es precisamente para el caso de rachas de caras o cecas, indistintamente (por eso aparece el factor 2).
Así, para n=5 la cantidad de secuencias con alguna racha mayor o igual que 3 es efectivamente 16; pero ojo que yo uso otra notacion, mi k no es el tuyo. Para ese ejemplo, habrìa que calcular 2^n - P(n,k) con n=5 y k=2 (primer termino: cantidad de secuencias en total: segundo termino: cantidad de secuencias con todas las rachas menores o iguales que 2); y como podes ver en la url que puse, n=5 k=2 => p=1/2=16/32
Ah, bien bien, tenés razón, muchas gracias, G
Conjeturo [*] una ley asintótica (para k y n grandes) de la forma
p ~ (1 - 1/2^k )^(n/2)
lo cual, en nueva aproximación, y para nuestro p=0.5 daría una ley de crecimiento
k ~ log_2(n)
lo cual (sin descartar posibles errores) pinta bastante bien con los resultados numéricos.
[*] Llegué a eso por un método analítico semi-ad-hoc made in casa, bastante sencillo, afín al que usa Knuth para desarrollar la chi-cuadrado y que (si no me equivoco) tiene alguna analogía con pasar del canónico al gran canónico en física estadística. También me permitió obtener el resultado más general para una moneda cargada, se los ahorro.
Refino la aproximacion (uh, que pesado!; pero lo anoto acá porque los borradores se me van a perder pronto)
k = log_2(n) - G(p) + o(1)
donde G(p) = 1 + log_2( - ln(p) )
Así, para p=1/2 resulta que la aproximacion que yo había obtenido a ojito en realidad es :
k = log_2(n) - 0.471233627
con un error que tiende a 0 para n creciendo a infinito.
Todo conjeturas mías, pero le tengo bastante confianza.
En Modelos de Regresión Lineal se usa el resultado aplicado a residuos: los residuos son los errores (con signo) medidos como diferencias entre los valores predichos por el modelo y los observados, si uno ordena los signos de esos errores en función a alguna variable de las observaciones, la sucesión que se forme debe cumplir estadísticamente con las leyes de rachas binarias. Así, si el modelo estimara el ingreso de una persona en función de cuánto paga mensualmente de alquiler (lo que harán los bancos a partir del lanzamiento de los nuevos créditos hipotecarios que anunció el gobierno), y uno ordenara los errores del modelo en función de la variable Alquiler, la sucesión resultante: --+-+-+-+-+-+-+-++-+-+ nos da indicios acerca de la construcción del modelo (en la secuencia de arriba la ausencia de rachas "largas" dice que posiblemente Alquiler no sea la mejor opción para predecir renta).
El procedimiento se conoce como Test de Rachas.
Tengo una variante del problema que me resulta interesante. Primero, noto que el problema de cuántas sucesiones de n tiradas hay sin rachas de longitud k+1 es equivalente al siguiente: Se tienen monedas de valores 1,2,3,...,k (muchas de cada una). Se quiere pagar la cantidad n e interesa el orden en que se paga. Por ejemplo, si k es 2 y n es 4, las posibilidades son
4=1+1+1+1,
4=1+1+2
4=1+2+1
4=2+1+1
4=2+2
Son 5, y 5 es un numero de Fibonacci, como bien probó Hernán.
Ahora bien, qué pasa si no tenemos todas las monedas de 1 a k. Por ejemplo, tenemos monedas de 1,3,4 (por decir algo). O mas general: podemos tener mas de un tipo de monedas del mismo valor. Por ejemplo, podemos tener solo monedas de 1, pero de dos tipos distintos (llamemoslas "a" y "b"). Entonces 2 se puede armar como
2=a+a
2=a+b
2=b+a
2=b+b
Hay aquí una fórmula (aunque sea recursiva) como en el caso anterior?
Obs 1: no sé la respuesta.
Obs 2: llegué a este problema por un lado bien distinto: calculando dimensiones de álgebras tensoriales de espacios graduados. No creo que valga la pena contar demasiado de qué se trata, pero sí mencionar que estos problemas de conteo son útiles en diversas áreas.
El comment de Pablo lleva directamente a esta otra pregunta: qué otra clase de testeos, además del de Rachas, deberían proponerse para una secuencia al azar? Es decir, el maestro del primer ejemplo podía reconocer a simple vista una secuencia simulada de lanzamientos al azar por la falta de rachas "largas". La pregunta es si habrá otras características "experimentales" o gráficas quizá menos obvias que indiquen otras figuras, inclinaciones, sesgos, a medida que aumenta la cantidad de lanzamientos. Hay algo así como una morfología del azar?
Guillermo: creo que tu última pregunta viene contestada en buena medida (y en términos bien... cuantitativos, digamos) por los métodos para testear los generadores de nùmeros (pseudo) aleatorios.
Googleando se encuentra material, la referencia clásica es el libro de Knuth:
Knuth, D. E. (1981), Seminumerical Algorithms, Vol. 2 of The Art of Computer Programming,
Matías:
Efectivamente, el problema de calcular "cuantas secuencias de largo n con rachas no mayores a k hay" equivale a preguntarse "cuantas particiones distintas pueden hacerse del número n, en subconjuntos de tamaño entre 1 y k, distinguiendo el orden".
Con respecto a tu variante: si la entendí bien, a primera vista (bah, a segunda vista; a la primera me pareció más complicado) parece que la recursión, con su deducción, puede generalizarse bastante directamente.
Así -me parece- si tenemos n=10, k=4 con racha de largo 2 "prohibida", tendría un número de fibonacci generalizado con agujeros... algo así f(10) = f(9) + f(7) + f(6)
Creo también -aunque acá tendría que revisarlo más- que el caso de rachas multiples se generalizaría igual. Si, por ejemplo, la racha de largo 2 tiene multiplicidad o degeneración 3, quedaría
f(10) = f(9) + 3 f(8) + f(7) + f(6)
(suena demasiado simple? sin embargo, me parece que està bien)
no te parece?
creo incluso que se podrían generalizar los resultados asintóticos, si te hicieran falta.
salud
esta versión de matías, y la solución de hernán vía particiones, me recuerda que alguien (Eda) me había planteado casi el mismo problema hará diez años, a ella le aparecía en algo de fractales y teoría de número (no recuerdo si importaba el orden de la descomposición). Y la respuesta se la terminó dando una amiga suya que se dedica a proba y estadística (M Eugenia), sospecho que lo planteó como rachas también.
Hernán: bien!
Hay una versión con funciones características. Si se tienen a_1 monedas de 1, a_2 monedas de 2,.... a_k monedas de r, se toma
f = a_1 x + a_2 x^2 + ... a_k x^k
y se pone
g(x) = e^f(x)
Entonces el coeficiente de g que acompaña a x^n es el número que yo quiero dividido n! Si no se lo quiere dividir por n! se puede tomar
h(x) = 1 / (1-f(x))
El radio de convergencia de esta función alrededor de x=0 (que es la menor raíz del polinomio 1-f) dice cómo crece la sucesión buscada. Si el radio es R entonces la sucesión crece aprox. como 1/R^n. Precisamente, 1/R es la mayor raíz del polinomio característico cuando se lo piensa como matrices.
A pesar de esto, aún no logro dar con la respuesta a la pregunta b del problema original de Guillermo de manera exacta.
Respondiéndole a Guillermo, existen diversos tests que buscan decidir por el azar* ó no de una lista de valores 0-1, cara-ceca.
*azar = distribución uniforme
Algunos ejemplos hay en la sig. página, varios de los cuales lo hacen estudiando las rachas de uno y otro valor... http://csrc.nist.gov/rng/rng9.html
Pero recordar que se trata de mecanismos probabilísticos, esto es, la máxima confianza que a uno le devuelva alguno de estos tests, no "asegura" la uniforme distribución de los datos: el maestro puede parecer infalible adivinando frente a sus alumnos, pero su método de decidir por las rachas -en alguna medida- yerra en los 2 sentidos (la moneda podrá generar secuencias largas sin rachas de 6 repeticiones y también habrá alumnos que imaginen un azar no basado en la pura alternancia).
Publicar un comentario