Una pregunta de probabilidad que ha podido responder en una entrevista de trabajo

Question

Hay $N$ los diferentes tamaños de los objetivos, numeradas de 1$, 2,\dots,$ N. Los ojos vendados tirador dispara hacia direcciones al azar. Porque tamaños de destino son diferentes, el éxito de las probabilidades de cada destino son diferentes, por ejemplo, de $p_1, p_2,\dots ,p_N$. Un agujero de bala que queda en el blanco cada vez que un objetivo es golpeado. El tirador hace no saber si golpeara un objetivo o no.

Tenga en cuenta que una sesión puede ser "vacío", es decir, $p_1+p_2+\cdots+p_N\le1$. De un tiro en la mayoría de los golpes de un destino.

El tirador sigue disparando hasta $X$ de la $N$, $X<$ N, los objetivos han de agujeros de bala. ( cada una de la $X$ objetivos es dar al menos una vez). Luego de que la pistola se le dice que se detenga.

La pregunta es: al final del juego, ¿cuál es la probabilidad de que $k$ ha NO sido golpeado, $1\leq k\leq$N.

Answer 1

Bien podemos suponer que el juego continúa hasta que todos los objetivos han sido alcanzados (lo que ocurrirá en el futuro si la totalidad de los $p_j > 0$; bien podemos eliminar cualquier objetivo que tiene $p_j = 0$).

Para cada subconjunto de $S$ de $\{1,\ldots, N\}$, vamos a $p_S = \sum_{s \in S} p_s$ ser la probabilidad de que un tiro golpea a un miembro de la $S$, y vamos a $a_{i,t}(S)$ ser la probabilidad de que $i$ es uno de los primeros $t$ objetivos en conjunto $S$ a ser golpeado. Desea $1 - a_{i,X}(\{1,\ldots,N\})$. Por supuesto $a_{i,t}(S) = 0$ si $i \noen S$, y nosotros también lo llevará a ser de $0$ si $t = 0$. De lo contrario, acondicionado en el primer destino en $S$ a ser golpeado, $$ a_{i,t}(S) = \dfrac{p_i}{p_S} + \sum_{j \S \ \ barra invertida \{i\}} \dfrac{p_j}{p_S} a_{i,t-1}(S \ \ barra invertida \{j\}) $$ Ahora me reclama que $$ a_{i,t}(S) = \sum_{T \subseteq S \barra invertida \{i\}} c(t,|T|,|S|) \frac{p_i}{p_{T \cup \{i\}}} $$ para algunas constantes de $c(t,m,n)$, $0 \le m \le n-1$. Voy a probar esto por inducción sobre $t$. En el caso de que $t=1$ tenemos $a_{i,1}(S) = p_i/p_S$, entonces $c(1,m,n) = 1$ si $m = n-1$, $0$ lo contrario.

Si $t >1$, tenemos ($|S|=n$): $$ \eqalign{a_{i,t}(S) &= \dfrac{p_i}{p_S} + \sum_{j \S \ \ barra invertida \{i\}} \dfrac{p_j}{p_S} \sum_{T \subseteq S \barra invertida \{i,j\}} c(t-1, |T|,n-1) \dfrac{p_i}{p_{T \cup \{i\}}}\cr &= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2} c(t-1,m,n-1) \sum_{T \subseteq S \barra invertida \{i\}: |T| = m} \sum_{j \S \barra invertida (T \cup \{i\})} \dfrac{p_j p_i}{p_S p_{T \cup \{i\}}}\cr &= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2} c(t-1,m,n-1) \sum_{T \subseteq S \barra invertida \{i\}: |T| = m} \dfrac{p_{S \barra invertida (T \cup \{i\})} p_i}{p_S p_{T \cup \{i\}}}\cr &= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2} c(t-1,m,n-1) \sum_{T \subseteq S \barra invertida \{i\}: |T| = m} \dfrac{(p_S - p_{T \cup \{i\}}) p_i}{p_S p_{T \cup \{i\}}}\cr &= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2} c(t-1,m,n-1) \sum_{T \subseteq S \barra invertida \{i\}: |T| = m} \left(\dfrac{p_i}{p_{T \cup \{i\}}} - \dfrac{p_i}{p_S}\right)\cr &= \sum_{T \subseteq S \barra invertida \{i\}} c(t,|T|,n) \dfrac{p_i}{p_{T \cup \{i\}}} }$$ donde $c(t, m,n) = c(t-1, m,n-1)$ si $m < n-1$, mientras que $$c(t, n-1, n) = 1 - \sum_{m=0}^{n-2} {n-1 \elegir m} c(t-1,m,n-1)$$

Hmm se ve como $$ c(t, m, n) = \casos{1 & $t=n,m=0$\cr (-1)^{n+m+t} {m-1 \, seleccione {t+m-n}} & $ n-m \le t \le$n\cr 0 & lo contrario\cr}$$ Debería haber una inclusión-exclusión de una prueba de ello.

Answer 2

En el riesgo de disparo a mí mismo en el pie, he aquí cómo me gustaría que el planteamiento:

