Post Reply 
Cut the Cards
07-30-2020, 08:00 PM
Post: #1
Cut the Cards
PPC Journal V5N4 Page 13 poses a question about a deck of cards. Choose a card at random from a deck of 52 and put the card back. What is the average number of choices required to see all 52 cards?

I simulated the experiment in C++ and got the right answer (236) but I can't figure how to do this analytically. Is it possible?

If you simplify the problem down to a deck of 2 cards then it's easier: you choose the first card, and then it's just a matter of the average number of choices to get the second: 1*1/2 + 2*1/4 + 3*1/8 ..., but can that be extended to more cards?

Dave
Find all posts by this user
Quote this message in a reply
07-30-2020, 08:58 PM
Post: #2
RE: Cut the Cards
(07-30-2020 08:00 PM)David Hayden Wrote:  Choose a card at random from a deck of 52 and put the card back.
What is the average number of choices required to see all 52 cards?

First card picked must never been seen, thus only 1 try needed to get 1st card.
Probability of getting the next "new" card = 51/52, or averaged 52/51 tries to get 2nd card
...

We can get averaged picks either way:

XCas> sum(1/t, t=1 .. 52) * 52.0                 → 235.978285436
XCas> int((t^52-1)/(t-1), t=0 .. 1) * 52.0    → 235.978285436

→ averaged 236 picks to see all 52 cards
Find all posts by this user
Quote this message in a reply
07-30-2020, 09:49 PM
Post: #3
RE: Cut the Cards
So, it approaches x*(ln(x)+0.57721), where the latter constant is the Euler-Mascheroni constant. This isn't as accurate as doing it analytically but is good for fast calculations. For instance, if you picked a random second of a year every second, how many years would it take? About 17.84 total.

So many signals, so little bandwidth!
Find all posts by this user
Quote this message in a reply
07-30-2020, 10:21 PM
Post: #4
RE: Cut the Cards
Here is simulations, using Lua
Note: math.random(n) return 1 .. n, each with same probability.

Code:
function run(tests,cards)   -- averaged picks
    local n = 0             -- bad tries
    for i=1,tests do
        for t=1,cards do
            while math.random(cards) < t do n=n+1 end
        end
    end
    return n/tests + cards
end

lua> run(1e6, 52)
235.970842
Find all posts by this user
Quote this message in a reply
07-31-2020, 12:24 AM (This post was last modified: 07-31-2020 12:51 AM by John Keith.)
Post: #5
RE: Cut the Cards
(07-30-2020 09:49 PM)Jim Horn Wrote:  So, it approaches x*(ln(x)+0.57721), where the latter constant is the Euler-Mascheroni constant.

Or in other words, n*H(n), where H(n) is the nth harmonic number. (Albert's first formula in post #2)


(07-30-2020 09:49 PM)Jim Horn Wrote:  This isn't as accurate as doing it analytically but is good for fast calculations.

Actually it is very accurate as the first image in the Wikipedia link shows: LN(n)+gamma is the asymptotic limit of H(n) as n approaches infinity.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)