Oczekiwana liczba wyraźnych kolorów podczas rysowania bez zamiany

Rozważ urnę zawierającą kulek o różnych kolorach, przy czym jest proporcją kulek koloru wśród kulek ( ). Rysuję kulek z urny bez zamiany i patrzę na liczbę różnych kolorów wśród narysowanych piłek. Jakie jest oczekiwanie \ gamma w funkcji n / N , w zależności od odpowiednich właściwości rozkładu \ mathbf {p} ?P p i i N ∑ i p i = 1 n ≤ $N$$P$$p_i$$i$$N$$\sum_i p_i = 1$$n \leq N$γ n / N $\gamma$$\gamma$$n/N$$\mathbf{p}$

Aby dać więcej wglądu: jeśli $N = P$ i $p_i = 1/P$ dla wszystkich $i$ , zawsze będę widzieć dokładnie $n$ kolorów, czyli $\gamma = P (n/N)$ . W przeciwnym razie można wykazać, że oczekiwanie $\gamma$ wynosi $>P(n/N)$ . Dla stałych $P$ i $N$ wydaje się, że współczynnik pomnożenia $n/N$ byłby maksymalny, gdy $\mathbf{p}$ jest jednolity; może oczekiwana liczba różnych kolorów będzie ograniczona w funkcji $n/N$ i np. entropia $\mathbf{p}$ ?

Wydaje się, że jest to związane z problemem kolektora kuponów, z tym wyjątkiem, że próbkowanie odbywa się bez zamiany, a rozkład kuponów nie jest jednolity.

Załóżmy, że masz kolorów gdzie . Niech oznaczają liczbę kul tak . Niech i pozwolić zapisywać zestaw, na który składa się z podzbiorów elementem . Niech oznacza liczbę sposobów, w których możemy wybrać elementów z powyższego zestawu, tak że liczba różnych kolorów w wybranym zestawie wynosi . Dla wzór jest prosty:k ≤ N b i i ∑ b i = N B = { b 1 , … , b k } E i ( B ) i B Q n , c n c c = $k$$k \leq N$$b_i$$i$$\sum b_i = N$$B = \{b_1, \ldots, b_k\}$$E_i(B)$$i$$B$$Q_{n, c}$$n$$c$$c = 1$

$$Q_{n, 1} = \sum_{E \in E_{1}(B)}\binom{\sum_{e \in E}e}{n}$$

Dla możemy policzyć zestawy kulek o rozmiarze które mają co najwyżej 2 kolory minus liczba zestawów, które mają dokładnie kolor:n $c = 2$$n$$1$

$$Q_{n,2} = \sum_{E \in E_{2}(B)}\binom{\sum_{e \in E}e}{n} - \binom{k - 1}{1}Q_{n, 1}$$

kc1c2kc1≤c2≤k ( k-c$\binom{k - 1}{1}$ to liczba sposobów dodania koloru do ustalonego koloru, dzięki czemu będziesz mieć 2 kolory, jeśli w sumie masz kolorów. Ogólna formuła jest taka, że ​​jeśli masz stałe kolory i chcesz z nich zrobić kolory, mając jednocześnie kolorów ( ) to . Teraz mamy wszystko, aby wyprowadzić ogólną formułę dla :$k$$c_1$$c_2$$k$$c_1 \leq c_2 \leq k$Qn,$\binom{k - c_1}{c_2 - c_1}$$Q_{n, c}$

$$Q_{n, c} = \sum_{E \in E_{c}(B)}\binom{\sum_{e \in E}e}{n} - \sum_{i = 1}^{c - 1}\binom{k - i}{c - i}Q_{n, i}$$

Prawdopodobieństwo, że będziesz mieć dokładnie kolorów, jeśli narysujesz kulek, wynosi:$c$$n$

$$P_{n, c} = Q_{n, c} / \binom{N}{n}$$

Zauważ też, że jeśli .y>$\binom{x}{y} = 0$$y > x$

Prawdopodobnie istnieją specjalne przypadki, w których formułę można uprościć. Tym razem nie zadałem sobie trudu znalezienia tych uproszczeń.

Oczekiwana wartość, której szukasz, liczby kolorów zależnych od to:$n$

$$\gamma_{n} = \sum_{i = 1}^{k} P_{n, i} * i$$