Max Hernandez

Laberinto - Ejemplo de Canvas en HTML5

jueves, 29 de marzo de 2012

Tarea 3: Pruebas estadísticas para los números pseudoaleatorios


Las aplicaciones de los números aleatorios en la actualidad se ha vuelto tan diversa y tan importante en la actualidad que se necesita de cierto grado de calidad para que sea utilizable para las personas. Por eso esta semana quiero hablar sobre los generadores de números aleatorios y algunas pruebas para tener una mayor seguridad de que los generadores que utilizamos tienen la calidad ya mencionada.

Las aplicaciones de los números aleatorios son :

  • Criptografía.
  • Simulaciones.
  • Videojuegos.
  • Muestras en experimentos.
  • Obras de arte.

Generadores de numeros aleatorios

Los generadores de números aleatorios es un algoritmo determinista que producen una variable al azar especificada por una distribución..

Pruebas de aleatoriedad

PPara las pruebas de aleatoriedad elegí tres pruebas como ejemplo del conjunto de pruebas de NSIT los cuales son:

  • Frequency Test - Monobit: El propósito de esta prueba es determinar si la proporción de ceros y unos obtenidos.
  • Frequency Test - Block: El propósito de esta prueba es determinar la proporción de unos en bloques de M-bits (M=cantidad de bits por bloque)
  • Runs Test: El propósito de este es medir la cantidad de secuencias de bits idénticos interrumpidos.


import math
import random
from scipy.stats import chi2 

def frecuency_monobit(n ):
   sn = 0
   for i in range(n):
       bit = random.randint(0, 1) # numeros aleatorios 0 y 1
       if bit == 1:
           sn = sn + 1
       else:
           sn = sn - 1
   sobs = math.fabs(sn)/math.sqrt(n) 
   p_value = math.erfc(sobs/math.sqrt(2))
   
   return p_value

# M-> logitud de cada bloque
# n-> numero total de muestras
# N-> numero de bloques
def frecuency_block(n, M):
    N = int( n / M)
    bloques = []
    for i in range(N):
        bloques.append(0.0)
        for j in range(M):
            bit = random.randint(0, 1)
            if bit == 1:
                bloques[i] = bloques[i] + 1.0
        bloques[i] = bloques[i] / M

    x2obs = 0
    for i in bloques:
        x2obs = x2obs + (i-0.5)**2
    x2obs = 4*M*x2obs
    return (1.0 - chi2.cdf(x2obs, M-1))

#numero de muestras
#verificar el contador de cambios
def run_test(n):
    media = 0.0     vn_ops = 1.0

    for i in range(n):
        nuevo = random.randint(0,1) #int(algo[i])
        media = media + nuevo
        if i > 0 and anterior != nuevo:
            vn_ops = vn_ops + 1
        anterior = nuevo
    media = media / n

    if math.fabs(media-0.5) <= (2 / math.sqrt(n)):
        return math.erfc( math.fabs(vn_ops - 2*n*media*(1-media) )  / ( 2*math.sqrt(2*n)*media*(1-media) )  )
    else:
        return "run_test(): Prueba rechazada"

print frecuency_monobit(1000)
print frecuency_block(100,10)
print run_test(100) 
Estas pruebas generan un numero el cuales la regla de decisión es que si los valores son menores a 0.01 entonces se considera que la muestra es aleatoria.

Para revisar esto genere 10 veces cada prueba y como se puede observar, la mayoría de estas pasan la prueba lo cuál nos entrega un poco mas de seguridad de el generador.



Generador de numeros Poisson

Una vez que tengo una cierta seguridad de que los números que son el producto de el generador tienen las características necesarias para considerarse les aleatorios, ahora puedo intentar generar números con una distribución para mis fines de simulación, en mi caso practique haciendo un ejemplo convirtiendo los números producto del generador de python a la distribución poisson.

import math
import random

def poisson(lamb):
    acumulador = exponencial( lamb)
#    acumulador = 0
    contador = 0
    while( acumulador < 1):
        acumulador = acumulador + exponencial( lamb)
        contador+=1
    return contador


def exponencial(lamb):
    return (-1*math.log( random.random() ))/lamb

def buscar(vector, buscado):
  for i in range(len(vector)):
      if vector[i][0] == buscado:
          return i
  return -1

def contar(fl, n, lamb):
    numeros = []
    for i in range(n):
         generado = poisson(lamb)
         pos = buscar(numeros ,generado )
         if pos != -1:
             numeros[pos][1] += 1
         else:
             numeros.append([generado ,0 ])
    try:
        fl = open(fl , "w")
    except:
        print "Error al arbir el archivo"

    for i in numeros:
        i[1]=float(i[1])/n
        fl.write(str(i[0])+" "+format(i[1], '.6f')+"\n")

    try:
        fl.close()
    except:
        print "Error al cerrar el archivo"

