Cut the Cards
07-30-2020, 08:00 PM
Post: #1
 David Hayden Senior Member Posts: 326 Joined: Dec 2013
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
07-30-2020, 08:58 PM
Post: #2
 Albert Chan Senior Member Posts: 970 Joined: Jul 2018
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
07-30-2020, 09:49 PM
Post: #3
 Jim Horn Member Posts: 186 Joined: Dec 2013
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!
07-30-2020, 10:21 PM
Post: #4
 Albert Chan Senior Member Posts: 970 Joined: Jul 2018
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
07-31-2020, 12:24 AM (This post was last modified: 07-31-2020 12:51 AM by John Keith.)
Post: #5
 John Keith Senior Member Posts: 554 Joined: Dec 2013
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.
 « Next Oldest | Next Newest »

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