¿Cómo se puede probar la siguiente identidad para [math] 0 <k \ le m [/ math]? [matemáticas] \ displaystyle \ sum_ {i = \ max (0, 2k-m)} ^ ki \ binom {k} {i} \ binom {mk} {ki} = \ frac {k ^ 2} {m} \ binom {m} {k} [/ matemáticas]

Hice esta pregunta y ahora puedo proporcionar una respuesta que me satisfaga. Para apreciar mejor lo que sigue, le sugiero que primero lea el hilo de comentarios sobre la respuesta del Usuario de Quora. De hecho, su respuesta es un requisito previo para seguir la mía.

Mi problema original podría formularse de la siguiente manera: supongamos que tengo una bolsa que contiene bolas [matemáticas] m [/ matemáticas], [matemáticas] k [/ matemáticas] de las cuales son blancas y [matemáticas] mk [/ matemáticas] negras. Si dibujo aleatoriamente [math] k [/ math] bolas, ¿cuál es el valor esperado para el número de bolas extraídas que son blancas? Solo consideré la lógica detrás de la respuesta [matemática] k ^ 2 / m [/ matemática] en el Método 2 de Shen como un argumento plausible. Incluso me había convencido de que el resultado era correcto. Pero estaba teniendo dificultades para demostrarlo. Yo mismo había construido el Método 1 de Shen; pero estaba teniendo dificultades para simplificar la expresión con la sumatoria a [math] k ^ 2 / m [/ math]. De ahí mi pregunta. Pensé que era irónico que, como prueba, Shen simplemente afirmara lo que estaba tratando de probar en primer lugar.

Con respecto a lo que me hace cauteloso acerca de la lógica intuitiva para la expectativa: Considere el caso [matemáticas] m = 4 [/ matemáticas] y [matemáticas] k = 2 [/ matemáticas]. La mitad del tiempo, la primera bola que saque será blanca, en cuyo caso solo hay 1 posibilidad en 3 de que la segunda bola sea blanca. 2 de cada 3 si el primero era negro. Entonces tengo una expectativa como [matemáticas] (1/2) (1 + 1/3) + (1/2) (0 + 2/3) = 1, [/ matemáticas], que es la respuesta correcta. ¡Pero estaba tomando en cuenta las probabilidades condicionales ! Y la lógica intuitiva parece ignorar esto. Realmente existen dificultades cuando se trata con este tipo de problema. Entonces quería una prueba más convincente. Afortunadamente, Yves Shen me obligó a pensar en uno:

Numere las bolas 1 a [matemáticas] m [/ matemáticas] y deje que las bolas numeradas 1 a [matemáticas] k [/ matemáticas] sean las blancas. Ahora cree una matriz con [math] m! [/ Math] filas en las que todas las filas son diferentes y cada fila corresponde a una de las permutaciones de [math] [1, m] [/ math] [math]. [/ Math ] El número de permutaciones para las cuales un valor dado aparece en una posición especificada en una permutación es [math] (m-1)! [/ Math], por lo que hay [math] (m-1)! [/ Math] de cada valor en cada columna, para un total [matemática] k ^ 2 (m-1)! [/ matemática] ocurrencias de valores en [matemática] [1, k] [/ matemática] en la primera [matemática] k [ / math] columnas. Una prueba para el dibujo puede verse como elegir una fila al azar y tomar la primera [matemática] k [/ matemática] de esa fila. Como el total de todas las filas es [matemática] k ^ 2 (m-1)! [/ Matemática], entonces el promedio de todas las filas [matemática] m! [/ Matemática] (igualmente probable) sale a [matemática] k ^ 2 / m. [/ Matemáticas]

Entonces, como Shen estaba tratando de convencerme, la expectativa en cada columna es [matemática] k / m [/ matemática] y, a largo plazo, realmente puede agregar esas expectativas por columna de forma independiente.

Tenga en cuenta también que usar el mismo número para el número de bolas extraídas y el número del color contado ([matemática] k [/ matemática]) no es importante. Si sacamos bolas [matemáticas] d [/ matemáticas], la expectativa es [matemáticas] dk / m [/ matemáticas] blancas.

Considere el siguiente problema:

Ponga m bolas etiquetadas de 1 a m en una bolsa. Saca k bolas de la bolsa (sin reemplazo). ¿Cuál es el número esperado de bolas extraídas de la bolsa con una etiqueta menor o igual a k?

Método 1: El número de formas de dibujar bolas i con etiqueta de 1 a k y bolas ki con etiqueta de k + 1 a m es [matemáticas] {k \ elegir i} {mk \ elegir ki} [/ matemáticas]. El número total de formas de dibujar k bolas es [matemática] m \ elegir k [/ matemática]. Por lo tanto, la probabilidad de sacar bolas i con etiqueta de 1 a k es [matemática] \ frac {{k \ elegir i} {mk \ elegir ki}} {m \ elegir k} [/ matemática]. Por lo tanto, el número esperado de bolas con etiquetas de 1 a k es

[matemáticas] \ sum_ {i = \ max (0,2k-m)} ^ ki {k \ elige i} {mk \ elige ki} {m \ elige k} ^ {- 1}. [/ matemática]

Tenga en cuenta que el límite para i en la suma es asegurarse de que solo contamos las formas posibles, es decir, las formas en que ki está entre 0 y mk.

Método 2: Para cada bola extraída de la bolsa, la probabilidad incondicional de que su etiqueta sea menor o igual a k es [matemática] \ frac {k} {m} [/ matemática]. Por lo tanto, por la aditividad de la expectativa, el número esperado es [matemáticas] \ frac {k ^ 2} {m}. [/matemáticas]

La equiparación de los resultados anteriores derivados de los dos métodos da la identidad deseada.

  1. Suponga que 2k-m <0.
  2. Extiende los coeficientes binomiales.
  3. Haga algunas operaciones aritméticas y use una suma conocida para obtener el resultado deseado
  4. Suponga que 2k-m> 0
  5. Realice alguna sustitución para que la suma se ejecute desde 0. Si la propiedad se mantiene, esta expresión debería ser equivalente a la que tenía después del paso 1.