Número esperado de veces que se elige una palabra de un vocabulario dado cuando las palabras se agrupan

Question

Dos jugadores (jugador C y el jugador G) están jugando un (modificado) palabra juego de adivinanzas. Ambos jugadores comparten el mismo vocabulario $V$ y palabras en $V$ se agrupan en $K$ papeleras, que se denota como $b_1$, $b_2$, ..., $b_{K}$. Además, sabemos que $b_{i} \subset V$ e $\cup_{i=1}^{K} b_i = V$. Nota: aquí no tenemos $b_i \cap b_j = \emptyset$ para $i \neq j$.

El juego protocolo se describe de la siguiente manera:

1. El jugador C uniformemente elige una palabra $w$ a partir del vocabulario $V$. Jugador G no sé que palabra $w$ es.

2. Jugador G elige una bandeja y le pide Jugador C si su palabra elegida $w$ está en la papelera. Si es así, el juego termina. De lo contrario, el Jugador G se elija otro bin.

Preguntas: ¿Cuál es la mejor reciclaje de elegir el orden y lo que se espera que el número de veces de la elección de la papelera de reciclaje, de acuerdo a la mejor posible orden?

Ejemplo:

Supongamos que tenemos un vocabulario consta de diez palabras $V = \{w_1, w_2, ..., w_{10} \}$ y tres tolvas $b_1 = \{w_1, w_2, ..., w_5\}$, $b_2 = \{w_6, w_7 \}$, e $b_3 = \{w_8, w_9, w_{10} \}$.

Una posible bin elegir el orden es $b_1 \rightarrow b_3 \rightarrow b_2$ y el número esperado de veces de elegir el reciclaje es $\frac{1}{2}*1 + \frac{1}{2}*\frac{3}{5}*2 + \frac{1}{2}*\frac{2}{5}*\frac{2}{2}*3 = 1.7$. Sospecho que esta es la mejor reciclaje de elegir el orden, pero ¿cómo podemos demostrar este resultado?

Gracias.

Nota

Una pregunta relacionada (la que tiene más no la superposición de las limitaciones de los contenedores) se pregunta en MO y en su comentario, el usuario @DavidG.La cigüeña le da una buena respuesta (una intuitiva prueba de mejores pedido) para el caso de cuando los recipientes no se superponen.

Answer 1

No una respuesta, pero demasiado largo para un comentario.

Para un determinado ordenamiento de los contenedores, que permite decir $a_{1}, a_{2}, ..., a_{K}$ (que es una permutación de la $b_i$'s), vamos a $f(w)$ ser el momento de la detección de la palabra $w$. A continuación, $f(w) = j$, es decir, será descubierto durante la $j$th bin, iff $w \in c_j$ donde $c_j = a_{j} - \bigcup^{j-1}_{i=1} a_i$. I. e. $c_j$ son las nuevas palabras introducidas por bin $a_j$.

Para calcular el número esperado de vueltas, la suma de todos los descubrimiento veces $f(w)$ y luego se divide por el número de palabras. Por lo que el número esperado se minimiza cuando se $\sum_{w \in V} f(w)$ es mínimo.

En la OP del ejemplo original de todos los $b_i$'s son distintos, por lo que es bastante claro que $\sum_{w \in V} f(w)$ es minimizado cuando se asigna el mayor número de ellos como $1$s, entonces el mayor número de ellos como $2$s, etc. En este ejemplo, la previsión del número de vueltas $= {5\times 1 + 3 \times 2 + 2 \times 3 \over 10} = 1.7$.

Cuando la $b_i$'s no son disjuntos, entonces, como se muestra por la excelente ejemplo de @Jens en los comentarios, los codiciosos, la estrategia puede ser subóptima - asigna los números de $1,1,1,1,1,1,2,2,3,3$ , para un total de $16$ cuando la estrategia óptima asigna los números de $1,1,1,1,1,2,2,2,2,2$ , para un total de $15$.