Autor Tema: Probabilidad de un subconjunto con probabilidades para cada elemento

0 Usuarios y 1 Visitante están viendo este tema.

12 Agosto, 2020, 07:51 pm
Leído 290 veces

DeepButi

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: es
  • Karma: +0/-0
Tengo un conjunto de m elementos y un subconjunto de n elementos (0<n<m) construido según el siguiente procedimiento:

  • Se elige un elemento al azar
  • Para el elemento elegido se consulta en una tabla su probabilidad de conservarlo (y se conserva o descarta)
  • Se repite el procedimiento hasta que una de dos
    • a. Se dispone ya de n elementos, o bien
    • b. El número de elementos conserados + el número de elementos restantes = n. En dicho caso se conservan todos ls elementos restantes independientemente de su probabilidad en la tabla.
Estoy buscando un algoritmo que me permita calcular la probabilidad de cualquier subconjunto específico.

Un ejemplo simple, disponemos de los elementos E1 E2 y E3 de probabilidades p1=0.5 p2=0.4 p3=0.2.
¿Cual es la probabilidad del subconjunto E1 (m=3, n=1)?

Casos favorables. Elemento Ei, probabilidad de elegirlo, probabilidad de conservarlo (si es E1) o de rechazarlo (si NO es E1)

Código: [Seleccionar]
E1  1/3 0.5             
E2  1/3 (1-0.4)   E1  1/2 0.5
                  E3  1/2 (1-0.2)   E1
E3  1/3 (1-0.2)   E1  1/2 0.5
                  E2  1/2 (1-0.4)   E1

La probabilidad del subconjunto E1 es por tanto
p(E1) = 1/3 * 0.5 + 1/3 * 0.6 * (1/2 * 0.5 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.5 + 1/2 * 0.6) = 0.4433
y
p(E2) = 1/3 * 0.4 + 1/3 * 0.5 * (1/2 * 0.4 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.4 + 1/2 * 0.5) = 0.3533
p(E3) = 1/3 * 0.2 + 1/3 * 0.5 * (1/2 * 0.2 + 1/2 * 0.6) + 1/3 * 0.6 * (1/2 * 0.2 + 1/2 * 0.5) = 0.2033

He generalizado el método para n=1, pero soy incapaz de obtener una fórmula/algoritmo genérica para cualquier n.

============================================

Probabilidad del subconjunto Ek con m elementos de probabilidades pi

$$p(Ek)=∑_{j=1}^mpk′′ * Combi^{j−1} * \frac{1}{j ∗ C(^m_j)}$$

Donde pk'' = 1 cuando j=m y pk'' = pk cuando j<>m
y $$Combi^j$$ significa la suma de los possibles productos de j elementos del tipo (1-pi) con i<>k
Como la explicación de $$Combi^j$$ no sé si es muy clara, veamos un ejemplo con m=4 k=2

Código: [Seleccionar]
j=1 ...   p2 / 4 +                              (*sin elementos*)
j=2 ...   p2 [(1-p1) + (1-p3) + (1-p4)] / 12 +              (*elementos simples*)
j=3 ...   p2 [(1-p1) (1-p3) + (1-p1) (1-p4) + (1-p3) (1-p4)] / 12 +     (*todos los posibles pares*)
j=4 ...   (1-p1) (1-p3) (1-p4) / 4                      (*todos los posibles trios*)

12 Agosto, 2020, 09:45 pm
Respuesta #1

Masacroso

  • Moderador Global
  • Mensajes: 2,583
  • País: es
  • Karma: +0/-0
Me parece que no hay un algoritmo eficiente que calcule la probabilidad exacta, o al menos yo no veo cómo, ya que en la forma que está relatado el problema no veo otra salida que utilizar la fuerza bruta, es decir, dado un conjunto listar todas las formas diferentes de llegar a obtener ese conjunto, y luego calcular la probabilidad de obtener el conjunto para cada una de las formas.

