Sirisian 2263 Report post Posted October 22, 2008 I'm writing an algorithm, but I need to know something first. Say I have 100 bits and 40 of them are 1s and I take another 100 bits and 40 of them are 1s. What's the probability that when I XOR the two bit vectors that I'll get a bit vector with less than 40 1s. XOR has the truth table: a b q 0 0 0 // No change 0 1 1 // Increase by one 1 0 1 // No change 1 1 0 // Decrease by one So to start I'd just like to find the probability of getting 40 1s. So the number of increases and decreases are equal. Then since I'm actually trying to find the probability of getting less than 40 1s I'd need to find the probability of getting 0-39 and adding the probabilities up. I have no idea how to do this though. I really need to figure this out. Any help would be appreciated. 0 Share this post Link to post Share on other sites
Zipster 2359 Report post Posted October 22, 2008 I totally stumped myself trying to figure this out through permutations, partitions, equivalence classes, and all that fancy stuff they teach you in discrete math, so I'm going to take a different approach with the stuff I learned in my formal probability class [grin]The probably of any given bit in the vector being 1 is 40 out of 100, or 0.4. The probably of any given bit being a 0 in the other vector is 0.6. Then there's two possible ways this can be the case. So the probability of two associated bits (i.e. same index) being different is 0.4*0.6*2 = 0.48. We can then apply the binomial distribution f(k; 100, 0.48) with k = 0 to 39, and add them all up. So f(0; 100, 0.48) = 3.98e-29, f(1; 100, 0.48) = 3.68e-27, etc. It's easy enough to whip up an Excel spreadsheet to do all the calculations for you :) I got a result that seemed to be within the right ballpark, at least. I'm not sure if it's the same probability you'd get via brute-force counting methods, but hopefully it's really close![Edited by - Zipster on October 22, 2008 11:22:03 PM] 0 Share this post Link to post Share on other sites
Raghar 96 Report post Posted October 23, 2008 So you have a two binary numbers 100 bit long with 40 bits set.Because every combination of bits is equaly likely the first number could be set to ...111.Lets look at simplified case. Two 5 bit numbers.The resulting number must have less bits than 2 set. Which means there must be two cancelations. Mere one cancelation would cause two bits surviving.(2/5) * (1/4) = 2/20Now lets look at 10 bit numbers.Result can have at most 3 bits set.After canceling three bits, the resulting number can have at most two bits, and probability of cancelation of three bits is: (2/5) * (3/9) * (1/4)Now you know the algorithm, and you can extend it to 100 bit number. 0 Share this post Link to post Share on other sites
ToohrVyk 1595 Report post Posted October 23, 2008 Since this situation is equivalent when you shuffle the bits of all numbers in the exact same way, consider the first number to be laid out as follows 00..11, as Raghar suggested. The second number contains zeros an ones. Let's define the number of "ones" in the first 60 bits, A1, and the number of "ones" in the last 40 bits, A2. Then, the problem states that A1 + A2 = 40. Because of the nature of XOR, the number of "one" bits in the final result is B = A1 + (40 - A2) = 2 A1. So, the probability of B = 40 is the probability of A1 = 20, and the probability of B ≤ 40 is the probability of A1 ≤ 20.A1 can be expressed as the number of "one" bits that you get if you select 60 random bits out of a set which contains 40 "one" bits. A recursive formula would be here, for the probability of getting N1 "one" bits and N0 "zero" bits out of M1 "one" bits and M0 "zero" bits: P(N1,N0,M1,M0) = M1/(M1+M0) P(N1-1,N0,M1-1,M0) + M0/(M1+M0) P(N1,N0-1,M1,M0-1) = 1 if N1 = N0 = 0 = 0 if N1 < 0 or N0 < 0Applied here, the probability for A1=20 is 4.2%, and for A1≥20 is 7.2%. 0 Share this post Link to post Share on other sites
Rockoon1 104 Report post Posted October 24, 2008 xor cancels out matching 1's..The problem restated:The keno has 100 numbered balls, and 40 of them are drawn at random during a "game."The player selects 40 numbers.The player wins the jackpot if he matches at least 21 numbers What is the probability that the player wins the jackpot?When drawing R numbers from N balls, the number of ways that you can match X numbers is:(R choose X) * ( (N-R) choose (R-X) )So for all X := 21..40, sum the number of ways you can win.And for all X := 0..20, sum the number of ays you can lose.The probability is then Wins / (Wins + Losses)You'll need a bignum package because wins+losses should be a 94 bit number. 0 Share this post Link to post Share on other sites