Metonymie.com :: Apuntes » Probabilidad
Bloque de Colores

Problema de Algoritmia Básico: Simulación del Caso Promedio

Icono de Post February 29 2012 :: Algoritmia, Estadística, Probabilidad, Python ::

Finalmente para analizar el caso promedio, decidí realizar una serie de simulaciones en Python, aproveche de paso, para presentar este programa como trabajo práctico final en la materia “Lenguajes de Scripting” de la facultad. El código del programa de la simulación puede encontrarse aquí, para correrlo compilar algo.c, ejecutar limpiar.sh y luego version-1-0.py. Las muestras se guardan en formato CSV en la carpeta “resultados/muestras” y los reportes en “resultados/reportes”.

Algunas notas sobre la simulación

Me interesaba analizar específicamente el comportamiento de la porción del algoritmo en la que se itera a travéz de la lista pasados que es la porción variable del mismo. Para hacer esto, cree una variable global total y en cada iteración por la lista pasados en la función esta_en_lista() se la incrementa en uno. El programa escribe luego en STDOUT el valor de esta variable al finalizar. Ver algo.c.

En el script de Python se genera una lhttps://github.com/emluque/Post_Stuff/blob/master/Problema_Algoritmia_Basico/Simulacion/version-1-0.pyista randomizada se levanta un proceso al que se le pasa esta lista como argumento y luego se lee el STDOUT del proceso para obtener el costo. Esto se hace en el archivo: muestras.py y la porción de código que hace esto es:


  def generar_lista(self):
    lista = []
    for i in range(self.n):
      lista.append(random.randint(1, self.k))
    return ",".join( [str(x) for x in lista])

  def generar_resultado(self, lista ):
    process = subprocess.Popen(["algoritmo/algo", lista] , shell=False, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    res = ""
    for char in process.stdout.read():
      res += char
    
    process.wait()
    #Esta linea que sigue es medio al dope
    if (process.returncode != None):
      if(process.returncode < 0):
        print("----")
        print(process.returncode)
        print("----")
        raise NameError("Tio, No andubo el proceso.") 
    else:   
      process.kill()

    return int(res)

  def generar_resultados(self):
    for i in range(self.cant):
      strr = self.generar_lista();
      a = self.generar_resultado( strr )
      self.resultados.append(a)

Resultados

Un conjunto de resultados pregenerados (una corrida completa del programa puede tardar varias horas) puede verse aquí.

Reportes de Tipo 1

Lo primero que podemos ver en los reportes de tipo 1 es como a mayor tamaño de muestra, la función va tendiendo a un tipo de gráfica especifica. Que no es exactamente igual para diferentes tamaños de alfabeto y cadena, pero se acerca a un Campana de Gauss aunque un poco deformada en la región derecha y con una media corrida un poco hacia la izquierda del rango de valores posibles.

Por ejemplo, este es el gráfico obtenido para tamaño de cadena 10, tamaño de alfabeto 10 con 100000 muestras:

Y este es para 200,200,100000:

Reportes de Tipo 2

Los reportes de tipo 2, permiten ver el comportamiento de la gráfica manteniendo fijo el tamaño de cadena y de muestra.

Que nos muestra el reporte de tipo 2?

Bueno lo que vemos es que manteniendo el tamaño de cadena fijo, al ir aumentando el tamaño de alfabeto, los valores estadísticos (promedio, mediana, modo) van siendo cada vez mayores, lo mismo sucede con la gráfica. Podemos pensar que la posibilidad de ocurrencia de un elemento mayor a los elementos precedentes aumenta a mayor tamaño de alfabeto, lo cual mueve los valores hacia la derecha. Ver el comportamiento de los valores en el reporte para tamaño de cadena 200.

Por otro lado si el tamaño de alfabeto es significativamente mayor al tamaño de cadena, este comportamiento va disminuyendo. Lo cual indica que luego de un determinado valor en función al tamaño de la cadena, la posibilidad de que ocurra un elemento mayor a los elementos anteriores va estabilizándose. Ver reporte para tamaño de cadena 10.

Reportes de Tipo 3

Los reportes de tipo 3, nos muestran que la gráfica de la función se encuentra corrida hacia la izquierda en relación al rango de valores posibles, y que a mayor valor de n y k más hacia la izquierda se mueve en proporción al rango. Esto parecería coincidir con nuestras intuiciones de los posts anteriores, y parecería confirmarse gráficamente los factores de atenuamiento que habíamos considerado en estey este posts.

Gráfico de la función con alfabeto n=50, k=50 y muestra de tamaño 500:

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Simulación del Caso Promedio

Probabilidad – Formulas Básicas

Icono de Post May 14 2008 :: Estadística, Probabilidad ::

Definiciones Básicas

Experimento Aleatorio: Experimento cuyo resultado no puede predecirse con exactitud.

S: Espacio Muestral: Conjunto de todos los resultados posibles de un experimento aleatorio.

EJ: Experimento: arrojar 2 veces una moneda de 2 caras

E = {(c,c), (c,s), (s,c), (c,c)}

Punto Muestral: cada uno de los resultados posibles de un experimento aleatorio.

Suceso o Evento: subconjunto de puntos del espacio muestral.

Suceso Imposible o nulo: no ocurrirá con total seguridad.

Probabilidad de Laplace

Es a priori, no experimental.

Si un experimento admite N resultados posibles, todos ellos equiprobables entonces:

P(A) = F N = Casos Favorables Casos Posibles

Desventajas:

  • Resultados pueden no ser equiprobables
  • Numero de casos debe ser finito
  • No siempre se conocen los casos favorables

Probabilidad de Von Misses o de la Probabilidad Frecuencial

Es a posteriori, luego de un experimento.

EJ: Se toma un dado cargado y buscamos la probabilidad de que salga el número 2. Se realiza el experimento un número n de veces y observamos la cantidad de resultados favorables fr (Frecuencia absoluta del suceso).

f r = f i n = número de exitos número de pruebas

Ley de los grandes números o convergencia estocástica de las frecuencias relativas

Al aumentar las pruebas las frecuencias relativas tenderán a estabilizarse alrededor de un determinado valor.

P(A) = lim n f r = lim n f a n

Clasificación de Sucesos

Sucesos mutuamente excluyentes: La ocurrencia de uno impide la ocurrencia del otro.
P(A ∩ B) = 0
Sucesos no excluyentes o conjuntos: pueden ocurrir simultaneamente.
P(A ∩ B) != 0
Sucesos exhaustivos: Su unión es equivalente a S
P(A) + P(B) + … = P(S) = 1
A ∪ B ∪ … =

Definición Axiomatica de Probabilidad

Sean:
S espacio muestral
E un experimento aleatorio
A un suceso ∈ S en E

entonces P(A) es una función del tipo P(A): A -> (0,1)

Caracteristicas

0 <= P(A) <= 1
P(S) = 1
Sean A, B dos sucesos mutuamente excluyentes => P(A ∪ B) = P(A) + P(B)

Teorema de la suma de Probabilidades

P( A ∪ B ) = P(A) + P(B) – P(A ∩ B) = 1 – P( A _ B _ )
NOTA: Pensar en Cardinalidad de conjuntos cuando se piensa P( A ∪ B).
Nota: ∪ puede pensarse en este caso como ⊻ y ∩ como ∧, si se utiliza la notación P(A o B) = P(A) + P(B) – P(A y B)

EJ: Probabilidad de sacar una carta de un maso que sea o un 4 o un oro = P(4) + P(oro) – P(4 de oros)

P( A ∪ B ∪ C) = P(A) + P(B) + P(C) – P(A ∩ B) – P(A ∩ C) – P(B ∩ C) + P(A ∩ B ∩ C)

Teorema del Producto de Probabilidades

Sea S un espacio muestral y A,B dos sucesos pertenecientes a S. La probabilidad de que ocurran A y B simultanea o sucesivamente en 2 REPETICIONES de un experimento es.

P(A ∩ B) = P(A) . P(B/A) = P(B) . P(B/A)

Probabilidad condicional: P(A/B) = Probabilidad de que ocurra A dado la ocurrencia previa (o simultanea) de B

P(A/B) = P ( A B ) ) P ( B )