El principio clave es que podemos ignorar cualquier acción que no produzca un resultado tangible. En particular, esto incluye la falta de un objetivo, así que podemos empezar por la normalización de las probabilidades: escribir $\tilde{p_i} =\frac{p_i}{\sum_{1\leq k\leq N}p_k}$ de manera que podamos trabajar con valores que $\sum\tilde{p_i}=1$.

Pero a partir de aquí, se debe tener claro que el proceso es sólo dibujo sin reemplazo - después de nuestra prueba, vamos a tener algunas conjunto de $X$ elementos, y la probabilidad de que esos elementos son de $i_0, i_1, \ldots, i_X$ es $\tilde{p}_{i_0}\cdot\tilde{p}_{i_1}\cdots\tilde{p}_{i_X}$. Así que la probabilidad de que $k$ es golpear a solo $\dfrac{\sum_{\{S:\left/S\right/=X \wedge k\in S\}} \mathbb{P}_S}{\sum_{\{S: \left|S\right|=X\}} \mathbb{P}_S}$, la parte baja de la suma es sobre todos, $X$-elemento de subconjuntos de $S$ de $1\ldots$ N y la parte superior de la suma es sobre todos los subconjuntos con $k\in S$ y $\mathbb{P}_S=\prod_{i\in S}\tilde{p}_i$ (y, por supuesto, la probabilidad de que $k$ no se ve afectado es sólo el complemento de este valor).

EDIT: como se ha señalado por Nate Eldredge en un comentario más abajo, la fórmula no se puede simplificar a una independiente de las otras probabilidades; vamos a la siguiente servir como una advertencia acerca de hacer suposiciones!

Esta fórmula en sí mismo debería ofrecer una mayor simplificación, estoy razonablemente seguro, pero que tomará un poco de la masticación. (I fuertemente la sospecha de que todo lo demás es sólo una cortina de humo y la probabilidad final es una expresión sencilla en $\tilde{p}_k$ y $\tilde{q}_k=1-\tilde{p}_k$, pero necesito trabajar a través de los detalles y tener mis patos en una fila antes de que yo estoy seguro de que.)

Answer 3

Yo no creo que sea fácil. Dicen que tenemos p1 = p2 = 0.49, y p3 .. p22 = 0.01. Para la primera de dos objetos, la probabilidad de ser el primer objeto es de 0,49, la oportunidad de ser el primero o el segundo es un poco por encima de 0,98 y, a continuación, se hace cercano a 1, muy rápidamente.

Para el resto de objetos, la posibilidad de ser el primer objeto es de 0.01, la oportunidad de ser uno de los dos primeros es de 0,03, y estar entre los primeros 2 + n la probabilidad es aproximadamente n/a 20.

Si las probabilidades son menos extremas, a continuación, creo que se hace bastante difícil, por ejemplo de 20 elementos con 0.03 ≤ pk ≤ 0.07.

Answer 4

Chicos por favor criticar la siguiente respuesta a mi propia pregunta.

Deje que la variable $L$ ser el número de disparos por el final del juego. Entonces, claramente, la probabilidad de la $k$-ésimo objetivo sobrevive es de $(1-p_k)^L$.

Entonces la pregunta real es cómo determinar $L$ o el $E(L)$, la expectativa de $L$.

Deje de $q_i=1-p_i$ ser la probabilidad de perder un objetivo para un solo disparo.

Con $L$ disparos, la probabilidad de que el $i$-ésimo objetivo ha sido alcanzado, al menos, una vez que se $1-q_i^L$. Entonces, dado un conjunto de objetivos de $S$, donde $k\noen S$ y $|S|=X$, la probabilidad de que todos los objetivos en $S$ han sido azotadas, al menos una vez, digamos que es $S$ completado, es que \begin{ecuación} P_{\mbox{S completado}} = \prod_{i\in S} (1-q_i^L) \end{ecuación}

Tenga en cuenta que hay $C_{N-1}^{X}$ target $S$ satisfacer $k\noen S$ y $|S|=X$, formando un conjunto $\tilde{S} = \{S \mediados de k\noen S \mbox{ y }|S|=X \}$. Como se ha dicho, $|\tilde{S}|=C_{N-1}^{X}$.

Debido a que el juego se acaba cuando $L$ disparos se han hecho, entonces la probabilidad de que al menos uno $S\en\tilde{S}$ completado es igual a 1 (no estoy seguro si estoy en lo correcto al decir esto). O \begin{ecuación} \sum_{S\en\tilde{S}} P_{\mbox{S completado}} = 1 \end{ecuación}

Con todo esto, tenemos \begin{ecuación} \sum_{S\en\tilde{S}} \prod_{i\in S} (1-(1-p_i)^L) = 1 \end{ecuación}

A sabiendas de $p_i$, $1\leq i \leq N$, $L$ puede ser obtenida mediante el cálculo de herramientas como Matlab o R. (no he verificado la solución con las herramientas aún)

Answer 5

Creo que la manera correcta de pensar acerca de esto es darse cuenta de que el juego es sobre si y sólo si has llegado a $X$ los objetivos particulares, por lo que el juego en cuestión los estados son todos los subconjuntos de $[1, N]$ de tamaño $X$ - las que contienen $k$ son los estados donde se han llegado a destino k antes de que el juego es largo.

