Newsgroups: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 24 Jan 91 15:04:35 GMT
Subject: Re: An interesting combinatorical question

ss...@andrew.cmu.edu (Steven M. Stadnicki) asked:

>1) Start with an n-digit number, all 1's.  Continue XORing with
>random n-digit numbers until you reach zero (0's in all places).
>How many steps will this take, on the average?

warw...@batserver.cs.uq.oz.au (Warwick Allison) writes:

>... every XOR operation will have 1/(2^n) chance of producing all zeroes
>(by being equal to the current A value),

Correct.

>so the solution is that, on average, it will take 2^(n-1) XOR
>operations to become all zeroes....

No.  The average number of operations will be 2^n.  In general, if we
take a sequence of independent trials, each with probability p of
success, the average number of trials to the first success is 1/p.

Also, there is one exception to the solution.  When n=0, the average
number of operations is zero, because the n-digit number, all ones, is
in that case also all zeroes.

Dan