contar( "poisson.dat", 1000000, 20)
poisson_esperado("esperado.dat", 1, 50, 20)
-----------------------------
Este fue mi primer resultado, para comparar los números que esperaría que salieran con los números obtenidos genere 1000000 números con mi generador de números pPoisson y después conté el número de ocurrencias de cada uno y estas dividirlas entre el total para obtener una probabilidad práctica de que genere ese número mi programa. Después lo gráfique junto con la formula de la distribución Poisson dándole como parámetro una lambda semejante y el resultado fue el siguiente:


Después de algunas pruebas y modificaciones el resultado fue el siguiente donde los números tienen una probabilidad práctica muy parecida a la de la formula de Poisson, con lo cuál compruebo que este generador tiene cierta calidad para usarla en futuras simulaciones.




Referencias:
http://es.wikipedia.org/wiki/Generador_de_n%C3%BAmeros_aleatorios
Página de NIST- http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Presentación del proyecto medio curso



Es un juego entre dos personas, cada una con 16 piezas, en un tablero de 8x8. Cada pieza tiene características especiales para moverse y atacar otras piezas y el objetivo es derrocar al rey enemigo.
El objetivo es llevarlo a una dispositivo móvil que utilice el sistema operativo Android usando la pantalla táctil y la cámara como interfaces de entrada y salida con el usuario. Además de agregar características de realidad aumentada.

Importancia/impacto esperado del proyecto

La importancia del proyecto se encuentra en que tratar de juntar las mejores características de los juegos de ajedrez ya existentes y tratar de añadir características que no existen en los juegos ya existentes como es la realidad aumentada

La realidad aumentada (RA) es el término que se usa para definir una visión directa o indirecta de un entorno físico del mundo real, cuyos elementos se combinan con elementos virtuales para la creación de una realidad mixta en tiempo real. Aquí muestro un vídeo de el proyecto de Jaimie Thom quien trabaja con algo parecido pero usando una computadora de escritorio.


Esta es la pagina del proyecto y aquí se puede encontrar mas información del mismo: http://jaimie2819.posterous.com/augmented-reality-chess-game-final-documentat

El plan es dar la ilusión de tener un tablero real frente al usuario(para esto usar la cámara) y que la interacción con el tablero sea lo mas real posible, ya seleccionando una pieza usando la pantalla táctil o pasando la mano sobre ella para seleccionar.




Herramientas y tecnologías utilizadas:


  • El SDK de Android: Me servirá para compilar y probar mis aplicaciones.
  • Eclipse: Como IDE para desarrollo se integra con el SDK de Android por lo cual me resultara útil.
  • QCAR: Librería de realidad aumentada desarrollado por la empresa Qualcomm. Es gratuito, gratuito y parece tener una buena documentación.
  • Cacoo: Herramienta para generar gran cantidad de diagramas y diferentes tipos de diseños de interfaces gráficas.
  • GanttProject: GanttProject es una herramienta de escritorio multiplataforma para la calendarización y gestión de proyectos.

Diagrama de Gantt


Como se puede ver las partes mas significativas de el proyecto son tener la lógica del juego, después pasarlo a android con las características necesarias para que el sistema funcione correctamente en un dispositivo móvil tomando en cuenta las restricciones de este.
Después se añade la parte de la realidad aumentada, con la estructura del sistema tenemos hábil abstraer entradas y salidas del programa para poder añadir por módulos este tipo de características puesto que aun no estoy completamente seguro como funcione la librería que escogí.
Una vez hecho esto corrijo lo que haya que corregir y me centro en los detalles y pruebas con esto se da el proyecto por finalizado.

Saludos

Links útiles:

lunes, 12 de marzo de 2012

Tarea 2: Procesos estocásticos discretos y continuos

Buen día.

Problema a analizar:

Dos jugadores de poker empiezan una partida amistosa, Alice y David. Alice reparte las cartas y se da cuenta que su mano muy buena( póker) y entre sus cartas un 9 de treboles. Por otro lado David recibe una mano bastante peculiar, un Rey, una Quina, un Joto todos de treboles y un 2 de diamantes. Como puede observarse es una mano muy buena pero necesita un As de treboles y para vencer a Alice. Despreciando la idea de que Alice tambien puede pedir cartasy el final del juego. ¿Cuál es la probabilidad de que david saque un As de treboles del mazo?, ¿Cuál es la probabilidad de que lo haga en el siguiente turno si la carta obtenida anteriormente se introduce de nuevo en el mazo y se barajea el mismo? y ¿Cúal es la probabilidad de que lo haga en el siguiente intento?.


Para responder las preguntas anteriores ponemos darnos cuenta que el problema tiene las caracteristicas de uns distribución geometrica, pero pimero:

¿Qué es una distribución de probabilidad?
Una función que asigna a cada suceso definido sobre la variable aleatoria la probabilidad de que dicho suceso ocurra. El rango de esta función constituye todos los sucesos que puedan ocurrir en el conjunto o en la situación analizada.

Los tipos de distribuciones son los siguientes:


Distribuciones discretas:
Se consideran distribuciones discretas las cuáles su función solo puede tomar valores positivos, finitos o finitos númerables.

