martes, 7 de febrero de 2012

Simulación para vagos (o que no sabemos lo suficiente)

El otro día, buscando temas por ahí, me topé con la secuencia http://oeis.org/A051293

1, 2, 5, 8, 15, 26, 45, 76, 135, 238, 425, 768, 1399, 2570, 4761, 8856, 16567, 31138…

que representa el número de subconjuntos de {1,2,3,...,n} cuya media aritmética es entera.

Por ejemplo, en el caso de 4, los subconjuntos con media entera son {1}, {2},{3},{4},{1,3},{2,4},{1,2,3} y {2,3,4}, en total 8.

Me pareció un tema interesante e intenté abordarlo usando congruencias y después particiones, pero la cosa se complicó y me sentí vago. Quien tenga más disposición que yo puede seguir con ello. Además, el autor de esta secuencia en OEIS se vio obligado a conjeturar cosas. Malo.

¿Y si lo simulara? 

Yo nunca lo había intentado con conjuntos de este tipo y quizás podría reproducir la secuencia, al menos con algún pequeño error. Me puse a ello:

(a) Simulación de subconjuntos

Se puede usar la técnica de tirar una moneda: recorremos los elementos de {1,2,3,...,n} y para cada uno de ellos tiramos una moneda. Si sale cara, lo incluimos en el subconjunto, y si sale cruz, no lo incluimos. En los lenguajes de programación disponemos de la función ALEATORIO(), que en Basic es RND. Así que el algoritmo de formación de un subconjunto de {1,2,3,...,n} podría ser similar a este esquema:

Randomize
For i=1 to n
If rnd(1)>1/2 then … se incluye en el subconjunto
Next i

Para quienes no lo sepan, randomize hace que cada vez que usemos el algoritmo se forme una secuencia distinta de números aleatorios (en realidad, seudoaleatorios)

(b) Identificación de las medias aritméticas enteras

Como en nuestro caso nos interesa la media en cada subconjunto, las sentencias presentadas en Basic se podrían concretar en el sentido de que para cada subconjunto tomemos nota del número de elementos y de su suma, para luego dividir y hallar la media.

Podemos definir la variable n para recoger el número de elementos y la variable s para formar la suma. En ese caso las sentencias anteriores se podían modificar así:

Randomize
n=0:s=0
For i=1 to n
If rnd(1)>1/2 then n=n+1:s=s+i
Next i
media=s/n

De esta forma obtendríamos la media de los elementos de cada subconjunto.

Ahora sólo nos quedaría comprobar si la media es entera.  Esta prueba consistirá en ver si media=INT(media). Podemos generar muchos  conjuntos aleatorios, por ejemplo 10000 y contar aquellos en los que la media es entera. En caso afirmativo incrementamos un contador.

Por último, lo que marque el contador lo convertimos en proporción dividiendo entre 10000 y multiplicamos después  por 2n para que cuente subconjuntos. Después presentamos resultados. Aquí tienes un listado aproximado en Basic de Excel:

Randomize
a = 0  Contador de exitos
Input n  o cualquier otra forma de capturar n


For i = 1 To 10000


ActiveWorkbook.Sheets(1).Cells(3, 3).Value = i  esto sólo sirve para saber por dónde va la simulación
c = 0 cuenta elementos del conjunto aleatorio
s = 0 suma elementos del conjunto aleatorio
b = 1 / 2 es la media, que la declaramos al principio no entera.


For k = 1 To n se genera el conjunto aleatorio
m = Rnd(1)
If m < 1 / 2 Then c = c + 1: s = s + k: b = s / c
Next k


If b = Int(b) Then si es entero se incrementa el contador
a = a + 1
ActiveWorkbook.Sheets(1).Cells(fila, 6).Value = a / i * 2 ^ n  Valor adaptado a 2^n
End If


Next i

Los resultados obtenidos han sido bastante acertados. Transcribimos los correspondientes a una sola pasada del algoritmo:

N S(N) Simulación Errores relativos
3 5 5,0576 0,01152
4 8 8,031209363 0,00390117
5 15 14,8704 -0,00864
6 26 25,5872 -0,015876923
7 45 44,6464 -0,007857778
8 76      76,34683468 0,004563614
9 135 133,9707708 -0,00762392
10 238 236,032 -0,008268908

Como era de esperar, al aumentar N se presentan desviaciones mayores. Los errores relativos son más estables.

Pues hemos hecho el vago, pero con diversión.