Solution to The Long Night Riddle

I hope you are here because you already solved the riddle on your own. If not, you are a fool like John Snow that thinks that with courage, every battle can be won!

Start by defining \(p_t=\frac{W_t}{W_t+H_t}\) as the proportion of White Walkers in the battle. If there are \(H_t\) and \(W_t\) and at time \(t\) fighting, in the next period:

• With probability  \(p_t\) Human dies, so there will be \(W_{t+1}=W_{t}+1\) and \(H_{t+1}=H_{t}-1\)
• With probability \(1-p_t\) a White Walker dies, so there will be \(W_{t+1}=W_t-1\) and \(H_{t+1}=H_t\)

Armed with these laws of motion, we can compute the expected number of White Walkers and Humans in the next period, given the White Walkers and Humans in this period. That is:

\begin{align}
E[H_{t+1}]&=p_t(H_t-1)+(1-p_t)H_t\\
E[W_{t+1}]&=p_t(W_t+1)+(1-p_t)(W_t-1)
\end{align}

What to do with that? If the battle is even at time \(t\), it has to, in expectations, be even at time \(t+1\). Therefore the expected ratio of Humans and White Walkers must be constant over the battle.

$$\frac{E[H_{t+1}]}{E[W_{t+1}]}=\frac{p_t(H_t-1)+(1-p_t)H_t}{p_t(W_t+1)+(1-p_t)(W_t-1)}=\frac{H_t}{W_t}$$

WARNING: this expression is wrong! It is the expected ratio what needs to be constant, not the ratio of the expectations. It turns out that when \(W_t\) is large enough, both terms converge. More on that later.

Now, we can write the number of Humans as a fraction of White Walkers, i.e., \(H_t=\kappa W_t\). Substituting in the previous equation, it yields:
$$\frac{\frac{1}{1+\kappa}(\kappa W_t-1)+\frac{\kappa}{1+\kappa}\kappa W_t}{\frac{1}{1+\kappa}(W_t+1)+\frac{\kappa}{1+\kappa}(W_t-1)}=\kappa$$

Simplifying:
$$\frac{(\kappa W_t-1)+\kappa^2 W_t}{(W_t+1)+\kappa(W_t-1)}=\kappa$$

And with further simplification, (\kappa\) is the solution to:
$$\kappa^2-\kappa-1=0$$

The solution is \(1.6180339\), or \(\frac{1+\sqrt{5}}{2}\). Does this number say something to you? The golden ratio! How beautiful it is?

As it was noted, using the fraction of expectations instead of the expectation of the ratio is wrong, but it is a good approximation when the number of White Walkers and Humans is big enough. This is because while the ratio is constant at \(\kappa\), the covariance term converges to zero, and the expectation of the inverse is the inverse of the expectation.

On can find the exact solution (up to integer constrains), by computing directly the expectation of the ratio, and then solving for \( \kappa(W_t)\). The problem becomes:
$$\frac{H_t}{W_t}=p_t\frac{H_t-1}{W_t+1}+(1-p_t)\frac{H_t}{W_t-1}$$

The solution of this starts at \(1\), because if there is one White Walker, \(1\) Human evens the battle, and as the number of White Walker increases, the solution approaches to the golden number.

Want more fun? A small R code that simulates B battles, given a initial number of White Walkers and Humans.

B<-1000
W<-1000
kappa<-1.6180339
H<-W*kappa
Hwin<-1:B*0
for (b in 1:B){
  Wnext=1
  Hnext=1
  W<-W[1]
  H<-H[1]
  while (min(Wnext,Hnext)>0){
    p<-W[length(W)]/(W[length(W)]+H[length(H)])
    e<-runif(1)
    Hnext<-(e<p)*(H[length(H)]-1)+(e>=p)*H[length(H)]
    H<-c(H,Hnext)
    Wnext<-(e<p)*(W[length(W)]+1)+(e>=p)*(W[length(W)]-1)
    W<-c(W,Wnext)
  }
  Hwin[b]<-(Hnext>0)
}
mean(Hwin)
t<-1:length(H)
plot(t,H,'l',col='darkred',lwd=3,ylim=c(0,max(H,W)))
lines(t,W,col='skyblue',lwd=3)