Start by defining pt=WtWt+Ht as the proportion of White Walkers in the battle. If there are Ht and Wt and at time t fighting, in the next period:
- With probability pt Human dies, so there will be Wt+1=Wt+1 and Ht+1=Ht−1
- With probability 1−pt a White Walker dies, so there will be Wt+1=Wt−1 and Ht+1=Ht
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:
E[Ht+1]=pt(Ht−1)+(1−pt)HtE[Wt+1]=pt(Wt+1)+(1−pt)(Wt−1)
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.
E[Ht+1]E[Wt+1]=pt(Ht−1)+(1−pt)Htpt(Wt+1)+(1−pt)(Wt−1)=HtWt
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 Wt 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., Ht=κWt. Substituting in the previous equation, it yields:
11+κ(κWt−1)+κ1+κκWt11+κ(Wt+1)+κ1+κ(Wt−1)=κ
Simplifying:
(κWt−1)+κ2Wt(Wt+1)+κ(Wt−1)=κ
And with further simplification, (\kappa\) is the solution to:
κ2−κ−1=0
The solution is 1.6180339, or 1+√52. 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 κ, 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 κ(Wt). The problem becomes:
HtWt=ptHt−1Wt+1+(1−pt)HtWt−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)
E[Ht+1]E[Wt+1]=pt(Ht−1)+(1−pt)Htpt(Wt+1)+(1−pt)(Wt−1)=HtWt
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 Wt 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., Ht=κWt. Substituting in the previous equation, it yields:
11+κ(κWt−1)+κ1+κκWt11+κ(Wt+1)+κ1+κ(Wt−1)=κ
Simplifying:
(κWt−1)+κ2Wt(Wt+1)+κ(Wt−1)=κ
And with further simplification, (\kappa\) is the solution to:
κ2−κ−1=0
The solution is 1.6180339, or 1+√52. 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 κ, 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 κ(Wt). The problem becomes:
HtWt=ptHt−1Wt+1+(1−pt)HtWt−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)
Solution to The Long Night Riddle
Reviewed by marc
on
18:55:00
Rating:
Cap comentari: