41J Blog

Archive for the ‘Uncategorized’ Category.

Ion314 die images

February 4, 2023, 9:33 pm

Category: Uncategorized | Comment

N choose K, with T targets. Probability of choosing at least one target

February 3, 2023, 7:13 am

Looking at n choose k, but you want to get at least one of a target t. For example you have a bag of blue marbles, which contains some number of red marbles. N is the total number of marbles in the bag. K is the number of marbles being chosen. T is the number of red marbles.

This is probably well known, but I worked through it a few different ways anyway…

First a simulation (C++):

#include <iostream>
#include <vector>

using namespace std;


int main(int argc,char **argv) {

  int n = 3000;
  int k = 50;
  int t = 30; // targets

  vector<int> items(n,0);

  for(int i=0;i<t;i++) {
    int itm=rand()%items.size();
    for(;items[itm] !=0;) itm = rand()%items.size();
    items[itm] = 1;
    //items[i] = 1;
  }

  //cout << "items: ";
  //for(int i=0;i<items.size();i++) cout << items[i] << " ";
  //cout << endl;

  vector<int> count(t,0);

  // rounds of choosing
  int rounds=100000;
  for(int j=0;j<rounds;j++) {
    cout << "round: " << j << endl;
    int tcount=0;

    vector<int> selected;
    for(int i=0;i<k;i++) {

      int itm = rand()%items.size();
      for(;std::count(selected.begin(), selected.end(), itm);) itm = rand()%items.size();
      selected.push_back(itm);
      //cout << "selected: " << itm << " " << items[itm] << endl;
      if(i%100000==0) cout << i << endl;
    }

    //count items on target
    for(int i=0;i<selected.size();i++) {
      if(items[selected[i]] == 1) tcount++;
    }
    cout << "tcount: " << tcount << endl;

    count[tcount]++;
  }

  int morezero=0;
  for(int i=0;i<t;i++) {
    if((count[i] > 0) || (i==0)) cout << i << " " << count[i] << endl;
    if(i>=1) morezero+=count[i];
  }
  cout << "One or more: " << morezero << endl;
  cout << "One or more fraction: " << (double)morezero/rounds << endl;
}

Next I calculated this by looking at the number of combinations calculating the fraction of combinations containing at least one target and total number of combinations:

from math import comb
import sys
def totalcomb(n, k, t):
        return comb(n,k)
def targetcomb(n, k, t):

        total = 0
        total += comb(t,k)
        for i in range(k-1,0,-1): #(i=k-1;i>0;i--)
                # print(t," ",i, ", ", n, " ", k-i)
                # Ways of choosing i items out of t. Multiply by
                total += comb(t,i)*comb(n-t,k-i)
        return total

n = int(sys.argv[1])
k = int(sys.argv[2])
t = int(sys.argv[3])
print (targetcomb(n,k,t)/totalcomb(n,k,t))
print (targetcomb(n,k,t))
print (totalcomb(n,k,t))

Then in terms of probability, using the probability that each draw does not contain a target:

from math import comb
import sys

def tprb(n, k, t):

        totalp = 1

        for i in range(0,k,1):
                p = 1 - (t / (n - i))
                totalp = totalp * p

        return 1-totalp

n = int(sys.argv[1])
k = int(sys.argv[2])
t = int(sys.argv[3])

print (tprb(n,k,t))

All approaches give the same answer, the last is the least computationally taxing…