Quelle est la distribution de la cardinalité de l'intersection d'échantillons aléatoires indépendants sans remplacement?

10

S estcertain ensemble avecnN éléments, eta1,a2,...,am sont des entiers positifs fixes inférieurs ou égaux àn .

Avec les éléments de S étant également susceptible, m échantillons L1,L2,...,Lm sont séparément et indépendamment tirées S sans remplacement, dont la taille est a1,a2,...,am , respectivement.

|L1L2 ... Lm|{0,1,...,min{a1,a2,...,am}}

Eau fraîche
la source
Je peux vous fournir une recette pour le calculer récursivement mais je ne connais pas de solution sous forme fermée. Cela suffirait-il ou voulez-vous une expression explicite de la fonction de distribution étant donné a1,,am et n ?
Bridgeburners
@Bridgeburners Une recette serait bien, au moins elle fournirait une méthode / un moyen d'attaquer ce problème et les problèmes associés.
llrs

Réponses:

3

Voici une autre approche, qui n'implique pas de récursivité. Cependant, il utilise toujours des sommes et des produits dont les longueurs dépendent des paramètres. Je vais d'abord donner l'expression, puis expliquer.

Nous avons

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

EDIT: À la fin de l'écriture de tout cela, j'ai réalisé que nous pouvons consolider un peu l'expression ci-dessus en combinant les coefficients binomiaux en probabilités hypergéométriques et coefficients trinomiaux. Pour ce que cela vaut, l'expression révisée est Ici est une variable aléatoire hypergéométrique où tirages sont tirés d'une population de taille ayant états de réussite.

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

Dérivation

Obtenons une notation afin de rendre les arguments combinatoires un peu plus faciles à suivre (espérons-le). Tout au long, nous considérons et fixes. Nous utiliserons pour désigner la collection de -tuples ordonnés , où chaque , satisfaisantSa1,,amC(I)m(L1,,Lm)LiS

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

Nous utiliserons également pour une collection identique sauf que nous avons besoin de au lieu de l'égalité.C(I)L1LmI

Une observation clé est que est relativement facile à compter. En effet, la condition est équivalente à pour tous les , donc dans un sens, cela supprime les interactions entre les différentes valeurs . Pour chaque , le nombre de satisfaisant à l'exigence est , puisque nous pouvons construire un tel en choisissant un sous-ensemble de de taillepuis l'union avec . Il s'ensuit que C(I)L1LmILiIiiiLi(|S||I|ai|I|)LiSIai|I|I

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

Maintenant, notre probabilité d'origine peut être exprimée via le comme suit: C

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

Nous pouvons apporter ici deux simplifications tout de suite. Premièrement, le dénominateur est le même que Deuxièmement, un argument de permutation montre quene dépend que de travers la cardinalité. Puisqu'il existe sous-ensembles de ayant la cardinalité , il s'ensuit que où est un sous-ensemble fixe arbitraire de ayant une cardinalité

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

En prenant du recul, nous avons maintenant réduit le problème à montrer que

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

Soit les sous-ensembles distincts de formés en ajoutant exactement un élément à . Alors (Cela signifie simplement que si , alors contient mais ne contient pas non plus d'élément supplémentaire.) Nous avons maintenant transformé le problème de comptage un problème de comptage , que nous savons mieux gérer. Plus précisément, nous avons J1,,JnkSI0

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

Nous pouvons appliquer l'inclusion-exclusion pour gérer la taille de l'expression d'union ci-dessus. La relation cruciale ici est que, pour tout , En effet, si contient un certain nombre de , alors il contient également leur union. Nous notons également que l'ensemble a la taille. Par conséquent 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).
(Nous pouvons restreindre les valeurs ici puisque le produit des coefficients binomiaux est nul à moins que pour tout , c'est-à-dire .)jjalkljmin(a1,,am)k

Enfin, en substituant l'expression à la fin à l'équation pourci-dessus et en consolidant la somme, on obtient comme revendiqué.|C(I0)|

|C(I0)|=j=0min(a1,,am)k(1)j(nkj)l=1n(njkaljk)
Jason
la source
+1 pour tous les efforts et la solution, mais je vais devoir peaufiner mes calculs pour comprendre la plupart de cela (et l'autre réponse). Merci
llrs
4

Je ne connais pas de méthode analytique pour résoudre ce problème, mais voici une méthode récursive pour calculer le résultat.

Pour vous choisissez éléments parmi ont été choisis auparavant. La probabilité de choisir éléments qui se croisent avec dans votre deuxième tracé est donnée par la distribution hypergéométrique:m=2a2n, a1kmin{a1,a2}L1

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

On peut appeler le résultatNous pouvons utiliser la même logique pour trouver où est la cardinalité de l'intersection de trois échantillons. Alors,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).

Trouvez ceci pour chaque . Ce dernier calcul n'est pas numériquement difficile, car est simplement le résultat du calcul précédent et est une invocation de la distribution hypergéométrique.k{0,1,2,,min(a1,a2,a3)}P(b2=ln,a1,a2)P(b3=kn,b2=l,a3)

En général, pour trouver vous pouvez appliquer les formules récursives suivantes: for and ce qui revient à dire queP(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.

Le voici en 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
Brûleurs
la source
Merci pour votre solution et votre code. J'attends d'autres réponses (si elles viennent) avant d'attribuer la prime.
llrs