I'm doing some research to see if there is a distribution I can use to match a somewhat complicated problem, which is as follows:

  1. 158 numbers are to be selected at random in the range of 0 to 8191.
  2. If the number is below some threshold (<= 7495), it is valid. If above the threshold, it is invalid and is discarded.
  3. Valid numbers are reduced modulus 1499, where they become unique elements in an array - i.e. they can't be chosen twice (so effectively, valid samples below the threshold effectively remove 5 different choices at once since 7495 = 1499 * 5).
  4. To make matters more complicated, there is a series of checkpoints laid out evenly throughout selection that must be passed for sampling to continue. For example - after 19 samples, at least 14 valid numbers must be selected. After 39, 30 valid numbers. After 59, 47 must be selected, and so on. I'm not listing all of the checkpoint values here, unless someone thinks they need them. But I think we can reason about the scenario without these specifics.
  5. I am trying to determine analytically the probability that 158 valid numbers will be selected out of 196 samples, with all checkpoints being passed (there are 10 of them).

My thought process (using marbles and urns), was sort of the following:

  1. Because valid marbles are chosen without replacement, my first thought was that it's kind of like a hyper-geometric distribution. But the situation isn't quite just a hyper-geometric distribution with n=196, k=158, N=8192, and K=7495. The valid marbles are reduced mod 1499, which complicates things.
  2. Reading about the Wallenius Noncentral Hypergeometric Distribution led me to think the modulus could be dealt with by viewing this as a distribution where there are 1499 marbles of 'weight' 5 and 697 marbles of 'weight' 1 (1499*5 + 697 = 8192), except the problem is that the values above the threshold (from 7495 to 8191) aren't actually 'removed' from the urn.
  3. My next thought was that since the invalid marbles aren't removed the initial probability of being below the threshold is constant, so I thought maybe this could be simplified as starting with the probability of acquiring a valid marble (7495/8192), and then applying a hyper-geometric distribution, with n=196, k=158, N=1499, and K=1499. But now the problem here is of course the checkpoints. This would incorrectly factor in cases where checkpoints were not passed, yet enough valid marbles were drawn by the end.
  4. Off of the above point, then I thought I could view this as again starting with a 7495/8192 probability of pulling a valid marble, but then breaking the checkpoints into 10 distinct hyper-geometric distributions, with n and k becoming just the deltas between the checkpoints. This too seems incorrect, because these aren't independent events. N and K aren't staying the same throughout the process.

So presently, I'm wondering if I'm overthinking and if there is some nice distribution I can use, or if the "checkpoints" element of this problem really does complicate this such that the only way I'm going to be able to compute a number out of this is with some recursive functions iterating over each case.

I guess since the probability of selecting a valid number/marble changes, this can't be a simple binomial distribution, right? But also - the selection range doesn't change either, no marbles are "removed". It's more like the valid marbles are selected, but stay in the urn and jump sets and become invalid after being selected.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.