Re: Possible Solution
Hi, (BruceZ, Huh, PseudoPserious)
Maybe some "FOOD for Thought"
I again want to thank you people for the posts. I am way behind in comprehending some or most of these posts (I will take my time trying to grasp them). Anyway – I wanted your opinions (I wonder) if any of these solutions are exact or are they all excellent approximations. Myself (initially), without any feedback from Huh, Bruce, or PP: I would have used brute force (Monte Carlo Techniques) to get an answer -- using hopefully an accurate algorithm for pseudo random numbers.
Food for thought:
So far I get the impression from the posts that the original Huh problem statement as an expanding tree type problem where the probabilities at each level are to be calculated and summed. An individual deal is a 2-tuple sample without replacement, and each deal is a sample with replacement. This generates a tree type sequence with an infinite series of terms. I don’t know how to handle this on an exact basis. Maybe I can eventually understand it better. I wanted to mention something to you guys and see if you considered it….
From the posts, the consensus is that on average 117 deals are required to complete the process. Also since the different (or slightly different) techniques used to come up with the answer all predict about 117, I feel that any errors introduced by the various techniques are relatively small. That said: I wanted to see if any of you guys considered working the problem (getting an answer) by starting at the end and working backwards (reverse the tree). I’m just curious if you have considered any merit to this thought – maybe it is trivial and doesn’t deserve considering. Anyway, as you know near the end of the process….
At the end of the process when only one card is missing, on average, 26 deals are required to complete the process. If two cards are missing, about 13.26 or so deals are required to get it down to one card or zero cards. Probably the sequence is about 9.02 deals req’d to get down to one, two, or remain at three cards; and about 6.9 deals req’s to get four cards down to two, three, or remain at four cards (and so on and on). The numbers of deals required at each level reduces eventually (as you know) to about 1.92307 to generate the tree at the initial level. My interest in this was that most of the deals are req’d near the end of the process which may give some additional incite to the nature of the problem.
Also I had a question. Can some this problem be considered a Markoff chain (process), that is does it have Markovian properties.
Most warm regards,
Carl
|