Jaki jest rozkład liczności przecięcia niezależnych losowych próbek bez zamiany?

n ∈ N 1 , 2 , . . . , a m$S$ jest zestawem z elementami , a są stałymi dodatnimi liczbami całkowitymi mniejszymi lub równymi .$n\in\mathbb{N}$$a_1,a_2,...,a_m$$n$

Ponieważ elementy są równie prawdopodobne, próbek jest osobno i niezależnie od bez zamiany, których wielkość wynosi odpowiednio .$S$$m$$L_1, L_2,...,L_m$1 , 2 , . . . , a $S$$a_1,a_2,...,a_m$

przecięcia próbekma, ogólnie rzecz biorąc, wsparcie równe , ale którą dystrybucję stosuje?$\left|L_1\cap L_2\cap\ ...\ \cap L_m\right|$$\{0,1,...,\min\{a_1,a_2,...,a_m\}\}$

Oto inne podejście, które nie wymaga rekurencji. Nadal jednak wykorzystuje sumy i produkty, których długości zależą od parametrów. Najpierw dam wyraz, a potem wyjaśnię.

Mamy

$$\begin{align} P &\bigl( | L_{1} \cap L_{2} \cap \cdots \cap L_{m} | = k \bigr) \\ &= \frac{\binom{n}{k}}{\prod_{i = 1}^{n} \binom{n}{a_{i}}} \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} -j - k}. \end{align}$$

EDYCJA: Pod koniec pisania tego wszystkiego zdałem sobie sprawę, że możemy nieco skonsolidować powyższe wyrażenie, łącząc współczynniki dwumianowe w prawdopodobieństwa hipergeometryczne i współczynniki trójmianowe. Jeśli chodzi o wartość, zmienione wyrażenie to Tutaj jest losową zmienną hipergeometryczną, w której losowania są pobierane z populacji o wielkości mającej stanów powodzenia.

$$\begin{equation} \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n}{j, k, n - j - k} \prod_{l = 1}^{n} P( \text{Hyp}(n, j + k, a_{l}) = j + k). \end{equation}$$ $\text{Hyp}(n, j + k, a_{l})$$a_{l}$$n$$j + k$

---

Pochodzenie

Zdobądźmy notację, aby nieco łatwiej śledzić argumenty kombinatoryczne (miejmy nadzieję). Przez cały czas uważamy i naprawione. Użyjemy do oznaczenia kolekcji uporządkowanych -tuple , gdzie każdy , spełniający$S$$a_{1}, \ldots, a_{m}$$\mathcal{C}(I)$$m$$(L_{1}, \ldots, L_{m})$$L_{i} \subseteq S$

• $|L_{i}| = a_{i}$ ; i
• $L_{1} \cap \cdots \cap L_{m} = I$ .

Użyjemy również dla kolekcji identycznej, z tym że wymagamy zamiast równości.$\mathcal{C}'(I)$$L_{1} \cap \cdots \cap L_{m} \supseteq I$

Kluczową obserwacją jest to, że można stosunkowo łatwo policzyć. Jest tak, ponieważ warunek jest równoważny dla wszystkich , więc w pewnym sensie usuwa interakcje między różnymi wartościami . Dla każdego liczba spełniająca wymagania wynosi , ponieważ możemy zbudować taki , wybierając podzbiór o rozmiarzea następnie unioning z . Wynika, że $\mathcal{C}'(I)$$L_{1} \cap \cdots \cap L_{m} \supseteq I$$L_{i} \supseteq I$$i$$i$$i$$L_{i}$$\binom{|S| - |I|}{a_{i} - |I|}$$L_{i}$$S \setminus I$$a_{i} - |I|$$I$

$$\begin{equation} | \mathcal{C}'(I) | = \prod_{i = 1}^{n} \binom{|S| - |I|}{a_{i} - |I|}. \end{equation}$$

---

Teraz nasze pierwotne prawdopodobieństwo można wyrazić za pomocą w następujący sposób: $\mathcal{C}$

$$\begin{equation} P \bigl( | L_{1} \cap L_{2} \cap \cdots \cap L_{m} | = k \bigr) = \frac{ \sum_{I : |I| = k} | \mathcal{C}(I) | } { \sum_{\text{all $I \subseteq S$}} | \mathcal{C}(I) | }. \end{equation}$$

Możemy od razu wprowadzić dwa uproszczenia. Po pierwsze, mianownik jest taki sam jak Po drugie, argument permutacji pokazuje, żezależy tylko od poprzez liczność. Ponieważ istnieje podzbiory o liczności wynika, że gdzie jest arbitralnym, stałym podzbiorem o liczności

$$\begin{equation} | \mathcal{C}'(\emptyset) | = \prod_{i = 1}^{n} \binom{|S|}{a_{i}} = \prod_{i = 1}^{n} \binom{n}{a_{i}}. \end{equation}$$ $| \mathcal{C}(I) |$$I$$|I|$$\binom{n}{k}$$S$$k$ $$\begin{equation} \sum_{I : |I| = k} | \mathcal{C}(I) | = \binom{n}{k} | \mathcal{C}(I_{0}) |, \end{equation}$$ $I_{0}$$S$$k$ .

Cofając się o krok, zredukowaliśmy problem do pokazania, że

$$\begin{equation} | \mathcal{C}(I_{0}) | = \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k}. \end{equation}$$

---

Niech będą odrębnymi podzbiorami utworzonymi przez dodanie dokładnie jednego elementu do . Następnie (To po prostu mówi, że jeśli , to zawiera ale również nie zawiera żadnego dodatkowego elementu.) Przekształciliśmy teraz problem zliczania problem zliczania , o którym wiemy więcej, jak sobie z tym poradzić. Mówiąc dokładniej, mamy $J_{1}, \ldots, J_{n - k}$$S$$I_{0}$

$$\begin{equation} \mathcal{C}(I_{0}) = \mathcal{C}'(I_{0}) \setminus \biggl( \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr). \end{equation}$$ $L_{1} \cap \cdots \cap L_{m} = I_{0}$$L_{1} \cap \cdots \cap L_{m}$$I_{0}$$\mathcal{C}$$\mathcal{C}'$ $$\begin{equation} | \mathcal{C}(I_{0}) | = | \mathcal{C}'(I_{0}) | - \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr| = \prod_{l = 1}^{n} \binom{n - k}{a_{l} - k} - \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr|. \end{equation}$$

---

Możemy zastosować wykluczenie włączenia, aby obsłużyć wielkość wyrażenia unii powyżej. Kluczową zależnością jest tutaj to, że dla każdego niepustego , Dzieje się tak, ponieważ jeśli zawiera pewną liczbę , to również zawiera ich związek. Zauważamy również, że zestaw ma rozmiar. W związku z tym $\mathcal{I} \subseteq \{ 1, \ldots, n - k \}$

$$\begin{equation} \bigcap_{i \in \mathcal{I}} \mathcal{C}'(J_{i}) = \mathcal{C}' \biggl( \bigcup_{i \in \mathcal{I}} J_{i} \biggr). \end{equation}$$ $L_{1} \cap \cdots \cap L_{m}$$J_{i}$$\bigcup_{i \in \mathcal{I}} J_{i}$$|I_{0}| + |\mathcal{I}| = k + |\mathcal{I}|$ $$\begin{align} \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr| &= \sum_{\emptyset \neq \mathcal{I} \subseteq \{ 1, \ldots, n - k \}} (-1)^{| \mathcal{I} | - 1} \biggl| \bigcap_{i \in \mathcal{I}} \mathcal{C}'(J_{i}) \biggr| \\ &= \sum_{j = 1}^{n - k} \sum_{\mathcal{I} : |\mathcal{I}| = j} (-1)^{j - 1} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k} \\ &= \sum_{j = 1}^{n - k} (-1)^{j - 1} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k}. \end{align}$$ (Możemy tutaj ograniczyć wartości , ponieważ iloczyn współczynników dwumianowych wynosi zero, chyba że dla wszystkich , tj. .)$j$$j \leq a_{l} - k$$l$$j \leq \min(a_{1}, \ldots, a_{m}) - k$

