We can ask, how big is the message after the first gap *s* is
removed. At that point the number of gaps decreases by one, and the
total of the gap widths decreases by *s*.
Subtracting the two sizes gives the number of bits it took to encode *s*.
Let's call this function nbitsC() for Combinatorics:

(1000000 +2Of course this is a division (the inverse of the fraction of messages that start with^{32}-1)! (999999 +2^{32}-1-s)! nbitsC(s)=log_{2}(-----------------) - log_{2}(-----------------) 1000000!(2^{32}-1)! 999999!(2^{32}-1-s)!

(1000000 +2Separating the first factor of the first factorial...^{32}-1)! 999999!(2^{32}-1-s)! nbitsC(s)=log_{2}(-----------------------------------) 1000000!(2^{32}-1)! (999999 +2^{32}-1-s)!

(1000000 +2Canceling and rearranging a bit...^{32}-1) (999999 +2^{32}-1)! 999999!(2^{32}-1-s)! = log_{2}(---------------------------------------------------) 1000000!(2^{32}-1)! (999999 +2^{32}-1-s)!

1000000+2When^{32}-1 (999999 +2^{32}-1 )! (2^{32}-1-s)! = log_{2}(-------------) + log_{2}(----------------------------) 1000000 (999999 +2^{32}-1-s)! (2^{32}-1 )!

1000000+2When s is small, the right term is approximately^{32}-1 nbitsC(0) = log_{2}(-------------) ~= 12.0687673 1000000

999999 +2which is fairly linear until^{32}-1-(s+1)/2 nbitsC(s)-12.0687673 = log_{2}(---------------------) * s 2^{32}-1-(s+1)/2

This page was made with a
php script
and a Python program.
Last change

Up to