|
|
| Author |
Message |
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
 Posted: Fri Jun 16, 2006 8:23 am Post subject:
Pls. help to count probabilities
|
|
|
Note [*]
Let say we've chose two 32 bit numbers A and B uniformly at random.
That mean that probability of their XOR to be equal to a chosen number
C will be (1/2)^32.
1. From that would it be correct to say that probability that numbers A
and B differs in only by one bit is (1/2)^27? (rationale: we have 32
numbers that are powers of 2 in 32 bit number => probability that A XOR
B is equal one of them is 32/(2^32) = (1/2)^27)
2. What would be probability that A and B are different in only two
bits?
3. If we define a "good" set to be 1/8 th of all 32 bit numbers, then
what is probability that both A and B falls to a "good" set and are
different by a). 1 bit; b). 2 bits.
4. How these probabilities change if A and B will be two distinct 32
numbers that are chosen uniformly at random (i.e. we first pick A from
all 32 bits numbers and than we pick B from {0...2^32}\A.
Thanks in advance,
-Valery.
http://www.harper.no/valery
[*] this is not homework (just to avoid flame-baits). I've graduated 20
years ago and my math is a bit rusty today. |
|
| Back to top |
|
 |
bert
science forum addict
Joined: 04 Jan 2006
Posts: 54
|
| Posted: Fri Jun 16, 2006 8:53 am Post subject:
Re: Pls. help to count probabilities
|
|
|
valery wrote:
| Quote: | Note [*]
Let say we've chose two 32 bit numbers A and B uniformly at random.
That mean that probability of their XOR to be equal to a chosen number
C will be (1/2)^32.
1. From that would it be correct to say that probability that numbers A
and B differs in only by one bit is (1/2)^27? (rationale: we have 32
numbers that are powers of 2 in 32 bit number => probability that A XOR
B is equal one of them is 32/(2^32) = (1/2)^27)
2. What would be probability that A and B are different in only two
bits?
3. If we define a "good" set to be 1/8 th of all 32 bit numbers, then
what is probability that both A and B falls to a "good" set and are
different by a). 1 bit; b). 2 bits.
4. How these probabilities change if A and B will be two distinct 32
numbers that are chosen uniformly at random (i.e. we first pick A from
all 32 bits numbers and than we pick B from {0...2^32}\A.
Thanks in advance,
-Valery.
http://www.harper.no/valery
[*] this is not homework (just to avoid flame-baits). I've graduated 20
years ago and my math is a bit rusty today.
|
1. Correct. Another rationale is that given A, the number of choices
of B which give the desired result is exactly 32 out of 2^32.
2. There are (32 * 31 / 2) instances of the desired XOR result, so
the same number of choices of B, approximately 1 in 2^23.
3. Surely just multiply the probabilities above by 1 in 2^6, for the
further independent probability that both A and B are "good".
4. B distinct from A changes the probability that their XOR would
be zero, from 1 in 2^32 to zero. It increases the other
probabilities by a factor of 1 in 2^32, since it makes one
unsuccessful outcome impossible.
-- |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Fri Jun 16, 2006 9:44 am Post subject:
Re: Pls. help to count probabilities
|
|
|
Thanks Bert!
-Valery.
http://www.harper.no/valery
bert wrote:
| Quote: | valery wrote:
Note [*]
Let say we've chose two 32 bit numbers A and B uniformly at random.
That mean that probability of their XOR to be equal to a chosen number
C will be (1/2)^32.
1. From that would it be correct to say that probability that numbers A
and B differs in only by one bit is (1/2)^27? (rationale: we have 32
numbers that are powers of 2 in 32 bit number => probability that A XOR
B is equal one of them is 32/(2^32) = (1/2)^27)
2. What would be probability that A and B are different in only two
bits?
3. If we define a "good" set to be 1/8 th of all 32 bit numbers, then
what is probability that both A and B falls to a "good" set and are
different by a). 1 bit; b). 2 bits.
4. How these probabilities change if A and B will be two distinct 32
numbers that are chosen uniformly at random (i.e. we first pick A from
all 32 bits numbers and than we pick B from {0...2^32}\A.
Thanks in advance,
-Valery.
http://www.harper.no/valery
[*] this is not homework (just to avoid flame-baits). I've graduated 20
years ago and my math is a bit rusty today.
1. Correct. Another rationale is that given A, the number of choices
of B which give the desired result is exactly 32 out of 2^32.
2. There are (32 * 31 / 2) instances of the desired XOR result, so
the same number of choices of B, approximately 1 in 2^23.
3. Surely just multiply the probabilities above by 1 in 2^6, for the
further independent probability that both A and B are "good".
4. B distinct from A changes the probability that their XOR would
be zero, from 1 in 2^32 to zero. It increases the other
probabilities by a factor of 1 in 2^32, since it makes one
unsuccessful outcome impossible.
-- |
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 2:28 am | All times are GMT
|
|
Ringtones | Make Money From Home | Discount Magazine Subscriptions | Facebook Proxy | Debt Consolidation
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
