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 w funkcji , w zależności od odpowiednich właściwości rozkładu ? $N$ $P$ $p_i$ $i$ $N$ $\sum_i p_i = 1$ $n \leq 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.

probability expected-value coupon-collector-problem

— a3nm
źródło

Myślę, że ten problem można określić jako: jaka jest oczekiwana liczba niezerowych wpisów w próbce z wielowymiarowego rozkładu hipergeometrycznego ?

— Kodiolog,

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$ $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})

$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: $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}

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

$\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$ $\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}

$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})

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

Zauważ też, że jeśli . $\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$

γ_{n} = \sum_{i = 1}^{k} P_{n, i} * i

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

— jakab922
źródło

Nazywasz prawdopodobieństwo, ale wydaje się, że określono ją jako sumę liczb całkowitych. Czy zapomniałeś coś podzielić?

P_{n, c}

$P_{n,c}$

— Kodiolog

Tak, chyba masz rację. Musisz podzielić przez , ale niestety nadal nie jest tak. Jeśli i robię podwójne liczenie w powyższej formule.

(\binom{N}{n})

$\binom{N}{n}$

E, F \in E_{c} (B)

$E, F \in E_{c}(B)$

E \cap F \neq \emptyset

$E \cap F \neq \emptyset$

— jakab922

Wygląda na to, że wzór można naprawić za pomocą metody sitowej. Opublikuję poprawkę później dzisiaj.

— jakab922,