Números esperados de cores distintas ao desenhar sem substituição

15

Considere uma urna contendo NN bolas de cores diferentes, com sendo a proporção de bolas de cor entre as bolas ( ). Eu desenho bolas da urna sem substituição e olho para o número de cores diferentes entre as bolas que foram sorteadas. Qual é a expectativa de em função de , dependendo das propriedades adequadas da distribuição ?P p i i N i p i = 1 n N γ γPpiiNipi=1nNγγn/Nn/Npp

Para dar uma ideia mais clara: Se e para todos os , em seguida, I irão ver sempre exactamente cores, isto é, . Caso contrário, pode ser demonstrado que a expectativa de é . Para e fixos , parece que o fator pelo qual multiplicar seria máximo quando for uniforme; talvez o número esperado de cores diferentes vistas seja delimitado em função de e, por exemplo, a entropia de ?N = P p i = 1 / P i n γ = P ( n / N ) γ >N=Ppi=1/Pinγ=P(n/N)γP(n/N)>P(n/N)PPNNn / N p n / N pn/Npn/Np

Isso parece estar relacionado ao problema do coletor de cupons, exceto que a amostragem é realizada sem substituição e a distribuição dos cupons não é uniforme.

a3nm
fonte
11
Penso que este problema pode ser afirmado como: qual é o número esperado de entradas diferentes de zero em uma amostra de uma distribuição hipergeométrica multivariada ?
Kodiologist

Respostas:

2

Suponha que você tem k cores, onde k N . Deixe- b i denotam o número de bolas de cores i tão Σ b i = N . Deixe B = { b 1 , ... , b k } e deixou E i ( B ) Notate o conjunto que consiste nos i subconjuntos elemento de B . Seja Q n , c denota o número de maneiras pelas quais podemos escolher nkk NbEuEubEu= NB = { b1 1, , Bk}EEu( B )EuBQn , cnelementos do conjunto acima, de modo que o número de cores diferentes no conjunto escolhido seja c . Para c = 1, a fórmula é simples:cc = 1

Q n , 1 = E E 1 ( B ) (e E en )

Qn,1=EE1(B)(eEen)

Para c = 2 , podemos contar conjuntos de bolas de tamanho n com no máximo 2 cores menos o número de conjuntos com exatamente 1 cor:c=2n1

Q n , 2 = E E 2 ( B ) (e E en ) - ( k-11 ) Qn,1

Qn,2=EE2(B)(eEen)(k11)Qn,1

( k-11)(k11) is the number of ways you can add a color to a fixed color such that you will have 2 colors if you have kk colors in total. The generic formula is if you have c1c1 fixed colors and you want to make c2c2 colors out of it while having kk colors in total(c1c2kc1c2k) is (kc1c2c1)(kc1c2c1). Now we have everything to derive the generic formula for Qn,cQn,c:

Qn,c=EEc(B)(eEen)c1i=1(kici)Qn,i

Qn,c=EEc(B)(eEen)i=1c1(kici)Qn,i

The probability that you will have exactly cc colors if you draw nn balls is:

Pn,c=Qn,c/(Nn)

Pn,c=Qn,c/(Nn)

Also note that (xy)=0(xy)=0 if y>xy>x.

Probably there are special cases where the formula can be simplified. I didn't bother to find those simplifications this time.

The expected value you're looking for the number of colors dependent on nn is the following:

γn=ki=1Pn,ii

γn=i=1kPn,ii
jakab922
fonte
4
You call Pn,cPn,c a probability, but you seem to have defined it as a sum of integers. Did you forget to divide by something?
Kodiologist
Yes, I guess you're right. You need to divide by (Nn)(Nn), but unfortunately it's still not right that way. If E,FEc(B)E,FEc(B) and EFEF I do doublecounting in the above formula.
jakab922
Seems like the formula can be fixed by using the sieve method. I will post a fix later today.
jakab922