All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 a game of chance (Posted on 2003-12-31)
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?

 See The Solution Submitted by Cory Taylor Rating: 4.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 3
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

 Search: Search body:
Forums (0)