EJ: Se tira un dado 2 veces,

a) cual es la probabilidad de que la suma sea 8.

Evento(suma 8 ) = {(2,6), (3,5), (4,4), (5,3), (6,2)} = 5 posibilidades.

Total de combinacines de 2 dados = 62= 36

P(suma 8 ) = 5 36

Hasta aqui nos manejamos con los conceptos de Laplace.

b) Cuál es la probabilidad de que si la suma dio 8 que el primer resultado haya sido 3?

A ojo se puede ver que solamente una (3,5).

P(3 en la primer tirada) = 1 5

Pero lo vamos a hacer correctamente:

Evento(suma 8 ) = {(2,6), (3,5), (4,4), (5,3), (6,2)}
Evento(primer resultado fue 3) = {(3,1), (3,2), (3,3), (3,4), (3,5), (3,6) }
E(suma 8 ) ∩ E(primer 3) = {(3,5)}

Para sucesos independientes

Si los sucesos son independientes, la formula se reduce a:

P(A ∩ B) = P(A) . P(B)

Diagramas de Carol

A A _ TOTAL
BA ∩ B A _ ∩ BB
B _ A ∩ B _ A _ B _ B _
TOTALA A _

EJ: Sea A y B dos eventos sobre un expacio muestral con los siguientes valores

