[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
1640.0. "how many cards will we announce ?" by HANNAH::OSMAN (see HANNAH::IGLOO$:[OSMAN]ERIC.VT240) Fri Jul 10 1992 18:00
Here's a probability problem which I think I made up:
Assign an order of value to every card in a standard deck. Arbitrarily,
we'll use the bridge ordering, which is
spades is better than hearts is better than diamonds is better than
clubs, and within each suit, ace is high, two is low. (In case you
don't know bridge, the suits arranged alphabetically increase in value)
Shuffle the deck. Look at the first card and announce it.
Then look at the second card, and only announce it if it is higher than the
first card.
Likewise through the deck, looking at each card and only announcing it if
it is higher than any card seen so far.
We stop, of course, if we've announced the ace of spades.
The question:
What is the expected quantity of announced cards ?
By the way, I thought of this puzzle when I was designing computer programs
that scan huge sets of data, looking for some sort of best fit. If the data
is long, it's sometimes useful to keep the user from getting too bored, by
announcing the best found so far as we go. I got to wondering whether such
intermediate announcements would be overwhelming in quantity...
/Eric
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1640.2 | this gives a ref in Knuth | DESIR::BUCHANAN | | Mon Jul 13 1992 05:24 | 3 |
| See 1562.*
Andrew
|
| 1640.3 | Surprisingly few expected | VAXRT::BRIDGEWATER | Eclipsing the past | Wed Jul 15 1992 17:56 | 52 |
| Let e(n) = the expected number of announced cards including the highest
ranked card in a deck of n cards
Then, e(0) = 0
and for n a positive integer:
n-1
e(n) = (1/n) sum (1 + e(i))
i=0
n-1
= 1 + (1/n) sum (e(i))
i=0
This is because the highest ranked card is equally likely to be any of
the n cards. If it is the k-th card in the deck, then we have a sub-
deck of k-1 cards followed by the highest ranked card in the n-card deck,
which is in turn followed by a sub-deck of n-k cards. The sub-deck of
n-k cards will not contain any cards to be announced since they all
come after the highest ranked card in the n-card deck. Of course, we
will have to announce the highest ranked card when we come to it.
Before announcing that card, we have the same problem to solve using
the k-1 card sub-deck as we started with using the n-card deck.
n
e(n) = sum (1/i)
i=1
This can easily be proved by induction:
e(0) = 0
e(1) = 1 (both formulae agree)
For n a positive integer:
n-1
e(n) = 1 + (1/n) sum (e(i))
i=0
n
e(n+1) = 1 + [1/(n+1)] sum (e(i))
i=0
= [n/(n+1)][e(n)-1] + 1 + [1/(n+1)]e(n)
= e(n) + 1/(n+1)
So for a deck of 52-cards, the expected number of announced cards is:
52
sum (1/i) = 4.53804+
i=1
- Don
|