2
$\begingroup$

In the context of writing a program for sortition, I would like to know if the entropy of my input random variable in large enough to potentially produce all outcome of my sortition problem.

Let say I have $n$ candidates, and I want to pick $k$ of them. $n \gg k$ ($n$ is in millions, $k$ in hundreds)

To process this sortition, I am using a binary input of $j$ bits. This input has an entropy of $2^j$ possible combinations.

I would like to know what $j$ to choose for a given $n, k$ so that : $$2^j \sim C(n, k) $$

For that, I would need an approximation of $C(n,k)$ for large numbers, expressed as exponentials.

I am aware of the Stirling's approximation, for expressing large factorials as exponentials. But I did not found similar approximation for binomial coefficients.

$\endgroup$
1
  • 1
    $\begingroup$ If $k \ll n$, then ${n\choose k} \approx \dfrac{n^k}{k!}$ $\endgroup$ Aug 25 '14 at 15:27
1
$\begingroup$

As $n \to \infty$ with $k$ fixed, $C(n,k) \sim n^k/k!$.

$\endgroup$
0
$\begingroup$

Ok, thanks for you input. I realise that if $n >> k$, things are easier.

So if I want a upper limit, Let say for sorted sortition, then I consider for $k \to \infty$ $$ A(n, k) \sim n^{k} \implies n^{k} \sim 2^j \implies e^{k \ln(n)} \sim e^{j \ln(2)} \implies j \sim \frac{k \ln(n)}{\ln(2)} $$

For instance, for $n=1,000,000$ and $k=100$, I need $j=1993$ bits of random input.

$\endgroup$

Your Answer

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

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