A A _ TOTAL
B101838
B _ 30342362
TOTAL40360400

P(A) = 40/400 = 1/10

P(B/A) = 10/40 = 1/4
desarrollando la formula
P(B/A) = P ( A B ) P ( A ) = 10 400 40 400 = 1/4

P(A ∩ B) = P(A) . P(B/A) = 40 400 . 10 40 = 10 400 = 1/40

Nota: los valores surgen directamente de la tabla.

Muestras sin reposición

Supongamos un conjunto U de tamaño 50. Este esta dividido en 2 subconjuntos mutuamente excluyentes y exhaustivos sobre U que llamaremos A y B, La cardinalidad de A=10 y la de B=40. O lo que es lo mismo sea E el evento de seleccionar un elemento de U => P(A) = 1/5 y P(B) = 4/5 tal que P(S) = P(A) + P(B) = 1.

Consideraremos ahora una serie de eventos: E1, E2 , E3, E en el que en cada evento se toma un elemento de U pero no se lo repone. De esta manera la cardinalidad de U decrece en 1 por cada evento realizado y se modifica el espacio muestral y tambien se modifican luego de cada evento P(A) y P(B).

Por ejemplo: supongamos que E1toma un elemento de A entonces Para E2: P(A) 9/49 y P(B) = 40/49

que posibilidad hay de que el proximo evento E2sea de nuevo A. En simbolos:

P(E2 / E1) = 10 50 . 9 49

P(ABBA) = 10 50 . 40 49 . 39 48 . 9 47

Teorema de la Probabilidad Total

Sea un espacio muestral S dividido en 2 sucesos A1 y A2 tal que: P(A1 ∩ A2) = 0 (Son mutuamente excluyentes), P ( A i ) = 1 ( forman un sistema exhaustivo ) .

Conjuntamente sobre S puede darse un suceso D conjuntamente con A1 o A2. Es evidente que P(A1 ∩ D) y P(A2 ∩ D) son mutuamente excluyentes.

P(D) = P ( A i ) . P( D / Ai)

Ej: A,B,C forman un sistema exhaustivo sobre el espacio muestra S y son mutuamente excluyentes.

P(A)=45%, P(B)=32%, P(C)=23%

Para A, D=4%, para B, D=6% y para C, D=2,5%

P(D) = P(A) . P(D/A) + P(B) . P(D/B) + P(C) . P(D/C)

P(D) = 0.45 x 0.04 + 0.32 x 0.06 + 0.23 x 2.5 = 0.043 o 0.43%

Nota: Se puede plantear con arboles

Teorema de Bayes o Teorema de la probabilidad de las causas

Sean Aisucesos excluyentes y exhaustivos, D un suceso tal que P(D) > 0 y se conocen P(D/Ai) y P(Ai).

P(Ak/D) = P ( A k D ) P ( D ) = P ( A k ) . P ( D / A k ) i P ( A i ) . P ( D / A i )

Esperanza Matematica

En una distribución de probabilidades del tipo:

Xi P( Xi )
0 P( 0 )
1 P( 1 )
2 P( 2 )
…..…….
TOTAL1 o 100%

Donde la sumatoria de todas las P( X i ) = 1 o 100%.
Se define la esperanza matematica como:

E = X i P ( X i )

Referencias

Apuntes de clase de Estadí­stica 1, Conceptos Teóricos y Ejemplos. M. Cattaneo, S. Diez, Universidad de Palermo, 2007.