What is the expected change of the purchasing game?

101 Views Asked by At

Denote the price of item as $N$ cents. The player has infinite coin supply of $1$, $5$, $10$ or $25$ cents. The player keeps drawing one coin of these four types with equal probability, until accumulated value reaches $N$ or beyond.

Question 1: What is the expected change the player could have for $N = 30$?

For example, if the player keeps drawing until he/she has $29$ cents. He/she draws another $5$ cent. Then he/she keeps the change of $4$ cents. (My thought: for small $N$, such as $N = 30$, we might use Markov chain and solve all adsorbing state probabilities by hand. However, this is unpleasant.)

Question 2: What if the $N$ goes really large?

1

There are 1 best solutions below

10
On BEST ANSWER

I'll answer Question $2$ on the limit of the expected change as $N\to\infty$.

In a quasisteady state, the process is expected to progress by the average coin value $\frac{1+5+10+25}4=\frac{41}4$ in each step. It follows that each sum has probability $\frac4{41}$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.

This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $N\le v\le N+24$ can be reached with $k$ different coins before the game ends, it contributes $\frac k4\cdot\frac4{41}(v-N)=\frac k{41}(v-N)$ to the change.

The sum $N$ can be reached with any coin value, but it contributes $0$ change.

The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $\frac3{41}\sum_{k=1}^4k=\frac{30}{41}$.

The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $\frac2{41}\sum_{k=5}^9k=\frac{70}{41}$.

The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $\frac1{41}\sum_{k=10}^{24}k=\frac{255}{41}$.

So the total expected change in the limit $N\to\infty$ is $\frac{30+70+255}{41}=\frac{355}{41}\approx8.66$.

I really do have to share my favourite change joke with you at this point:

A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?” The Zen monk replies: “Make me one with everything.” Afterwards, the Zen monk pays and says: “Where's my change?” The vendor replies: “Change comes from within.”