5
$\begingroup$

A standard deck of $52$ shuffled playing cards can be used as a source of randomness.

Assuming cards are not replaced as they're drawn, a full deck of cards provides $225.58$ bits of entropy $- 52!$ combinations $= \log_2(52!)$ bits of entropy.

What is the correct way to calculate the bits of entropy supplied by multiple decks of cards?

For a single deck reshuffled 3 times in a row I would expected $\log_2(52!^3) = 676.74$ bits. But for 3 decks shuffled together, what is the value?

Also, if $N$ cards have been drawn of $X$ decks, how much entropy has been accumulated?

This sounds like a homework question but I'm trying to develop this as a feature in a project - https://github.com/iancoleman/bip39/issues/33

$\endgroup$
  • 3
    $\begingroup$ Using Shannon entropy on non-uniform distributions is rather dubious for cryptographic purposes. I prefer using the probability of the most likely outcome as an estimator for the security, i.e. $-\log_2{p_{\max}}$. $\endgroup$ – CodesInChaos Nov 29 '16 at 10:37
  • 1
    $\begingroup$ BTW, the $-\log p_{\max}$ measure suggested by @CodesInChaos is also known as the min-entropy. $\endgroup$ – Ilmari Karonen Nov 29 '16 at 18:54
2
$\begingroup$

Use the multinomial coefficients.

$\endgroup$
  • 4
    $\begingroup$ Perhaps you could add some explanation of how to use the linked construct to tackle his problem? At least add (52*3)!/(4!)^52 ... $\endgroup$ – rmalayter Nov 29 '16 at 2:29
  • 2
    $\begingroup$ @rmalayter That would be $(52\cdot 3)! / (3!)^{52}$, I guess the $4!$ was a typo. $\endgroup$ – tylo Nov 29 '16 at 13:31
  • $\begingroup$ @Ricky_Demer yep a typo on my phone. Entering MathML from a phone is something I dare not try $\endgroup$ – rmalayter Nov 29 '16 at 14:10
  • $\begingroup$ @Ricky Demer: Can you think of a way of solving the "if N cards have been drawn of X decks, how much entropy has been accumulated?" part of the question ? (noting that we must add on average, or something else on that tune) $\endgroup$ – fgrieu Nov 30 '16 at 7:32
2
$\begingroup$

An intuitive way to tackle computing the entropy $H(X)$ in $X$ joined and shuffled identical decks of 52 cards is: the entropy that would be available if the back of the cards were recognizable, less the entropy lost because they are not. That's $$H(X)=\log_2((52X)!)-52\log_2(X!)$$


I found no equally simple way of computing the entropy $H(X,N)$ in the first $N$ cards out of $X>1$ joined and shuffled identical decks of 52 cards.

In fact, that quantity is only well-defined when $N\in\{0,1,(52X-1),52X\}$. For other $N$, it depends on the experiment. For example, for $N=51X$, our $H(X,N)$ can range from $H(X)-\log_2(X!)$ when all the remaining $X$ cards are distinguishable, to $H(X)$ when they are all identical (which can be determined with certainty from the $N=51X$ cards drawn). Thus we must first decide if we aim at computing the average $H(X,N)$, or the minimal $H(X,N)$.

$\endgroup$
  • $\begingroup$ I think computing a close-ish lower bound is good enough. $\endgroup$ – Chris Moore Dec 2 '16 at 17:27

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.