2
$\begingroup$

I want to characterize the simple algorithm for selecting, say, 20% of a discrete set when the total size of the set is not known:

foreach item in the set
   generate a random non-negative integer R
   if (R mod 100) < 20 then
      select item

Does that algorithm have a name? Is it the same as Algorithm $B\mathcal U$ in Binomial random variate generation? (The algorithm there has "generate $u \sim \mathcal U(0,1)$" instead of a random integer, and uses $\le$ instead of $\lt$. Algorithm cited here)

The probability of ending up with $k$ items after examining $n$ of them can be calculated using the binomial distribution as: $$f(n, k) = \binom{n}{k}p^k(1-p)^{n-k}$$ where $p=\frac{20}{100} = 0.2\quad$ in this example. However, plotting the resulting values for widely different $n$ results in non-comparable graphs. In the picture below, I plotted the values of $f(n,k)$, scaling the interval $[0, n]$ in abscissa to the unit interval $[0, 1]$, and multiplying $f(n, k)$ by $n/10$ in ordinate, so as to compensate for shrinking the abscissa. (That way, the "integral" of the curve appears to be preserved.) For high values of $n$ I compute the average of a few $k$'s. Since the results are rather high, I use a logarithmic scale.

Binomial distribution for p=0.2

I'd like to show the picture above in a wikipedia article. However, the explanation above smells of original research. Is there an accepted way to scale those functions so as to compare them? Are there references that justify them?

Note: cross posted to math.stackexchange, I didn't know of this site.

$\endgroup$
6
  • 1
    $\begingroup$ "generate a random integer R" doesn't seem well defined. Do you mean random integer between 1 and 100? Or really any integer? $\endgroup$
    – bdeonovic
    Sep 1, 2021 at 20:07
  • 1
    $\begingroup$ Also generating random integer uniformly at random is basically the same as generating random float from continuous uniform distribution. The rest of the algorithm is just “throw a coin to decide” and doesn’t have special name. $\endgroup$
    – Tim
    Sep 1, 2021 at 21:37
  • 1
    $\begingroup$ This is essentially the binomial distribution, with $p=0.20$ and $n=|\text{set}|.$ $\endgroup$ Sep 1, 2021 at 21:42
  • $\begingroup$ bdeonovic: I'll edit s/integer/natural number/. Tim: Yet Kachitvichyanukul and Schmeise call it "Algorithm BU". Adrian Keister: yes, exactly! $\endgroup$
    – Ale
    Sep 2, 2021 at 7:16
  • $\begingroup$ @Adrian Keister: do you want to post your comment(s) as an answer? Better to have a short answer than no answer at all. Anyone who has a better answer can post it. $\endgroup$ Sep 2, 2021 at 16:49

1 Answer 1

2
$\begingroup$

This is essentially the binomial distribution, with $p=0.20$ and $n=|\text{set}|,$ the number of elements in the set.

$\endgroup$
2
  • $\begingroup$ Does that mean the scaled graphs renders the intrinsic nature correctly? $\endgroup$
    – Ale
    Sep 4, 2021 at 8:04
  • $\begingroup$ Well, there's nothing wrong with a logarithmic scale, as long as it's clearly called out, which you've done. For some plots, particularly those that cross many orders of magnitude, a logarithmic scale is much more illuminating than a linear one. $\endgroup$ Sep 4, 2021 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.