Consider two opposing armies of knights armed only with swords. The sizes of these armies are 500 and 300 knights.

When locked in combat with an enemy each knight has even odds of winning or losing. Knights, being chivalrous, prefer single combat and will not double up on their enemies. The extra knights in the larger army will wait until there is a free enemy to fight.

[Essentially the killing power of the larger army is proportional to the size of the smaller army.]

When the dust settles the smaller army is eliminated. How many knights (are expected to) remain in the larger army?

Generalize for two armies of size A and B where A>B.

By the same logic that indicates that, when there are 500 knights on one side and 300 on the other,  the answer will be 200 expected knights left on the larger side at the end of the battle, would indicate that if there were 5 knights on one side and 3 knights on the other, that you'd expect 2 knights to remain on the side that started with 5.

However, in this smaller case, the probabilities of various numbers n of knights remaining is C(5+3-n-1,5-n)/2^(5+3-n). For numbers ranging from 1 to 5 is 15/128, 5/32, 3/16 3/16 and 1/8. The probabilities for 1 to 3 of the smaller party actually being left are 15/128, 5/64 and 1/32. As a check, these probabilities add to 1.

But muliplying the probabilities for the larger party by the numbers left for that probability and adding them together, to give the expected value, results in a value of 303/128 = 2.3671875, rather than 2. And, further, as the question can be interpreted as requiring the expected value given that the larger party has won, this has to be divided by the overall 99/128 probability that the larger party in fact won, making the expected value, given that the larger party in fact won,  3.0606....

For the actual problem, 500 vs 300, the deviation is less pronounced.  There is actually a .9999999999994303757... probability that in fact the larger army wins.  Doing the same calculations as for the smaller case results in an expected value of 200.00000000000219524208... overall of the number of the larger army remaining (including those cases where the larger army lost and had none left), or 200.000000000116120098... if we are given that the larger army in fact won.

 10   for L=500 to 1 step -1
 20    P=combi(800-L-1,500-L)/2^(800-L)
 30    T=T+P
 40    T2=T2+P*L
 90   next
100   print T:print T2:print T2/T

Posted by Charlie on 2005-08-23 14:02:54