Entre las mas comunes se encuentran:
  • Distribución de Bernoulli: Donde se mide la probabilidad de exito a fracaso de un suceso.
  • Distribución binomial: Donde se mide la probabilidad de exito o fracaso en sequencia una cantidad determinada de veces.
  • Distribución binomial negativa: Donde se mide la probabilidad de que en un número determinado de intentos obtener otra cantidad determinada de exitos.
  • Distribución Poisson: Donde se mide la probabilidad de que un numero de eventos ocurran en tiempos especificos.
  • Distribución geométrica
  • Distribución hipergeométrica

Distribuciones continuas:
Se consideran distribuciones continuas las cuáles su función puede tomar valores infinitos dentro de un intervalo definido.

Entre las mas comunes se encuentran:
  • Distribución exponencial
  • Distribución normal
  • Distribución uniforme (continua)
  • Distribución F


Distribución geométrica
[imagen obtenida de: http://mathworld.wolfram.com/images/eps-gif/GeometricDistribution_800.gif]


Esta distribución analiza el numero de ensayos de Bernoulli que se necesitan para llegar al primero éxito. Su rango va desde uno hasta el infinito, puesto que por lógica debe haber al menos un intento y los intentos pueden ser ilimitados. Como los intentos pueden ser ilimitados, se puede verificar que si se suman los valores de la función de uno al infinito esta suma tiene como resultado uno.

Su formula de probabilidad es la siguiente:

Para x=1,2,3...

Donde "p" es la probabilidad de éxito y "q" que es "q=(1-p)" la probabilidad de fracaso, como uno es la probabilidad total a esta se le resta la probabilidad de éxito y lógicamente esta probabilidad que queda es la de fracaso.

La formula del valor esperado es :



Ahora volviendo al problema de la partida de póker

para analizar el problema primero obtendremos la probabilidad de que en un ensayo de Bernoulli haya un éxito o un fracaso, primero definimos el éxito: Un mazo de cartas tiene 52 cartas pero diez de estas ya están en manos de los contrincantes por lo tanto no las tomaremos en cuenta, eso nos deja 42 cartas de las cuales solo nos es útil entonces la probabilidad de acierto es 1/42.

Entonces "p = 1/42" lo cuál hace que :
q = (1-(1/42)) = 42/42 - 1/42 = 41/42
Sustituyendo esto en la formula:
P(x) = ((41/42)^0)*(1/42) = 1/42


Puesto que en el primer intento la probabilidad de éxito es la misma que un solo ensayo de Bernoulli o intentar una ves. Para ver el comportamiento de la probabilidad de que el primer éxito sea en un numero de intento mayor.

Ahora para responder las otras dos preguntas realice una gráfica con un programa que hicimos en la clase. El eje horizontal es el número de veces que se debe lanzar la moneda y el eje vertical es la probabilidad.



Como es observable es entre mas aumenta la cantidad de intentos mas improbable se vuelve que esa sea la del primer éxito.

versión continua - distribución exponencial

La distribución exponencial es la distribución que mide la probabilidad de que de dos eventos específicos y que ocurren regularmente sucedan uno de tras de otro con una diferencia de tiempo especifica = "x".

Los parámetros de la función son el tiempo "x" y la frecuencia con la que  ocurre el evento en una unidad de tiempo que se representa con la letra griega lambda( λ).

La función de la densidad de la probabilidad es:
La formula para obtener el valor esperado es la siguiente:

Una de las cosas que caracterizan esta distribución es que se dice que esta no tiene memoria. Esto quiere decir que

una vez esperados un tiempo "T" antes de un evento esto no quiere decir que el tiempo de espera para el siguiente evento vaya a disminuir, este sigue teniendo la misma distribución de probabilidad.

Para entender esta función modifique un programa que hicimos en clase para graficar esta el cuál es el siguiente:

function exponential(lambda, filename)
  output = fopen(filename, "w");
  prob = 1;
  x = 1;
  while (prob > 0.0)
    prob = 1-exp(  ((-1*lambda)*x) );
    x++;
    fprintf(output, "%d %f\n", x, prob);
  endwhile
  fclose(output);
endfunction

Y gráfique el siguiente ejemplo digamos que cada jugada en el juego entre David y Alice dura dos en promedio dos minutos entonces si nuestra unidad de tiempo son los minutos entonces se podria decir que se le entrega a David media carta por minuto osea que " λ = 0.5" así que para analizar esto hize la siguiente gráfica donde el eje vertical es la probabilidad y el horizontal el tiempo:



Como  puede observarse al avanzar el tiempo la gráfica tiende a acercarse a uno lo cuál nos dice que  entre más tiempo pase mas probable es que se lleve a cabo la siguiente partida.

referencias:
http://es.wikipedia.org/wiki/P%C3%B3quer
http://es.wikipedia.org/wiki/Distribuci%C3%B3n_de_probabilidad
http://es.wikipedia.org/wiki/Distribuci%C3%B3n_de_probabilidad