View Single Post
Old 01-12-2013, 04:46 AM
gah44 gah44 is offline
Invited Guest
Join Date: Jul 2012
Location: Seattle, WA
Posts: 153
Default Re: Computing Pr(f(x) != g(x))

Originally Posted by butterscotch View Post
Yes as you mentioned, covering all the cases of integrations can be tricky.
Another effective method is generating many random points over the X space and simply counting when f and g disagree over those points.
Yes that is another way. Somehow it doesn't seem as satisfying as the analytical solution, even an approximate analytical solution.

As the lines get closer, it takes more and more random points to get enough points to disagree.

Also, as the lines get closer, it is more likely that both go through the same edge of the square, and so the easier to compute integrations are more and more significant.

For the 100 point case, top and bottom gets about 30% of the trials. By symmetry, the left and right case should give the same answer. I separately compute the case where the lines cross inside the square and when they don't. (I could double the trials to make up for the not counted left-right.)

Then there are four (symmetric) cases where both lines go through a top or bottom side and a left or right side. That should get the majority of the rest of the cases.
Reply With Quote