1
$\begingroup$

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
$\endgroup$
4
  • $\begingroup$ I don't understand: how is $90$ an odd 2-bit number? How is it odd? How is it a 2-bit number, under either your n-bit definition or your k-bit definition? $\endgroup$
    – Henry
    Aug 11 '13 at 1:00
  • $\begingroup$ @Henry - The first odd 2-bit number in my trial run occurred at position 45 (it could have been 3 or 5 or 9 or 17 or 33 or 65 or 129), the second odd 2-bit number occurred at position 90 in the sequence. Does that help? $\endgroup$ Aug 11 '13 at 1:04
  • $\begingroup$ It still seems strange, but I starting to understand what you are saying. $\endgroup$
    – Henry
    Aug 11 '13 at 1:11
  • $\begingroup$ Perhaps if you ignore the odd requirement it will begin to make sense. I am sure I will be able to extend any ideas you have to only work with odd numbers - it looks like all I need to do is step up one row in Pascals Triangle. $\endgroup$ Aug 11 '13 at 1:16
2
$\begingroup$

If you have $p$ people arranged in a row at random and $s$ of them are special, then the expected average gap between special people is $\frac{p+1}{s+1}$. Imagine having an additional special person, and arranging all $p+1$ people round a circular table with $s+1$ gaps between the special people: the gaps are identically distributed so each have the same expectation, whether or not you ignore the gaps next to the additional person.

So all you need to do is find $s$ and $p$ for your particular question.

There are $2^n$ numbers with $n$ bits. ${n \choose k}$ of them have $k$ bits set, and ${n-1 \choose k-1}$ have $k$ bits set including the last one: these are the numbers in Pascal's triangle you have found.

So the answer to your not-necessarily-odd question is $\dfrac{2^n+1}{{n \choose k}+1}$, while the answer to your odd question is $\dfrac{2^n+1}{{n-1 \choose k-1}+1}$.

If $n=8$ and $k=2$ then this last expression is $\dfrac{257}{8}=32.125$, so your random example of $32.83$ was not too far away. For $n=10$ and $k=2,3,4,5$ it gives about $102.5, 27.7, 12.1, 8.1$, and if I were you I would check the first of these.

$\endgroup$
3
  • $\begingroup$ That all looks spot on. Could you expand a little on ${n \choose k}$ please? My schoolboy maths is a little rusty I'm afraid. I'm happy with the discrepancy between my 84.75 against your 102.5, after all this was just one sample run. $\endgroup$ Aug 11 '13 at 17:35
  • $\begingroup$ ${n \choose k}$ is the number of ways of choosing $k$ different items from $n$ possibilities. Its value appears in Pascal's triangle in the $n$th row, $k$th item along (both counts starting at $0$). Using factorials ${n \choose k}=\frac{n!}{k! (n-k)!}$. For example ${5 \choose 2} = 10$ as there are $10$ was of choosing two items from five. $\endgroup$
    – Henry
    Aug 11 '13 at 18:00
  • $\begingroup$ Works a treat - perfect! $\endgroup$ Aug 12 '13 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.