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


10

n N 1 , 2 , . . . , a m nS jest zestawem z elementami , a są stałymi dodatnimi liczbami całkowitymi mniejszymi lub równymi .nNa1,a2,...,amn

Ponieważ elementy są równie prawdopodobne, próbek jest osobno i niezależnie od bez zamiany, których wielkość wynosi odpowiednio .SmL1,L2,...,Lm1 , 2 , . . . , a mSa1,a2,...,am

przecięcia próbekma, ogólnie rzecz biorąc, wsparcie równe , ale którą dystrybucję stosuje?|L1L2 ... Lm|{0,1,...,min{a1,a2,...,am}}


Mogę podać przepis na obliczanie go rekurencyjnie, ale nie znam rozwiązania w formie zamkniętej. Czy to wystarczy, czy może chcesz wyrazić wyrażenie funkcji dystrybucji z a1,,am i n ?
Bridgeburners,

@Bridgeburners Przepis byłby fajny, przynajmniej zapewniłby jakąś metodę / sposób ataku tego problemu i pokrewnych.
llrs

Odpowiedzi:


3

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

P(|L1L2Lm|=k)=(nk)i=1n(nai)j=0min(a1,,am)k(1)j(nkj)l=1n(njkaljk).

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.

j=0min(a1,,am)k(1)j(nj,k,njk)l=1nP(Hyp(n,j+k,al)=j+k).
Hyp(n,j+k,al)alnj+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ącySa1,,amC(I)m(L1,,Lm)LiS

  • |Li|=ai ; i
  • L1Lm=I .

Użyjemy również dla kolekcji identycznej, z tym że wymagamy zamiast równości.C(I)L1LmI

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 C(I)L1LmILiIiiiLi(|S||I|ai|I|)LiSIai|I|I

|C(I)|=i=1n(|S||I|ai|I|).

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

P(|L1L2Lm|=k)=I:|I|=k|C(I)|all IS|C(I)|.

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

|C()|=i=1n(|S|ai)=i=1n(nai).
|C(I)|I|I|(nk)Sk
I:|I|=k|C(I)|=(nk)|C(I0)|,
I0Sk .

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

|C(I0)|=j=0min(a1,,am)k(1)j(nkj)l=1n(njkaljk).

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 J1,,JnkSI0

C(I0)=C(I0)(i=1nkC(Ji)).
L1Lm=I0L1LmI0CC
|C(I0)|=|C(I0)||i=1nkC(Ji)|=l=1n(nkalk)|i=1nkC(Ji)|.

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 I{1,,nk}

iIC(Ji)=C(iIJi).
L1LmJiiIJi|I0|+|I|=k+|I|
|i=1nkC(Ji)|=I{1,,nk}(1)|I|1|iIC(Ji)|=j=1nkI:|I|=j(1)j1l=1n(njkaljk)=j=1nk(1)j1(nkj)l=1n(njkaljk).
(Możemy tutaj ograniczyć wartości , ponieważ iloczyn współczynników dwumianowych wynosi zero, chyba że dla wszystkich , tj. .)jjalkljmin(a1,,am)k

Na koniec, podstawiając wyrażenie na końcu do równania napowyżej i konsolidując sumę, otrzymujemy jak twierdzono.|C(I0)|

|C(I0)|=j=0min(a1,,am)k(1)j(nkj)l=1n(njkaljk)

+1 za cały wysiłek i rozwiązanie, ale muszę dopracować matematykę, aby zrozumieć większość tego (i drugiej odpowiedzi). Dzięki
llrs

4

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=2a2n, a1kmin{a1,a2}L1

P(kn,a1,a2)=(a1k)(na1a2k)(na2).

Możemy nazwać wynikMożemy użyć tej samej logiki do znalezienia gdzie jest licznością przecięcia trzech próbek. Następnie,b2.P(b3=kn,b2,a3),b3

P(b3=k)=l=0min(a1,a2)P(b3=kn,b2=l,a3)P(b2=ln,a1,a2).

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{0,1,2,,min(a1,a2,a3)}P(b2=ln,a1,a2)P(b3=kn,b2=l,a3)

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

P(bi=k)=l=0min(a1,a2,,ai1)P(bi=kn,bi1=l,ai)P(bi1=l),
P(bi=kn,bi1=l,ai)=(lk)(nlaik)(nai),
i{2,3,,m},
P(b1)=δa1b1,
b1=a1.

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

Dziękujemy za Twoje rozwiązanie i kod. Przed przyznaniem nagrody czekam na inne odpowiedzi (jeśli się pojawią).
llrs 8'18
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.