In a random sequence of n-bit numbers, what is the average distance apart of each k-bit number and what is the average distance apart of each odd k-bit number.
Numbers are all positive integers.
Definition: An n-bit number is a number consisting of n bits - set or clear.
Definition: A k-bit number is a number of just k set bits and therefore n-k clear bits.
E.g. in an n-bit number with n=8 there are 8 k-bit numbers where k = 1 and 28 k-bit numbers where k = 2.
Let me clarify with an example.
If I generate a sequence of all 256 8-bit numbers at random I will generate k-bit numbers as 1 0-bit number, 8 1-bit numbers, 28 2-bit numbers etc. Note that the list 1, 8, 28, 56, 70, 56, 28, 8, 1 is a row in Pascals triangle.
Taking only the odd values we get 1, 7, 21, 35, 35, 21, 7, 1 - the next lower row of the triangle.
I would like to get an estimate of the mean distance between these numbers.
In one run of my example I get the positions of each odd 2-bit number as [45, 90, 112, 121, 168, 229, 242] giving gaps of [45, 22, 9, 47, 61, 13] and an average gap of 32.83.
I need to predict this average gap for any n and k. This is beyond my schoolboy maths so I hope someone here can help.
In this example a(8,2) = 32.83. What, for example would a(96,13) be, i.e. the average gap between numbers with 13 bits set in a random sequence of 96-bit numbers. And what would o(96,13) be, i.e. the average gap between odd numbers with 13 bits set in a random sequence of 96-bit numbers.
Please assume good randomness and as many trials as needed to achieve stable averages.
Happy with a value derived from a row of Pascals triangle.
Approximate results from trial runs:
o(10,2)=84.75 o(10,3)=26.28 o(10,4)=11.86 o(10,5)=8.0