Por otra parte puedes utilizar el método de Monte Carlo para obtener una probabilidad aproximada, es decir, "jugar" muchas veces tu juego probabilístico y quedarte con la información relevante, es decir, cuántas veces aparece el conjunto deseado. Éste sería un algoritmo muy eficiente en el sentido de que cada vez que, mientras juegas, aparece un elemento que no pertenezca a tu conjunto elegido, entonces descartas inmediatamente ese juego y empiezas otro.

13 Agosto, 2020, 08:13 pm
Respuesta #2

DeepButi

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: es
  • Karma: +0/-0
Gracias por la respuesta.

No puedo usar el método Montecarlo porque el càlculo de la probabilidad es sólo una pequeña parte de un algoritmo más complejo que ya consume mucho tiempo de proceso, en el límite de lo razonable.

Llevo tiempo dándole vueltas y no veo cómo generalizarlo. Probablemente opte por multiplicar simplemente las probabilidades individuales (según el algoritmo descrito en mi post original). Obviamente no es correcto ya que no son eventos independientes, pero mejor que tal como lo hago de momento seguro que será ... y los resultados actuales son más que buenos ;)

PS. Actualmente simplemente multiplico las pi individuales, una burrada matemática pero como digo con resultados muy aceptables.

13 Agosto, 2020, 08:53 pm
Respuesta #3

Masacroso

  • Moderador Global
  • Mensajes: 2,583
  • País: es
  • Karma: +0/-0
Gracias por la respuesta.

No puedo usar el método Montecarlo porque el càlculo de la probabilidad es sólo una pequeña parte de un algoritmo más complejo que ya consume mucho tiempo de proceso, en el límite de lo razonable.

Llevo tiempo dándole vueltas y no veo cómo generalizarlo. Probablemente opte por multiplicar simplemente las probabilidades individuales (según el algoritmo descrito en mi post original). Obviamente no es correcto ya que no son eventos independientes, pero mejor que tal como lo hago de momento seguro que será ... y los resultados actuales son más que buenos ;)

PS. Actualmente simplemente multiplico las pi individuales, una burrada matemática pero como digo con resultados muy aceptables.

No he pensado mucho en el problema pero puedes intentar otra cosa que a lo mejor te va mejor, y es buscar un modelo que dependa de algunos estadísticos de la "muestra" de partida, es decir, de los m valores entre cero y uno. Por ejemplo ver si utilizando la media y la varianza de las m probabilidades puedes desarrollar un modelo que aproxime bastante bien los resultados, al menos para un valor de m suficientemente grande.

Creo que una librería que puedes usar para un estudio así sería Gen.jl del lenguaje de programación Julia. Pero bueno, como digo es sólo una idea, a lo mejor por fuerza bruta sale mejor, o como tú dices asumiendo que cada elección es independiente.

En cualquier caso alguien que sepa más de estadística te podría orientar mejor para buscar un modelo al proceso.

14 Agosto, 2020, 12:10 am
Respuesta #4

geómetracat

  • Moderador Global
  • Mensajes: 2,331
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Con probabilidades de conservar/rechazar cada elemento distintas yo desde luego no veo otra salida que fuerza bruta. Puedes unificar algunos casos (los que involucran permutaciones de los mismos elementos), pero poco más. En cualquier caso, no es muy distinto de lo que haces para el caso \( n=1 \), que también se podría considerar un algoritmo de fuerza bruta.

Si los valores de \( m,n \) con los que vas a trabajar son pequeños puedes usar un algoritmo a fuerza bruta que te de las probabilidades exactas. Si son grandes mejor buscar otra manera. Lo de aproximar la probabilidad por el producto de las de \( n=1 \) yo la verdad es que no veo por qué debería funcionar. Pero si dices que te funciona bien, pues ya está.
La ecuación más bonita de las matemáticas: \( d^2=0 \)