Mirando puro combinaciones, el número de estados donde se ha golpeado k es:

$$n_{k} = {X - 1 \elegir N - 1}$$

Como se selecciona la primera de ellas en el conjunto de $k$ y seleccionando $X - 1$ de los restantes $N - 1$ combinaciones. El número de combinaciones que no incluyen $k$ son:

$$n_{!k} = {X \elegir N - 1}$$

Así, en el límite donde todos los objetivos son igualmente probables, la respuesta sería:

$$\mathbf{p}_{!k} = \frac{n_{!k}}{n_{k} + n_{!k}}$$

(Tenga en cuenta que el denominador es el número total de final de juego de los estados.)

Cuando las probabilidades de golpear objetivos es diferente, creo que usted necesita para utilizar el mismo enfoque, pero utilizando el enfoque de esta cuestión para calcular la suma de los productos de todos los subconjuntos relevantes.

Usando la notación de un artículo de Wikipedia en primaria simétrica polinomios, y llamando a $\mathbf{T}_{!k} = \{p_i\}$ donde $i \in [1, N]$ y $i \neq k$:

$$P_{k} = p_{k} \cdot e_{X-1}(\mathbf{T}_{!k})$$ $$P_{!k} = e_{X}(\mathbf{T}_{!k})$$

Y la respuesta es: $$\mathbf{p}_{!k} = \frac{P_{!k}}{P_{k} + P_{!k}}$$

Editar Para comprobar que esta es la respuesta correcta, escribí un script de python que se ejecuta una prueba empírica del hecho al azar jugar el juego varias veces y se cuenta el número de juegos en los que $k$ fue golpeado:

from __future__ import division

from copy import copy
from itertools import combinations
from operator import mul
from functools import reduce, partial

import numpy as np

# Empirical approach
def play_game(t_list, k, X):
    if k >= len(t_list):
        raise ValueError("k cannot be greater than N")

    if X >= len(t_list):
        raise ValueError("X must be <= N")

    targ_probs = np.array(t_list) / sum(np.array(t_list))
    targ_inds = np.arange(0, len(targ_probs))
    targ_set = set()

    while True:
        c_target = np.random.choice(targ_inds, p=targ_probs)

        if c_target == k:
            return False

        targ_set.add(c_target)

        if len(targ_set) >= X:
            return True

def empirical_probability(n_games, t_list, k, X):
    game_outcomes = [play_game(t_list, k, X) for ii in range(n_games)]
    return sum(game_outcomes) / n_games

# Analytical approach
def elementary_symmetric_polynomial(m, t_set):
    return sum(map(partial(reduce, mul), combinations(t_set, m)))

def analytical_probability(t_list, k, X):
    t_k = t_list[k]
    t_set = np.array(t_list)
    t_set = t_set[[ii for ii in range(0, len(t_list)) if ii != k]]

    # All subsets of size X not containing k
    p_nk = elementary_symmetric_polynomial(X, t_set)

    # All subsets of size X - 1 not containing k
    p_k = t_k * elementary_symmetric_polynomial(X-1, t_set)

    return p_nk / (p_k + p_nk)

if __name__ == "__main__":
    n_games = 5000

    # Randomly generate a game set
    N = 6
    t_list = np.random.random((N,))
    t_list /= sum(t_list)

    empirical = [['X = '] + [str(X) for X in range(2, N-1)]]
    analytical = copy(empirical)
    for k in range(0, len(t_list)):
        ana_answers = ['k = {}'.format(k)]
        emp_answers = ['k = {}'.format(k)]
        for X in range(2, N-1):
            ana_answers.append(round(analytical_probability(t_list, k, X), 3))
            emp_answers.append(round(empirical_probability(n_games, t_list, k, X), 3))

        empirical.append(emp_answers)
        analytical.append(ana_answers)

    print("Empirical answers:")
    for row in empirical:
        print('\t'.join(str(x) for x in row))

    print("Analytical answers:")
    for row in analytical:
        print('\t'.join(str(x) for x in row))

La elección de $N = 6$ y ejecutar el juego 5000 veces, aquí es una carrera de los resultados:

p = [ 0.3305, 0.0350, 0.04995, 0.0831, 0.1503, 0.3509]
Empirical answers:
X =     2   3   4
k = 0   0.373   0.153   0.045
k = 1   0.916   0.833   0.721
k = 2   0.892   0.779   0.591
k = 3   0.813   0.642   0.407
k = 4   0.671   0.432   0.199
k = 5   0.348   0.141   0.041
Analytical answers:
X =     2   3   4
k = 0   0.397   0.218   0.108
k = 1   0.908   0.811   0.649
k = 2   0.871   0.741   0.542
k = 3   0.792   0.608   0.374
k = 4   0.652   0.416   0.225
k = 5   0.38    0.207   0.102

Creo que estas diferencias están dentro del ruido de la medición empírica. El algoritmo para la escuela primaria, el polinomio simétrico de cálculo de vino de esta pregunta.