---

Na koniec, podstawiając wyrażenie na końcu do równania napowyżej i konsolidując sumę, otrzymujemy jak twierdzono.$| \mathcal{C}(I_{0}) |$

$$\begin{equation} | \mathcal{C}(I_{0}) | = \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k} \end{equation}$$

Nie znam analitycznego sposobu rozwiązania tego problemu, ale oto rekurencyjny sposób obliczenia wyniku.

Dla wybierasz elementy spośród z których wybrano wcześniej. Prawdopodobieństwo wybrania elementów , które przecinają się z w drugim losowaniu, wynika z rozkładu hipergeometrycznego:$m=2$$a_2$$n,$ $a_1$$k \le \min\{a_1,a_2\}$$L_1$

$$P(k \mid n, a_1, a_2) = \frac{ {a_1 \choose k} {n - a_1 \choose a_2 - k} } {n \choose a_2}.$$

Możemy nazwać wynikMożemy użyć tej samej logiki do znalezienia gdzie jest licznością przecięcia trzech próbek. Następnie,$b_2.$$P(b_3 = k \mid n, b_2, a_3),$$b_3$

$$P(b_3=k) = \sum_{l=0}^{\min(a_1,a_2)} P(b_3=k \mid n, b_2=l, a_3) P(b_2 =l \mid n, a_1, a_2).$$

Znajdź to dla każdego . To ostatnie obliczenie nie jest trudne numerycznie, ponieważ jest po prostu wynikiem poprzedniego obliczenia, a jest wywołaniem rozkład hipergeometryczny.$k \in \{0, 1, 2, \dots, \min(a_1,a_2,a_3)\}$$P(b_2 = l \mid n, a_1, a_2)$$P(b_3 = k \mid n, b_2=l, a_3)$

Ogólnie, aby znaleźć , możesz zastosować następujące formuły rekurencyjne: dla i co oznacza, że$P(b_m)$

$$P(b_i=k) = \sum_{l=0}^{\min(a_1, a_2, \dots, a_{i-1})} P(b_i = k \mid n, b_{i-1}=l, a_i) P(b_{i-1}=l),$$ $$P(b_i = k \mid n, b_{i-1}=l, a_i) = \frac{{l \choose k} {n-l \choose a_i - k}} {n \choose a_i},$$ $i \in \{2, 3, \dots, m\},$ $$P(b_1) = \delta_{a_1 b_1},$$ $b_1 = a_1.$

Oto w R:

hypergeom <- function(k, n, K, N) choose(K, k) * choose(N-K, n-k) / choose(N, n)

#recursive function for getting P(b_i) given P(b_{i-1})
PNext <- function(n, PPrev, ai, upperBound) {
  l <- seq(0, upperBound, by=1)
  newUpperBound <- min(ai, upperBound)
  kVals <- seq(0, newUpperBound, by=1)
  PConditional <- lapply(kVals, function(k) {
    hypergeom(k, ai, l, n)
  })
  PMarginal <- unlist(lapply(PConditional, function(p) sum(p * PPrev) ))
  PMarginal
}

#loop for solving P(b_m)
P <- function(n, A, m) {
  P1 <- c(rep(0, A[1]), 1)
  if (m==1) {
    return(P1)
  } else {
    upperBound <- A[1]
    P <- P1
    for (i in 2:m) {
      P <- PNext(n, P, A[i], upperBound)
      upperBound <- min(A[i], upperBound)
    }
    return(P)
  }
}

#Example
n <- 10
m <- 5
A <- sample(4:8, m, replace=TRUE)
#[1] 6 8 8 8 5

round(P(n, A, m), 4)
#[1] 0.1106 0.3865 0.3716 0.1191 0.0119 0.0003
#These are the probabilities ordered from 0 to 5, which is the minimum of A