I have a game where you start with 13 cards (for example a single suit). Randomly select three cards, from which you discard both the lowest and the highest, while returning the median card to the original set. This process is then repeated with the sucessively smaller set until only a single card remains. What is the probability for each of the 13 cards you started with remaining as the last one in the set?
The process involves 6 steps, going successively to 11, 9, 7, 5, 3 and then 1 card remaining. At each step let n be the total number of cards at the start of the step, and let r be the ordinal value of a given card whose probabilities you want to follow into the next step, that is, it is card r out of n cards in ascending order of value.
During each step, the card will go from being r out of n to either r-2, r-1 or r out of n-2, or it will be eliminated from the deck.
The cases:
It will go to position r-2 if all three chosen cards are lower in value than it. This has probability
(r - 1) / n * (r - 2) / (n - 1) * (r - 3) / (n - 2)
It will go to position r-1 if either one or two of the three chosen cards is/are lower in value than it, and the highest chosen card is higher than it, or if the card in question is the middle-valued of the three chosen. The respective probabilities that two or one are below the given card and one above are:
3 * (r - 1) / n * (r - 2) / (n - 1) * (n - r) / (n - 2)
and
3 * (r - 1) / n * (n - r) / (n - 1) * (n - r - 1) / (n - 2)
and of being the middle-valued chosen card:
6 / n * (r - 1) / (n - 1) * (n - r) / (n - 2)
It will remain at position r if all the drawn cards are higher in value, having probability
(n - r) / n * (n - r - 1) / (n - 1) * (n - r - 2) / (n - 2)
The card will be eliminated from the deck if it is either the lowest or highest chosen card, with respective probabilities:
3 / n * (n - r) / (n - 1) * (n - r - 1) / (n - 2)
and
3 / n * (r - 1) / (n - 1) * (r - 2) / (n - 2)
A program which evaluates these successive probabilities for cards that start at the various positions and totals the probability of being eliminated (and then subtracts that total from 1, to get the probability of being the last card) is:
CLS
DEFDBL A-Z
FOR stPos = 1 TO 13
REDIM prob(13, 13)
prob(0, stPos) = 1
killed = 0
FOR newRow = 2 TO 12 STEP 2
oldRow = newRow - 2
n = 13 - oldRow
FOR r = 1 TO 13
GOSUB transit
IF r > 2 THEN prob(newRow, r - 2) = prob(newRow, r - 2) + allBelow * prob(oldRow, r)
IF r > 1 THEN prob(newRow, r - 1) = prob(newRow, r - 1) + (oneBelow + twoBelow + middle) * prob(oldRow, r)
prob(newRow, r) = prob(newRow, r) + allAbove * prob(oldRow, r)
killed = killed + (lowest + highest) * prob(oldRow, r)
NEXT r
NEXT newRow
PRINT USING "## #.#######"; stPos; 1 - killed
NEXT stPos
END
transit:
allBelow = (r - 1) / n * (r - 2) / (n - 1) * (r - 3) / (n - 2)
twoBelow = 3 * (r - 1) / n * (r - 2) / (n - 1) * (n - r) / (n - 2)
oneBelow = 3 * (r - 1) / n * (n - r) / (n - 1) * (n - r - 1) / (n - 2)
allAbove = (n - r) / n * (n - r - 1) / (n - 1) * (n - r - 2) / (n - 2)
lowest = 3 / n * (n - r) / (n - 1) * (n - r - 1) / (n - 2)
highest = 3 / n * (r - 1) / (n - 1) * (r - 2) / (n - 2)
middle = 6 / n * (r - 1) / (n - 1) * (n - r) / (n - 2)
RETURN
The results are:
1 0.0000000
2 0.0034965
3 0.0127146
4 0.0357067
5 0.0892845
6 0.1961927
7 0.3252101
8 0.1961927
9 0.0892845
10 0.0357067
11 0.0127146
12 0.0034965
13 0.0000000
-------
A similar program written in UBASIC, using that language's rational number capability, gives the following exact probabilities:
1 0
2 1/286
3 20/1573
4 337/9438
5 1264/14157
6 505/2574
7 4604/14157
8 505/2574
9 1264/14157
10 337/9438
11 20/1573
12 1/286
13 0
or, with a common denominator:
0 / 28314
99 / 28314
360 / 28314
1011 / 28314
2528 / 28314
5555 / 28314
9208 / 28314
5555 / 28314
2528 / 28314
1011 / 28314
360 / 28314
99 / 28314
0 / 28314
----
(The slashes are doubled in UBASIC's indication of rational numbers. I've changed them to single slashes to give the conventional notation.)
|
|
Posted by Charlie
on 2003-12-31 15:33:08 |
solution
