Introduction and Problem Statement

Riddle 234 from Five Thirty Eight’s column “The Riddler” was suggested by Kareem Carr. It is as follows:

We usually think of addition as an operation applied to a field like the rational numbers or the real numbers. And there is good reason for that - as Kareem says, “Mathematicians have done all the hard work of figuring out how to make calculations track with reality. They kept modifying and refining the number system until everything worked out. It took centuries of brilliant minds to do this!”

Now suppose we defined addition another (admittedly less useful) way, using a classic model organism: the nematode. To compute the sum of x and y, you combine groups of x and y nematodes and leave them for 24 hours. When you come back, you count up how many you have - and that’s the sum!

It turns out that, over the course of 24 hours, the nematodes pair up, and each pair has one offspring 50 percent of the time. (If you have an odd number of nematodes, they will still pair up, but one will be left out.) So if you want to compute 1+1, half the time you’ll get 2 and half the time you’ll get 3. If you compute 2+2, 25 percent of the time you get 4, 50 percent of the time you’ll get 5, and 25 percent of the time you’ll get 6.

While we’re at it, let’s define exponentiation for sums of nematodes. Raising a sum to a power means leaving that sum of nematodes for the number of days specified by the exponent.

With this number system, what is the expected value of \((1+1)^4\)?

Extra credit: As N gets larger and larger, what does the expected value of \((1+1)^N\) approach?

Solution

We can look at this as a stochastic process where \(S_0\) is the initial sum. In this case, we’re exploring \(S_0=1+1=2\). We can think of \(S_1\) as what the sum ends up being after 1 time period (24 hours in our case), and \(S_t\) the sum after \(t\) time periods. With this definition and initial condition, we’re after \(E(S_4)\).

It will be helpful to explore \(E(S_1)\) for the five initial conditions, \(S_0= s\) for \(s = 2,3,4,5,6\). One can quickly see that \(E(S_1)=2.5\) and 3.5 when \(s=2\) and 3, respectively. When \(s=4\), we end up having 2 pairings. Both can result in 0 offspring with probability .25, only one can have offspring with probability .50, and both could have offspring with probability .25. With this nice symmetry, we can easily see that \(E(S_1)=5\) for \(s=4\). Analogously, when \(s=5\) and there still can only be 2 pairs with a possible ending sum of 5, 6, or 7, it is easy to see \(E(S_1)=6\) for \(s=5\).

For \(s=6\) we see there are 3 pairs, and once again a binomial symmetry of the possible offspring (0, 1, 2, or 3 with probabilities .125, .375, .375, and .125, respectively). So, \(S_0=6\) can lead to \(S_1 \in \{6,7,8,9\}\). With the nice symmetry, we get \(E(S_1)=7.5\) for \(s=6\).

Next, we’ll look at \(E(S_2)\) for the three initial conditions \(S_0=s\) for \(s=2\), 3, and 4. We have seen 2 can either become 2 or 3 in 1 step with equal probability. Using our result above for one step, their one-step expectations are 2.5 and 3.5, respectively. So, \(E(S_2) = 0.5(2.5)+0.5(3.5)=3\) for two steps when \(S_0=2\).

When \(S_0=3\), the next step can be 3 or 4 with equal probability. We have seen that in one-step, the expectations for these two values are 3.5 and 5 respectively. Thus, \(E(S_2) = 0.5(3.5)+0.5(5) = 4.25\) when \(S_0=3\).

When \(S_0 = 4\), the next step can be 4, 5, or 6 with probabilities .25, .5, and .25, respectively. We have seen the expectations of these three values in one-step are 5, 6, and 7.5, respectively. Thus, \(E(S_2) = 0.25(5)+0.5(6)+0.25(7.5)=6.125\).

Third, we will find the three-step expectations for the initial values 2 and 3.

Again, an intial value of 2 can go to either 2 or 3 with .5 probability each. We just found the two step expectations for 2 and 3 to be 3 and 4.25, respectively. Thus, \(E(S_3) = 0.5(3)+0.5(4.25) = 3.625\) when \(S_0=2\).

