# Entropy measurement from shuffled cards

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

• 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}}$. – CodesInChaos Nov 29 '16 at 10:37
• BTW, the $-\log p_{\max}$ measure suggested by @CodesInChaos is also known as the min-entropy. – Ilmari Karonen Nov 29 '16 at 18:54

Use the multinomial coefficients.

• Perhaps you could add some explanation of how to use the linked construct to tackle his problem? At least add (52*3)!/(4!)^52 ... – rmalayter Nov 29 '16 at 2:29
• @rmalayter That would be $(52\cdot 3)! / (3!)^{52}$, I guess the $4!$ was a typo. – tylo Nov 29 '16 at 13:31
• @Ricky_Demer yep a typo on my phone. Entering MathML from a phone is something I dare not try – rmalayter Nov 29 '16 at 14:10
• @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) – fgrieu Nov 30 '16 at 7:32

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)$.

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