martes, 3 de diciembre de 2013

Una curiosidad: permutaciones obtenidas por simulación


El estudio que emprendemos hoy se parece bastante al problema de completar una colección de cromos, que ya tratamos hace unos meses (http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-1.html)

Pertenece al tipo de problemas de llenado aleatorio de un conjunto, como el de una línea o un cartón de bingo. Estos ejemplos se caracterizan porque la probabilidad de obtención de un nuevo elemento del conjunto depende del número de los ya obtenidos, en el sentido negativo, de ir disminuyendo la probabilidad conforme se llena el conjunto.

Hoy lo experimentaremos con permutaciones. Hace días, jugando con las cifras del número 19913 con el fin de obtener todos los números primos posibles, acudí a la herramienta Combimaq, de hojamat.es (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#combimaq), que me proporcionó la solución exacta, elemental, de 30 permutaciones, 30=5!/(2!2!)=120/4



Me pregunté entonces por la posibilidad de obtener esos resultados mediante simulación. Elegí este procedimiento:

(1) Se fija un conjunto cualquiera de unos pocos elementos, por ejemplo el dado 1, 9, 9, 1, 3, con o sin repetición de elementos.

(2) Lo sometemos reiteradamente a transposiciones aleatorias de sus elementos. Como una permutación se puede  descomponer en dichas transposiciones, cada vez que efectuemos esta operación estaremos creando una permutación del conjunto primitivo. Como es de suponer, después de varios intentos las permutaciones comenzarán a repetirse.

(3) Cada permutación nueva la comparamos con las anteriores, y si es distinta a todas ellas, la incorporamos a la lista de las formadas y seguimos el proceso. Nada nos garantiza que esto agote el conjunto de todas las permutaciones posibles, al igual que una colección de cromos en la que no se intercambian ni se compran puede no llegar a completarse nunca.

(4) El proceso parará si le incluimos un tope, que podría ser el número total de permutaciones que conozcamos previamente. Por ejemplo, en el caso de 19913 serían 30 permutaciones. Si no se indica ningún tope, puede que el proceso llegue a completar el catálogo de permutaciones o bien, cosa improbable, que nunca lo haga, se inicie un ciclo sin fin y haya que interrumpir el proceso (en realidad, esto también puede ocurrir fijado un tope de resultados). Esta interrupción se logra con la pulsación de la tecla ESC (en Excel) o Ctrl+May+ Q en OpenOffice y LibreOffice.

Descripción de la herramienta

Hemos incluido este simulador en http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#simulpermu

Funcionamiento

La  hoja principal presenta esta estructura



Escribes los elementos del conjunto en la fila de color verde. En la imagen se  ha elegido aaabbb.

Fijas el número de elementos, porque en esa fila puede haber otros residuales más a la derecha.

Después concretas el tope, o número de permutaciones esperado. En el ejemplo hemos escrito un 0 para que sea el simulador el que llegue al número de permutaciones totales, en este caso 20.

En la parte izquierda verás aparecer los intentos y los resultados. Es normal que se necesiten muchos intentos, y en este caso sin tope, la tardanza nuestra en interrumpir el proceso añadirá más. Por eso, para recuentos o estadísticas es preferible fijar previamente el número esperado de permutaciones.

Junto a cada permutación figura el número de intentos que ha necesitado.

Podemos usar el simulador para reproducir un resultado que ya conocemos. Imaginemos que en un curso de Combinatoria al alumnado le cuesta entender el número de permutaciones que se pueden construir con las letras REDADA. Iniciamos la simulación y observamos que la creación de permutaciones se estabiliza en el número 180













Para entender mejor el proceso, ordenamos la tabla completa mediante las columnas D, E, F,… (no olvides desactivar la opción de “Mis datos tienen encabezados”). De esta forma se entenderá mejor cómo se crean las distintas permutaciones:



En un segundo paso se puede demostrar la fórmula 6!/(2!2!)=720/4=180

Por el contrario, si sabemos, por ejemplo, que el conjunto 17767 presenta 5!/3!=20 permutaciones, planteamos la generación aleatoria con tope 20, y posteriormente ordenamos la tabla:



Podemos observar que las permutaciones se han ordenado de forma creciente (como si fueran cifras de un número) y demuestran mediante formación ordenada que el número de permutaciones vale 20.

Estadísticas de la simulación

Lo anterior presenta un interés relativo, es un mero ejercicio de simulación. Le dotaremos de más potencia realizando algunas estadísticas mediante la inclusión de un generador de series, que repite el proceso cuantas veces deseemos y nos devuelve las estadísticas.

Recuerda que cada permutación viene acompañada de los intentos que se han necesitado para encontrarla. En la imagen figura el desarrollo para generar las permutaciones del conjunto 1234.



Se han necesitado 64 intentos, repartidos como se ve en la imagen, con bastantes oscilaciones aleatorias, aunque con tendencia a crecer. Si deseamos estudiarlos mejor deberemos acudir a series de simulaciones.

La primera permutación sólo ha necesitado un intento. Siempre es así si el conjunto básico no presenta repeticiones (¿por qué?). Aquí el segundo también ha salido a la primera, pero el tercero ya necesita a 2 intentos. Así van aumentando hasta llegar al último, que requirió 16 intentos. Estamos ante una sucesión creciente de incrementos también crecientes.

Para estudiarla mejor pasamos a la segunda hoja de cálculo, en la que disponemos del botón para crear series, y lanzamos una de 1000 repeticiones, para obtener unas medias que se puedan confrontar con una posible teoría o realizar el ajuste a una función. El resultado de esta serie ha sido el siguiente:



¿Se podrá confrontar esto con alguna teoría? En realidad sí, porque el caso de los intentos necesarios para obtener unos éxitos se estudia con la distribución binomial negativa o de Pascal (http://www.uv.es/ceaces/base/modelos%20de%20probabilidad/binegativa.htm).

En nuestro ejemplo sólo se pretende conseguir un éxito y no varios, por lo que la fórmula de los intentos medios es muy simple M=1/p, siendo p la probabilidad de obtener, en nuestro caso, una permutación nueva, y que será del tipo 3/24, 4/24, …

En la imagen se han añadido los resultados que se esperarían según la teoría. Parecen muy ajustados, pero en otros muchos experimentos que hemos realizado se advierte un sesgo, en el sentido de que el número de intentos medios es algo superior a lo esperado, lo que nos hace dudar de la absoluta aleatoriedad del proceso.

En esa misma segunda hoja aparecerán los valores máximos y mínimos del número de intentos. El mínimo, si no hay repeticiones, siempre será 1 y el máximo oscila tanto que no tiene interés una estadística sobre él.

Pues a ver si descubres algo más o amplías el modelo.