Expected number of coins need to reach an integral value

Question

I'm trying to validate my work for the following problem but the computer simulation is not supporting it:

There are two types of coins: one worth $0.2$ and one worth $0.4$. Now suppose a person randomly selects a coin and adds it to a running total which starts at $0$. They keep on randomly selecting either of the two coins until they reach an integer value.

For example, the sequence $0.2$, $0.2$, $0.2$, $0.2$, $0.2$ will terminate with $5$ coins used. Another example is $0.2$, $0.4$, and $0.4$ with $3$ coins. However, the sequence $0.2$, $0.4$, $0.4$, $0.2$, $0.4$, $0.4$ is impossible since they would have reached $1.0$ before they reach 2.0.

Q: What is the expected number of coins used?

I reasoned that I could express the expectations as a system of equations. Let $E[N|0.2]$ be the expected number extra coins needed to get an integral value given that you already start off with a total ending with $20$ cents. We can define $E[N|0.4]$, $E[N|0.6]$, and $E[N|0.8]$ similarly.

I reasoned that the number of extra coins needed if our sum ended with $0.2$ would depend on whether we draw a $0.2$ or $0.4$ coin. With equal probability, our total would end with a $0.4$ or $0.6$. In either case, we only need the number of coins starting from a total ending with $0.4$ or $0.6$ in expectation plus the coin we already drew: $$E[N|0.2]=\frac{1}{2}(1+E[N|0.4])+\frac{1}{2}(1+E[N|0.6])$$

The remaining equations form a system:

\begin{align} E[N|0.2]&=\frac{1}{2}(1+E[N|0.4])+\frac{1}{2}(1+E[N|0.6])\\ E[N|0.4]&=\frac{1}{2}(1+E[N|0.6])+\frac{1}{2}(1+E[N|0.8])\\ E[N|0.6]&=\frac{1}{2}(1+E[N|0.8])+\frac{1}{2}(1)\\ E[N|0.8]&=\frac{1}{2}(1)+\frac{1}{2}(1+E[N|0.2]) \end{align}

The solution to this system is $(\frac{46}{11}, \frac{42}{11}, \frac{28}{11}, \frac{34}{11})$. Finally to get the expected number of coins, $E[X]$, used in total, we condition on the first coin drawn: $$E[X]=\frac{1}{2}(1+E[N|0.2])+\frac{1}{2}(1+E[N|0.4])=1+\frac{1}{2}\left(\frac{46}{11}+\frac{42}{11}\right)=5$$

I tried this technique for [$0.25$, $0.5$] and got an expected value of $4$ which makes sense and matches simulation results. When I ran a simulation for these two coins, however, I got a stable ~16ish :/

What is going on?

Answer 1

$5$ looks correct: I suspect the issue is floating point rounding in your simulation.

Note that 2-(0.2+0.2+0.2+0.2+0.2+0.2+0.2+0.2+0.2+0.2) gives 2.220446e-16 not 0.

Try making the coins $2$ and $4$ and checking whether they add up to a multiple of $10$

Here is a simulation in R which seems to reproduce your report. Note than using integers you do get close to $5$ and with decimals you are nearer $16$. In the $10^5$ integer simulations you never needed more than $37$ coins while in the floating point simulation there were implausibly $2119$ cases needing between $132$ and $12335$ coins, so pushing up the empirical average

reachmultipletarget <- function(coins, target){
  numbercoins <- 0
  sumcoins <- 0
  while(numbercoins == 0 | sumcoins %% target > 0){
    numbercoins <- numbercoins + 1
    sumcoins <- sumcoins + sample(coins, 1)
    }
  return(numbercoins)
  }

set.seed(2021)
sims <- replicate(10^5, reachmultipletarget(c(2, 4), 10))
mean(sims)
# 4.99726

sims <- replicate(10^5, reachmultipletarget(c(0.2, 0.4), 1))
mean(sims)
# 15.67679