An initial value of 3 can go to either 3 or 4 in one step with equal probabilities (.5). The two-step expectations for each of these were 4.25 and 6.125, respectively. Thus, \(E(S_3) = .5(4.25)+.5(6.125) = 5.1875\) when \(S_0=3\).

Finally, we find \(E(S_4)\) for the initial condition \(S_0=2\). As this sum will go to either 2 or 3 with a 50% chance each, and their 3-step expectations were calculated above, we find \(E(S_4) = 0.5(3.625)+0.5(5.1875) = 4.40625\).

Let’s build a recursive function that will take any initial sum and any N and return the expected nematode sum.

# A function to compute the expected nematode sum of (S)^N with inputs
# S the sum of any two numbers of nematodes, and N, the exponent. 
ExpNemSum <- function(S,N){
   # the possible number of offspring, x
   x <- seq(0,floor(S/2))
   # the probability of each of these offspring, px
   px <- dbinom(x,floor(S/2),.5)
   # the possible resulting nematode sums
   posNemSums <- seq(S,S+floor(S/2),1)
   # once the exponent is N=1, we return the natural expected value
   if(N==1){
      return(sum(px*posNemSums))
   }
   ## while the exponenet is greater than one, recursively call the function for 
   ## N-1 until we get down to 1. 
   else{
      RecursiveSum <- 0
      indices <- 1:(floor(S/2)+1)
      for(i in indices){
         curS <- posNemSums[i]
         curP <- px[i]
         RecursiveSum <- RecursiveSum + curP*ExpNemSum(curS,N-1)
      }
      return(RecursiveSum)
   }
}

Let’s check the one-step expectations of our calculations above.

ExpNemSum(2,1)
## [1] 2.5
ExpNemSum(3,1)
## [1] 3.5
ExpNemSum(4,1)
## [1] 5
ExpNemSum(5,1)
## [1] 6
ExpNemSum(6,1)
## [1] 7.5

Now, the two-step expectations.

ExpNemSum(2,2)
## [1] 3
ExpNemSum(3,2)
## [1] 4.25
ExpNemSum(4,2)
## [1] 6.125

The three-step expectations:

ExpNemSum(2,3)
## [1] 3.625
ExpNemSum(3,3)
## [1] 5.1875

Finally, the four-step expectation:

ExpNemSum(2,4)
## [1] 4.40625

We’ll use this function for the extra credit.

Extra Credit

Let’s explore \(E(S_N)\) for \(N=1,2,3\), and 4 when \(S_0=2\). These values were 2.5, 3, 3.625, and 4.40625, respectively.

Let’s find the 5th and 6th step expectations using our function.

ExpNemSum(2,5)
## [1] 5.382812
ExpNemSum(2,6)
## [1] 6.603516

Note that 3.625 can be written as 29/8, and that \(4.40625=\frac{141}{32}\), \(5.382812 = \frac{689}{128}\), and \(6.603516 = \frac{3381}{512}\).

It is easy enough to see that the denominators are odd powers of 2, but what is going on with those numerators? The 2-step expectation is 3, which can be written as 6/2, but what about the 1-step? Does it have a denominator of \(2^{-1}\)? If that is the case the numerator would have to be 5/4.

Notice this interesting pattern using some modular arithmentic.

3381%%689
## [1] 625
689%%141
## [1] 125
141%%29
## [1] 25
29%%6
## [1] 5

To follow that up, we find that

3381%%625
## [1] 256
689%%125
## [1] 64
141%%25
## [1] 16
29%%5
## [1] 4

So, we can write \(29=5^2+4^1\), \(141 = 5^3+4^2\), \(689=5^4+4^3\), and \(3381=5^5+4^4\). This hints that the general term is \[ E(S_N) = \frac{5^{N-1}+4^{N-2}}{2^{2N-3}} .\]

Indeed, this even works for \(N=1\)! The numerator is indeed 5/4 with a denominator of \(2^{-1}\).

Now, is there a way to make sense of this pattern in terms of the N-step expectations when \(S_0=2\)? That, I will have to wait for, as I want to do other things this weekend.