Cut the Cards

07302020, 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 

07302020, 08:58 PM
Post: #2




RE: Cut the Cards
(07302020 08:00 PM)David Hayden Wrote: Choose a card at random from a deck of 52 and put the card back. 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^521)/(t1), t=0 .. 1) * 52.0 → 235.978285436 → averaged 236 picks to see all 52 cards 

07302020, 09:49 PM
Post: #3




RE: Cut the Cards
So, it approaches x*(ln(x)+0.57721), where the latter constant is the EulerMascheroni 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! 

07302020, 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 lua> run(1e6, 52) 235.970842 

07312020, 12:24 AM
(This post was last modified: 07312020 12:51 AM by John Keith.)
Post: #5




RE: Cut the Cards
(07302020 09:49 PM)Jim Horn Wrote: So, it approaches x*(ln(x)+0.57721), where the latter constant is the EulerMascheroni constant. Or in other words, n*H(n), where H(n) is the nth harmonic number. (Albert's first formula in post #2) (07302020 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)