Algorithm for balancing samples in real time Let's say I'm conducting a survey with a desired number of participants (n = 100). The people who take my survey can either be male or female and I'd like there to be a 50/50 balance along males and females who take my survey.
If I knew that there were exactly twice as many females as males in this population, I could simply randomly turn away half the females that line up to take my survey. However, what if I don't know what the actual proportion of males and females are in the population? How do I decide with what probability to turn away either males/females?
One trivial solution is to accept some fraction of the participants (say n/10), and compute the breakdown in proportion. I then inversely weight the probability of selecting males or females in the next n/10 participants by their representation in the preceding slice.
But I'm wondering if there's an optimal approach that guarantees convergence at the desired level of representation (e.g. half males / half females) for a given sample size (n) as quickly as possible?
 A: Include people with 100% probability until their category fills up. Keep track of the total number seen so far per category. Then, on seeing the k'th person in a full category, we include it in our sample with probability target/k.
E.g. We want 50 men and 50 women. On seeing the 51st man, we include him in our sample 50/51 of the time (replacing a random member of the sample). The next man gets included 50/52 of the time, and so on. When we include someone in the sample past our target, we bump a random person from the sample.
At the end, each person that could be in our sample is in our sample with probability (sample)/(category population).
Let's say our target sample size per category is r. After we see k people for k >= r, each of the k people we've seen should be in our population with probability r/k. It's easy to show this is true for k=r, and a simple proof by induction shows this continues to be true as k grows. Basically, at each step an element is not kicked out of the pool with probability 1 - (r/(k+1)) * (1/r) = 1 - 1/(k+1) = k/(k+1). Thus the probability of an element surviving for the time-to-date goes to r/k * k/(k+1) = r/(k+1).
A: Looks like you don't need a sample that's representative of the population. You just need a sample that contains an equal number of both genders. If that is what it is, from the survey you have collected over the period of time, you could simply see the class with the least count and randomly select as many observations of the other class.
Sample size (n) unknown:
For example, your survey has 40 females and 45 males. Randomly select 40 males from the 45. This will give you a sample (since the population was not surveyed) that has an equal number of males and females.
Sample size (n) known:
If you know the size of the sample (n), then you can randomly pick half the sample size from both the genders provided the survey has at least as many observations from each of the genders as the half of sample size.
For example, n = 100 and you need 50 males and 50 females.
If the survey has >=50 observations from each of the two genders, you can randomly pick 50 from each of the genders.
If one of the genders' count is <50, you'll have to survey a bit longer (until the bare minimum is met) or reduce your sample size.
In general, we cannot tell the population proportion unless we survey each and every individual which could be a huge burden on the resources. So, we instead survey randomly selected areas and try to estimate the population proportion based on the sample.
