|
|
| Author |
Message |
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
 Posted: Wed Jul 05, 2006 1:44 pm Post subject:
Please help me to find a mistake here
|
|
|
[*]
1. Set \Omega is a set of all permutations of {0,1,...,2^32};
2. We choose 2^32 mappings P_i from the set Z(2^32)={0,1,...,2^32} to
a random permutation from the set \Omega uniformly at random;
3. Choose one P_i mapping (uniformly at random) and apply it to the
sequence of 71 numbers {1,2,3...,71};
4. Previous step results in a set of 71 x numbers C'
My calculation is that probability of event E that C' will contain two
pairs (A',A") and (B',B") where A' differs from A" by one bit and B'
differs from B" by one bit is (*):
1-(1-1/2^54)^(n_p*(n_p-1))
:where n_p = (71*70/2) - the number of unordered pairs;
and if we try all 2^32 mappings P_i, then probability that such event E
will occur at least once is (**):
1-(1-1/2^54)^(n_p*(n_p-1)*2^32)
Rationale:
-probability that two randomly chosen 32 bit numbers differs by one bit
is 1/2^27;
-so we get 1/2^54 = (1/2^27)^2 for two pairs (A',A") and (B',B")
-probability that no such event E' will occurs on two randomly chosen
pairs is (1-1/2^54)
-since we have p_n=(71*70/2) unordered pairs - gives us analogy of
running p_n experiments for pair (A', A") and p_n-1 experiments for
pair (B', B"), which gives us p_n * (p_n-1) for number of experiments
- therefore (*) and (**);
I've created a program that attempts to run such experiment over 2^32
mappings (it takes about 17 hours to run such test) and my program
shows that my mistake could not be more than 1/3 of what I get by
calculating (**).
However I could not spot the mistake in neither (*) nor (**)
Could someone please help me to find my mistake.
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 |
|
 |
James Waldby
science forum Guru Wannabe
Joined: 01 May 2005
Posts: 114
|
| Posted: Wed Jul 05, 2006 4:50 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
valery wrote:
| Quote: |
[*]
1. Set \Omega is a set of all permutations of {0,1,...,2^32};
2. We choose 2^32 mappings P_i from the set Z(2^32)={0,1,...,2^32} to
a random permutation from the set \Omega uniformly at random;
3. Choose one P_i mapping (uniformly at random) and apply it to the
sequence of 71 numbers {1,2,3...,71};
4. Previous step results in a set of 71 x numbers C'
My calculation is that probability of event E that C' will contain two
pairs (A',A") and (B',B") where A' differs from A" by one bit and B'
differs from B" by one bit is (*):
1-(1-1/2^54)^(n_p*(n_p-1))
:where n_p = (71*70/2) - the number of unordered pairs;
and if we try all 2^32 mappings P_i, then probability that such event E
will occur at least once is (**):
1-(1-1/2^54)^(n_p*(n_p-1)*2^32)
....
Rationale:
-probability that two randomly chosen 32 bit numbers differs by one bit
is 1/2^27;
-so we get 1/2^54 = (1/2^27)^2 for two pairs (A',A") and (B',B")
-probability that no such event E' will occurs on two randomly chosen
pairs is (1-1/2^54)
[other Rationale etc snipped] |
....
Let Q = prob. of event E that C' contains at least 2 pairs.
You claim Q = (*), but I think the following is more likely.
Let h=32, H=2^32, u=5, U=2^u (so U=h), m=71, and w=m*(m-1)/2.
Let R(k) stand for the probability that k pairs of numbers from
among m distinct numbers from Z(2^h) are 1-bit-distant, and let
x#y mean that x and y do not differ by 1 bit. Let r = probability
that x#y if y is uniformly randomly chosen from Z(2^h)\{x}.
We suppose r = (H-U+1)/(H-1). Now R(0) = r^w,
R(1) = w*(1-r)*r^(w-1), and Q = R(>= 2) = 1 - R(0) - R(1).
-jiw |
|
| Back to top |
|
|
matt271829-news@yahoo.co.
science forum Guru
Joined: 11 Sep 2005
Posts: 846
|
| Posted: Wed Jul 05, 2006 6:14 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
Some questions...
valery wrote:
| Quote: | [*]
1. Set \Omega is a set of all permutations of {0,1,...,2^32};
2. We choose 2^32 mappings P_i from the set Z(2^32)={0,1,...,2^32} to
a random permutation from the set \Omega uniformly at random;
|
Are these random mappings all distinct, or can P_i contain duplicates?
| Quote: | 3. Choose one P_i mapping (uniformly at random) and apply it to the
sequence of 71 numbers {1,2,3...,71};
4. Previous step results in a set of 71 x numbers C'
My calculation is that probability of event E that C' will contain two
pairs (A',A") and (B',B") where A' differs from A" by one bit and B'
differs from B" by one bit is (*):
|
By "two pairs" do you mean *at least* two pairs, or *exactly* two
pairs?
Must A', A'', B and B'' all be distinct? For example, if you were
working with 2^3 rather than 2^32 then would 000, 001, 011 count as two
pairs or not?
| Quote: | 1-(1-1/2^54)^(n_p*(n_p-1))
:where n_p = (71*70/2) - the number of unordered pairs;
and if we try all 2^32 mappings P_i, then probability that such event E
will occur at least once is (**):
1-(1-1/2^54)^(n_p*(n_p-1)*2^32)
Rationale:
-probability that two randomly chosen 32 bit numbers differs by one bit
is 1/2^27;
-so we get 1/2^54 = (1/2^27)^2 for two pairs (A',A") and (B',B")
-probability that no such event E' will occurs on two randomly chosen
pairs is (1-1/2^54)
-since we have p_n=(71*70/2) unordered pairs - gives us analogy of
running p_n experiments for pair (A', A") and p_n-1 experiments for
pair (B', B"), which gives us p_n * (p_n-1) for number of experiments
- therefore (*) and (**);
I've created a program that attempts to run such experiment over 2^32
mappings (it takes about 17 hours to run such test) and my program
shows that my mistake could not be more than 1/3 of what I get by
calculating (**).
|
Hint: when doing stuff like this, it's handy to develop a general
formula with variables standing for the parameters (e.g. 32 and 71
here), and try out the simulation using some small numbers, which is
much quicker. Depending on the particular problem you may be even able
to do an exhaustive search for some small numbers, which will give an
exact answer to check against rather than a ballpark simulation figure.
If your formula works for some non-trivial small numbers then that
gives you some confidence it's correct, and if it doesn't then it's
much easier to work out on paper where it's going wrong.
Also, tests with non-trivial small numbers can often be more diagnostic
when there are issues that definitely need to be considered but whose
effects fade away to almost nothing with large numbers (such as,
perhaps, the issue here of whether A', A'', B and B'' are all
distinct).
| Quote: | However I could not spot the mistake in neither (*) nor (**)
Could someone please help me to find my mistake.
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 |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Wed Jul 05, 2006 6:22 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
James Waldby wrote:
| Quote: | valery wrote:
[*]
1. Set \Omega is a set of all permutations of {0,1,...,2^32};
2. We choose 2^32 mappings P_i from the set Z(2^32)={0,1,...,2^32} to
a random permutation from the set \Omega uniformly at random;
3. Choose one P_i mapping (uniformly at random) and apply it to the
sequence of 71 numbers {1,2,3...,71};
4. Previous step results in a set of 71 x numbers C'
My calculation is that probability of event E that C' will contain two
pairs (A',A") and (B',B") where A' differs from A" by one bit and B'
differs from B" by one bit is (*):
1-(1-1/2^54)^(n_p*(n_p-1))
:where n_p = (71*70/2) - the number of unordered pairs;
and if we try all 2^32 mappings P_i, then probability that such event E
will occur at least once is (**):
1-(1-1/2^54)^(n_p*(n_p-1)*2^32)
...
Rationale:
-probability that two randomly chosen 32 bit numbers differs by one bit
is 1/2^27;
-so we get 1/2^54 = (1/2^27)^2 for two pairs (A',A") and (B',B")
-probability that no such event E' will occurs on two randomly chosen
pairs is (1-1/2^54)
[other Rationale etc snipped]
...
Let Q = prob. of event E that C' contains at least 2 pairs.
You claim Q = (*), but I think the following is more likely.
Let h=32, H=2^32, u=5, U=2^u (so U=h), m=71, and w=m*(m-1)/2.
Let R(k) stand for the probability that k pairs of numbers from
among m distinct numbers from Z(2^h) are 1-bit-distant, and let
x#y mean that x and y do not differ by 1 bit. Let r = probability
that x#y if y is uniformly randomly chosen from Z(2^h)\{x}.
We suppose r = (H-U+1)/(H-1). Now R(0) = r^w,
R(1) = w*(1-r)*r^(w-1), and Q = R(>= 2) = 1 - R(0) - R(1).
|
Thanks! But can you explain a bit your formulas?
I'm not quite sure if that's right. If I simply put your formulas in
pari/gp gives 0.00000000015057...
if we calculate prob. Q' that event E didn't occur; take power Q'^H and
subtract result from one, it gives that probability of getting two
"almost collisions" after 2^32 attempts is about 0.47 (with my formulas
it is about 0.77)
My simulation program finished with 12 experiments with 71 x 32bit
integers (taken by concatenation of SHA1 hashes of files in my
C:\Windows folder). What the program basically does - it tries 2^32
different encryption keys with algorithm with design similar to
Rijndael and checks for two "almost collisions". From 12 experiments
completed by my program I got 8 x 71 that had two "almost collisions",
and only four that didn't have.
I know that my formulas must be wrong because if they are right then it
is possible to prove something that is not possible in reality. Your
formulas give a bit better result when it concerns to reality check
(but they are a bit different than results of my experiment, from
whitch I'd rather expect something like 0.6).
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Wed Jul 05, 2006 6:43 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | Some questions...
valery wrote:
[*]
1. Set \Omega is a set of all permutations of {0,1,...,2^32};
2. We choose 2^32 mappings P_i from the set Z(2^32)={0,1,...,2^32} to
a random permutation from the set \Omega uniformly at random;
Are these random mappings all distinct, or can P_i contain duplicates?
3. Choose one P_i mapping (uniformly at random) and apply it to the
sequence of 71 numbers {1,2,3...,71};
4. Previous step results in a set of 71 x numbers C'
My calculation is that probability of event E that C' will contain two
pairs (A',A") and (B',B") where A' differs from A" by one bit and B'
differs from B" by one bit is (*):
By "two pairs" do you mean *at least* two pairs, or *exactly* two
pairs?
|
At least two pairs.
| Quote: | Must A', A'', B and B'' all be distinct? For example, if you were
working with 2^3 rather than 2^32 then would 000, 001, 011 count as two
pairs or not?
|
They are guaranteed to be distinct by definition of experiment. We are
using bijective mapping defined by a randomly choosen permutation.
| Quote: | 1-(1-1/2^54)^(n_p*(n_p-1))
:where n_p = (71*70/2) - the number of unordered pairs;
and if we try all 2^32 mappings P_i, then probability that such event E
will occur at least once is (**):
1-(1-1/2^54)^(n_p*(n_p-1)*2^32)
Rationale:
-probability that two randomly chosen 32 bit numbers differs by one bit
is 1/2^27;
-so we get 1/2^54 = (1/2^27)^2 for two pairs (A',A") and (B',B")
-probability that no such event E' will occurs on two randomly chosen
pairs is (1-1/2^54)
-since we have p_n=(71*70/2) unordered pairs - gives us analogy of
running p_n experiments for pair (A', A") and p_n-1 experiments for
pair (B', B"), which gives us p_n * (p_n-1) for number of experiments
- therefore (*) and (**);
I've created a program that attempts to run such experiment over 2^32
mappings (it takes about 17 hours to run such test) and my program
shows that my mistake could not be more than 1/3 of what I get by
calculating (**).
Hint: when doing stuff like this, it's handy to develop a general
formula with variables standing for the parameters (e.g. 32 and 71
here), and try out the simulation using some small numbers, which is
much quicker. Depending on the particular problem you may be even able
to do an exhaustive search for some small numbers, which will give an
exact answer to check against rather than a ballpark simulation figure.
If your formula works for some non-trivial small numbers then that
gives you some confidence it's correct, and if it doesn't then it's
much easier to work out on paper where it's going wrong.
|
Thanks for the hint. I thought doing something like that. The problem
is that I used an algorithm design resembling Rijndael (AES), but I
could not make it any shorter than 32 bits, otherwise MixColumns simply
looses meaning and "pseudo-random" permutation is gone...
| Quote: |
Also, tests with non-trivial small numbers can often be more diagnostic
when there are issues that definitely need to be considered but whose
effects fade away to almost nothing with large numbers (such as,
perhaps, the issue here of whether A', A'', B and B'' are all
distinct).
|
yes, they are all distinct.
| Quote: |
However I could not spot the mistake in neither (*) nor (**)
Could someone please help me to find my mistake.
Thanks in advance,
-Valery.
http://www.harper.no/valery
|
thanks again,
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Wed Jul 05, 2006 6:48 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | Some questions...
Must A', A'', B and B'' all be distinct? For example, if you were
working with 2^3 rather than 2^32 then would 000, 001, 011 count as two
pairs or not?
|
actually 000, 001, 011 could count as two pairs (001, 000) and (001,
011), in case if it makes it easier to count probabilities. However
this is degenerate case that is not very interesting for the purposes
of my experiment.
thanks again,
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
matt271829-news@yahoo.co.
science forum Guru
Joined: 11 Sep 2005
Posts: 846
|
| Posted: Thu Jul 06, 2006 1:29 am Post subject:
Re: Please help me to find a mistake here
|
|
|
valery wrote:
| Quote: | matt271829-news@yahoo.co.uk wrote:
Some questions...
Must A', A'', B and B'' all be distinct? For example, if you were
working with 2^3 rather than 2^32 then would 000, 001, 011 count as two
pairs or not?
actually 000, 001, 011 could count as two pairs (001, 000) and (001,
011), in case if it makes it easier to count probabilities. However
this is degenerate case that is not very interesting for the purposes
of my experiment.
|
I was trying to find an exact formula - in which case all these minor
points matter - but it doesn't seem to be particularly easy.
Incidentally, continuing in picky mode, in your original post you said
the numbers were 0,1,...,2^32. Did you actually mean 0,1,...,2^32-1?
Anyway, FWIW, making some simplifying assumptions (that seem entirely
reasonable since 71 is so much smaller than 2^32), I make the
probability of event E equal to about 1.76E-10. I think this is
slightly different from James Waldby's answer. I did it in a slightly
more elaborate way, but with these particular numbers I would have
thought the answers should differ by only an imperceptible amount. I'm
not sure at the moment why the answers differ as much as they do, but
if I get a following wind I might try to pick through it and figure it
out. |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Thu Jul 06, 2006 4:48 am Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | valery wrote:
matt271829-news@yahoo.co.uk wrote:
Some questions...
Must A', A'', B and B'' all be distinct? For example, if you were
working with 2^3 rather than 2^32 then would 000, 001, 011 count as two
pairs or not?
actually 000, 001, 011 could count as two pairs (001, 000) and (001,
011), in case if it makes it easier to count probabilities. However
this is degenerate case that is not very interesting for the purposes
of my experiment.
I was trying to find an exact formula - in which case all these minor
points matter - but it doesn't seem to be particularly easy.
Incidentally, continuing in picky mode, in your original post you said
the numbers were 0,1,...,2^32. Did you actually mean 0,1,...,2^32-1?
Yes, I meant 0,1,...,2^32-1. sorry for confusions. |
| Quote: | Anyway, FWIW, making some simplifying assumptions (that seem entirely
reasonable since 71 is so much smaller than 2^32), I make the
probability of event E equal to about 1.76E-10. I think this is
slightly different from James Waldby's answer. I did it in a slightly
more elaborate way, but with these particular numbers I would have
thought the answers should differ by only an imperceptible amount. I'm
not sure at the moment why the answers differ as much as they do, but
if I get a following wind I might try to pick through it and figure it
out.
Thanks! I'm really looking forward to it. |
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Thu Jul 06, 2006 6:00 am Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | Anyway, FWIW, making some simplifying assumptions (that seem entirely
reasonable since 71 is so much smaller than 2^32), I make the
probability of event E equal to about 1.76E-10. I think this is
slightly different from James Waldby's answer. I did it in a slightly
more elaborate way, but with these particular numbers I would have
thought the answers should differ by only an imperceptible amount. I'm
not sure at the moment why the answers differ as much as they do, but
if I get a following wind I might try to pick through it and figure it
out.
1.76E-10 sounds just perfect! it passes reality check and is very well |
aligned with my experiment (taking your numbers gives us about 0.58
probability that event E occurs at least once per 2^32 attempts).
Could you post your formulas, please? (with some explanations if
possible  .
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
matt271829-news@yahoo.co.
science forum Guru
Joined: 11 Sep 2005
Posts: 846
|
| Posted: Thu Jul 06, 2006 5:37 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
valery wrote:
| Quote: | matt271829-news@yahoo.co.uk wrote:
Anyway, FWIW, making some simplifying assumptions (that seem entirely
reasonable since 71 is so much smaller than 2^32), I make the
probability of event E equal to about 1.76E-10. I think this is
slightly different from James Waldby's answer. I did it in a slightly
more elaborate way, but with these particular numbers I would have
thought the answers should differ by only an imperceptible amount. I'm
not sure at the moment why the answers differ as much as they do, but
if I get a following wind I might try to pick through it and figure it
out.
1.76E-10 sounds just perfect! it passes reality check and is very well
aligned with my experiment (taking your numbers gives us about 0.58
probability that event E occurs at least once per 2^32 attempts).
Could you post your formulas, please? (with some explanations if
possible .
-Valery.
http://www.harper.no/valery
|
How do you get 0.58? I make 1 - (1 - 1.76E-10)^(2^32) equal to about
0.53... Incidentally, I don't think that your eight-out-of-twelve
experimental result is particularly diagnostic when discriminating
between the various suggested answers. With such a small number of
trials the experimental results are consistent with a fairly wide range
of actual probabilities.
Anyway. As understand it, to calculate Pr(E), the probability of event
E, we need to select 71 different numbers randomly from the numbers 0
to 2^32 - 1, and find the probability that at least two pairs differ by
exactly one bit. I will let k = 71 and n = 32. The exact answer looks
rather difficult to compute (unless I'm missing something obvious), but
as a simplification one can assume that all the pairs in the set of k
numbers can be considered independently.
The simplest way to do this is something along the lines of the method
that I think James Waldby used, and I'll use some of his notation for
consistency. The probability that any individual pair of (distinct)
numbers does NOT differ by exactly one bit is, as far as I can see,
given by r = (2^n - (n + 1))/(2^n - 1). The first number can be chosen
anyhow, and the second number can be chosen as any of 2^n - (n+1) out
of the remaining 2^n - 1. However, this is different from James'
answer, which I think has r = (2^n - n + 1)/(2^n - 1).
There are w = k*(k - 1)/2 pairs of numbers to consider, and, treating
all these as independent, the probability, R(x), that exactly x of
these pairs differ by just one bit is given by the binomial
distribution, R(x) = C(w,x)*r^(w - x)*(1 - r)^x. This gives
R(0) = r^w
R(1) = w*r^(w - 1)*(1 - r)
and then
Pr(E) = 1 - R(0) - R(1)
Using this method I get Pr(E) = 1.7133E-10, approx. (The difference
between this answer and your previous value of 1.5057E-10 is due to my
and James' slightly differing formulas for r.)
You can easily see by experimenting with some small values of n and k
that this answer is not exactly right. This is because the pair
probabilities aren't really independent as we assumed they were. One
would expect the difference to be very small though, since k is so much
smaller than 2^n.
I also tried a more elaborate method, as follows:
R(0) = 2^n * (2^n - (n+1)) * (2^n - 2*(n+1)) * ... * (2^n - (k -
1)*(n+1)) / (k! * C(2^n,k))
R(1) = 2^n * n * (2^n - 2*n) * (2^n - 2*n - (n+1)) * (2^n - 2*n -
2*(n+1)) * ... * (2^n - 2*n - (k - 3)*(n+1)) / (2*(k-2)!* C(2^n,k))
Here I am looking at the ways that each of the k numbers can be chosen
in turn from the 2^n candidates so as to meet the criteria. So, for
R(0), the first number can be any of the 2^n, the second any of 2^n -
(n+1), the third any of 2^n - 2*(n+1), and so on. Then we divide by k!
to compensate for multiple counting, and finally divide by the total
number of ways of choosing k from 2^n to get the probability. R(1) is
calculated in a similar way.
This method is not exact either, because when we reduce the count of
candidate numbers by n+1 each time we are potentially double-counting.
Using this second method I get Pr(E) = 1.7611E-10, approx. Even though
the two answers are closer than before I am still slightly surprised
that the difference is this large. Initially I managed to convince
myself that the second method ought to be more accurate, but I'm not
sure.
One final point. In your original post you didn't specify whether the
2^32 random mappings are all distinct. In other words, are they chosen
randomly from the total population of permutations with or without
replacement? Strictly speaking, the 1 - (1 - Pr(E))^(2^32) formula is
correct only if they are chosen with replacement (duplicates possible),
but I think the difference here will be truly minuscule for the numbers
in question. |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Thu Jul 06, 2006 8:33 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | How do you get 0.58? I make 1 - (1 - 1.76E-10)^(2^32) equal to about
0.53... Incidentally, I don't think that your eight-out-of-twelve
experimental result is particularly diagnostic when discriminating
between the various suggested answers. With such a small number of
trials the experimental results are consistent with a fairly wide range
of actual probabilities.
Anyway. As understand it, to calculate Pr(E), the probability of event
E, we need to select 71 different numbers randomly from the numbers 0
to 2^32 - 1, and find the probability that at least two pairs differ by
exactly one bit. I will let k = 71 and n = 32. The exact answer looks
rather difficult to compute (unless I'm missing something obvious), but
as a simplification one can assume that all the pairs in the set of k
numbers can be considered independently.
The simplest way to do this is something along the lines of the method
that I think James Waldby used, and I'll use some of his notation for
consistency. The probability that any individual pair of (distinct)
numbers does NOT differ by exactly one bit is, as far as I can see,
given by r = (2^n - (n + 1))/(2^n - 1). The first number can be chosen
anyhow, and the second number can be chosen as any of 2^n - (n+1) out
of the remaining 2^n - 1. However, this is different from James'
answer, which I think has r = (2^n - n + 1)/(2^n - 1).
There are w = k*(k - 1)/2 pairs of numbers to consider, and, treating
all these as independent, the probability, R(x), that exactly x of
these pairs differ by just one bit is given by the binomial
distribution, R(x) = C(w,x)*r^(w - x)*(1 - r)^x. This gives
R(0) = r^w
R(1) = w*r^(w - 1)*(1 - r)
and then
Pr(E) = 1 - R(0) - R(1)
Using this method I get Pr(E) = 1.7133E-10, approx. (The difference
between this answer and your previous value of 1.5057E-10 is due to my
and James' slightly differing formulas for r.)
You can easily see by experimenting with some small values of n and k
that this answer is not exactly right. This is because the pair
probabilities aren't really independent as we assumed they were. One
would expect the difference to be very small though, since k is so much
smaller than 2^n.
I also tried a more elaborate method, as follows:
R(0) = 2^n * (2^n - (n+1)) * (2^n - 2*(n+1)) * ... * (2^n - (k -
1)*(n+1)) / (k! * C(2^n,k))
R(1) = 2^n * n * (2^n - 2*n) * (2^n - 2*n - (n+1)) * (2^n - 2*n -
2*(n+1)) * ... * (2^n - 2*n - (k - 3)*(n+1)) / (2*(k-2)!* C(2^n,k))
Here I am looking at the ways that each of the k numbers can be chosen
in turn from the 2^n candidates so as to meet the criteria. So, for
R(0), the first number can be any of the 2^n, the second any of 2^n -
(n+1), the third any of 2^n - 2*(n+1), and so on. Then we divide by k!
to compensate for multiple counting, and finally divide by the total
number of ways of choosing k from 2^n to get the probability. R(1) is
calculated in a similar way.
This method is not exact either, because when we reduce the count of
candidate numbers by n+1 each time we are potentially double-counting.
Using this second method I get Pr(E) = 1.7611E-10, approx. Even though
the two answers are closer than before I am still slightly surprised
that the difference is this large. Initially I managed to convince
myself that the second method ought to be more accurate, but I'm not
sure.
One final point. In your original post you didn't specify whether the
2^32 random mappings are all distinct. In other words, are they chosen
randomly from the total population of permutations with or without
replacement? Strictly speaking, the 1 - (1 - Pr(E))^(2^32) formula is
correct only if they are chosen with replacement (duplicates possible),
but I think the difference here will be truly minuscule for the numbers
in question.
Thanks! |
Your help is highly apprecited!
-Valery
http://www.harper.no/valery |
|
| Back to top |
|
|
valery
science forum beginner
Joined: 16 Jun 2006
Posts: 10
|
| Posted: Thu Jul 06, 2006 8:49 pm Post subject:
Re: Please help me to find a mistake here
|
|
|
matt271829-news@yahoo.co.uk wrote:
| Quote: | valery wrote:
matt271829-news@yahoo.co.uk wrote:
How do you get 0.58? I make 1 - (1 - 1.76E-10)^(2^32) equal to about
0.53... Incidentally, I don't think that your eight-out-of-twelve
experimental result is particularly diagnostic when discriminating
between the various suggested answers. With such a small number of
trials the experimental results are consistent with a fairly wide range
of actual probabilities.
btw. 0.58 was a typo (that supposed to be 0.528 |
-Valery.
http://www.harper.no/valery |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jul 30, 2010 5:36 am | All times are GMT
|
|
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
