[5045] in cryptography@c2.net mail archive
Re: number of ones
daemon@ATHENA.MIT.EDU (Greg Rose)
Thu Jul 1 13:21:59 1999
Date: Thu, 01 Jul 1999 09:42:21 +1000
To: Mike Stay <staym@accessdata.com>
From: Greg Rose <ggr@qualcomm.com>
Cc: coderpunks@toad.com, cryptography@c2.net
In-Reply-To: <377AA332.501A@accessdata.com>
[Protocol question: this is obviously appropriate to coderpunks, but not
cryptography... should I (in future) delete cryptography from the reply list?]
At 17:07 30/06/99 -0600, Mike Stay wrote:
>I wrote
>> What's the average number of ones in a randomly-chosen N-bit number?
>
>Duh..
>Sorry, I was thinking of the average number of bits that change on
>increment. The answer's obviously N/2 for the above.
Good. I thought the first message was a troll.
With probability 1, the bottom bit changes.
With prob 1/2, the bottom bit generates a carry (i.e. when it started as one).
Now you're incrementing an N-1 bit number...
By recursion, the average number of bits which will change is 2 - 2^(1-N).
Obviously as N->infinity, the average number of bits which will change ->2
quite rapidly. In the real world, assume 2 bits change.
regards,
Greg.
Greg Rose INTERNET: ggr@Qualcomm.com
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
