Hallar la probabilidad de tener bolas k rojo después de días días

Question

Es una pregunta de la entrevista..

Inicialmente hay n bolas blancas. Cada día se le permite tomar una pelota. Si la bola en la mano es de color blanco, sustituir por bola roja. Si es de color rojo, poner la pelota en la bolsa sin hacer nada. La cuestión es encontrar la probabilidad de tener k bolas de color rojo después de d días.Dar la solución general

Empecé con la fabricación de un árbol binario.. inicialmente en el 1er día tenemos n bolas blancas, cuando tomamos 1 balón y aplicar la regla obtenemos 1 bola roja y (n-1) bolas blancas en el segundo día de recogida de bolas 1, podría ser de color blanco o rojo. si tomamos blanco nos quedamos con 2red y (n-2) bolas blancas de lo contrario, 1 rojo y (n-1) bolas blancas. estos dos nodos de nuevo cada uno, tienen dos hijos cada uno, para el día 3.. 1 con 3 bolas rojas y (n-3) bolas blancas , otro con 2 bolas rojas y (n-2)bolas blancas y así sucesivamente

Pero esto es un directo de la fórmula recursiva, es que hay una solución mejor? Creo que puede ser resuelto con programación dinámica, pero soy incapaz de conectar con programación dinámica con la probabilidad. alguna idea de cómo hacer esto ?

También alguien me puede ayudar con la forma de la probabilidad se calcula que en esta pregunta?

La última, alguien Puede darme un buen recurso para estudiar la probabilidad de programación basado en preguntas?

Answer 1

Hmm, resistente para una pregunta de la entrevista. Condición de la probabilidad de ser terminado en el d+1-ésimo dibujar ya que tiene exactamente k-1 bolas rojas en la bolsa. La probabilidad de terminar el próximo sorteo es $1-\frac{k-1}{n}$. Ahora sólo tenemos que encontrar la probabilidad de tener exactamente k-1 bolas rojas después d empates y multiplicar.

Este es idéntica a la probabilidad de sacar exactamente k-1 diferentes bolas de una urna con n bolas después d dibuja con la sustitución. La probabilidad de dibujo en la mayoría de los k-1 diferentes bolas debe ser dado por $\frac{(k-1)^d}{n^d}$.

Dibujo exactamente k-1 es el dado por la resta de la oportunidad de dibujo en la mayoría de los k-2, por lo que tenemos $\frac{(k-1)^d}{n^d}-\frac{(k-2)^d}{n^d}$. Así, obtenemos un total de probabilidad de

$(1-\frac{k-1}{n})(\frac{(k-1)^d}{n^d}-\frac{(k-2)^d}{n^d})$. Tenga en cuenta que esto sólo vale para $d>=k$. Yo también podría haber cometido un error a lo largo del camino. También hay probablemente una manera más rápida de hacer esto. Y uno podría ser capaz de simplificar el resultado. Podría ayudar de todos modos.

Answer 2

Esta es una cadena de Markov de ejercicio. Considere el vector $P_{d} = (p_d^0, p_d^1, \ldots, p_d^n) \in [0,1]^{n+1}$ donde $p_d^k$ es la probabilidad de que no son exactamente $k$ bola roja en la bolsa después de $d$ sorteos. Ahora, desde la $p_{d+1}^{k} = \frac{n-(k-1)}{n}p_{d}^{k-1} + \frac{k}{n}p_{d}^{k}$ uno puede encontrar inmediatamente una matriz de $A \in M_{{n+1} \times {n+1}}$ tal que $P_{d+1}=A \cdot P_d$ y resolver el problema mediante el cálculo de $P_d = A^d P_0$$P_0=(1,0,0,\ldots,0)$.

En conclusión, un algoritmo para calcular $p_d^k$ con la complejidad de la $\mathcal{O}(pk)$ es la siguiente.

1. Definir $(p_0^0, p_0^1, \ldots, p_0^k)=(1,0,\ldots,0)$.
2. Calcular $(p_{j+1}^0, p_{j+1}^1, \ldots, p_{j+1}^k)$ usando la fórmula de $p_{j+1}^{i} = \frac{n-(i-1)}{n}p_{j}^{i-1} + \frac{i}{n}p_{i}^{j}$$j=0, \ldots, d-1$.
3. El resultado está dado por $p^k_d$.

Answer 3

Creo que tienes que configurar este problema utilizando Cadenas de Markov de la teoría, que está familiarizado con ella?

El sistema que estamos considerando es un sistema discreto que puede ser en cualquiera de los (n+1) estados

{ [0], [1], [2], ... ,[n] }

donde [j] es el estado con j las bolas de color rojo. El sistema se inicia desde el estado [0] y evoluciona a lo largo del tiempo con una matriz de transición, (probabilidad de ir del estado i al estado j)

$T_{ij}=\frac{n-i}{n}$ si j=i+i

$T_{ij}=\frac{i}{n}$ si j=i

$T_{ij}=0$ lo contrario

Ahora esta cadena de Markov es estacionaria y se conoce la distribución inicial (que es una función delta alcanzó su punto máximo en el estado [0])

Usted puede obtener la distribución en un tiempo futuro k (en este caso usted está interesado en el tiempo k, lo que significa que después de k pasos) multiplicando la matriz de transición por sí misma k veces y luego multiplicando el resultado tiempos de la distribución inicial

$p_k=T^k p_0$

donde $p_k$ es el vector de probabilidades (indexados por el estado) en el momento k y $p_0$ es el vector de probabilidades en el tiempo 0 (función delta en 0).

Ahora, dado que el producto de una matriz fo ($T^k$) veces en un vector ($p_0$) que tiene un 1 en el primer elemento y 0 en todas las demás (su función delta) es sólo la primera columna de la matriz y ya que usted está interesado en la probabilidad de $d$ bolas de color rojo, a continuación, lo que se busca es el elemento de la matriz $(T^k)_{d+1,0}$

He puesto d+1 porque tomamos [0] bolas para ser el primer elemento. Así que todo lo que tienes que hacer es hacer la matriz producto y buscar ese elemento. Posiblemente, debido a que la matriz es casi diagonal, usted encontrará que usted puede calcular analíticamente, darle una oportunidad