Critical Line volume 29

Before I share the actual challenge for this month, I want to share what I think is an interesting observation.  In tournament poker, there come times in most tournaments where lower denomination chips that are no longer needed are ‘raced-off’ and replaced with higher denomination chips.  For example, once a level is reached that all future blind and ante amounts are multiples of 500, the 100-value chips will be removed from play.  Each five 100-value chips a player has is exchanged for a 500-value chip, and any remaining 100-value chips are raced off.  The race-off is pure luck and works as follows:

Every player at the table will have between 0 and 4 100-value chips.  The total amount of 100-value chips from all players is divided by 5 and round up or down to determine how many 500-value chips will be awarded.  The dealer shuffles the deck, and deals each player one card face up for each 100-value chip they have.  The player with the highest card receives the first 500-value chip, and all of their dealt cards are removed (note that suits are also ranked from high to low as Spades, Hearts, Diamonds, Clubs, so ties are impossible).  The player with the next highest card remaining receives the next 500-value chip, and so on until all the 500-value chips have been awarded.  Note that a player can only receive a maximum of one 500-value chip, even if they were dealt the two highest cards.

Here’s my observation.  Let’s say three people Alice, Bob and Charlie are involved in a race-off.  Alice has four 100-value chips, Bob has four 100-value chips, and Charlie has two 100-value chips.  A total of two 500-value chips will be awarded.  We want to determine the probability that Charlie is awarded one of the two 500-value chips.

When I first thought about this whilst observing this exact situation in a tournament, there were two intuitive ways that occurred to me, but I quickly realised they provided different answers, and so they can’t both be right.  This made me want to think about it more.

The first intuitive way is that Charlie’s probability of winning a chip could be half of the probability of Alice or Bob, since he has half the number of 100-value chips as each of them.  Since the sum of everyone’s probability must add to 200%, this quickly yields odds of 80% Alice, 80% Bob and 40% Charlie.

The second intuitive way is that one person will miss out, and Charlie’s probability of missing out could be double that of Alice or Bob (again since he has half the number of chips).  This quickly yields odds of missing out of 25% Alice, 25% Bob, 50% Charlie, or alternatively odds of winning of 75% Alice, 75% Bob and 50% Charlie.  Not the same answer as the first way!

So, I wondered, which is correct?  Or are they both wrong?  Further analysis after returning home revealed that neither of these two ways gives the correct answer!  The true answer lies somewhere in between the two.  Whilst I can find the correct answer, finding an intuitive explanation for it is somewhat more difficult.  Can you figure out Charlie’s probability of winning the race-off and explain why?

This is just a side observation though – the actual challenge for this month is a different question, this one dice related.

The challenge for this month:

Whilst still a probability question as many of my puzzles are, this one will be a little bit harder than normal to brute force solve, since it asks about a general case.  A challenge for the analytical solvers! 

You have a single die (or single dice if you prefer that language) with n sides showing the natural numbers from 1 to n. The die is calibrated fairly, so that each number from 1 through n has an equal 1/n chance of being rolled on any roll.

How many times on average must you roll the die until the cumulative sum of the numbers rolled first exceeds n?  Give your answer as a function of n if you can!

I will welcome answers for both the race-off and the dice question, but only the dice question will be eligible for the book voucher.

For your chance to win a $50 book voucher, send your solutions to ActuariesMag@actuaries.asn.au

The Critical Line – March 19

We had only one correct entry this month. Congratulations to Ean Chan, who claims the $50 book voucher!

Solution

We provide the more general solution for a $$2^n$$ bit message.

Let $$b$$ be a block of $$N=2^n-1$$ bits. First, recall from last week’s article that the algorithm of the Hamming Code provides a map, $$\varphi$$, from $$b$$ to an integer between $$0$$ and $$N$$. Where $$0$$ represented that the message was consistent and $$k$$, for $$1 \le k \le N$$ was the bit in the block that you needed to flip to make the message consistent.

If $$\varphi_b(k)$$ is the value of $$\varphi(b)$$ where the $$k^{\text{th}}$$ bit of $$b$$ was flipped then the sequence $$(\varphi(b), \varphi_b(1), \varphi_b(2), … \varphi_b(N))$$ has length $$2^n$$ and must be a permutation of $$(0, 1, 2, …, N)$$ (proof left as exercise. Leave a comment if you would like a hint)

 Suppose we have a random message $$m$$ of length $$2^n$$ bits and we want to convey the number $$j \in [0, 2^n-1]$$. Then our algorithm becomes:

1. Let $$m’$$ be the first $$2^n-1$$ bits
2. If $$\varphi(m’) = j$$ then flip last bit of $$m$$
3. Otherwise, find $$k$$ such that $$\varphi_{m’}(k)=j$$. Then flip the $$k^{\text{th}}$$ bit

Now exactly one bit from $$m$$ was flipped and the receiver can decode the message by calculating $$\varphi$$ of the first $$2^n-1$$ bits.

Ean Chan provided a nice spreadsheet demonstrating this solution, which you can find here.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.