Binary possibilities

volospian · 02-11-2011, 17:08

Guys,

I'm having a mental infarction today. I should be able to solve this puzzle, but I just can't get my head in gear...

If I had a 32 bit binary stream, but I only read the first 26 bits... what percentage of the final numbers *could" be the same as any other number... I thought it was simply the highest 32 bit number minus the highest 26 bit number and then finding the percentage between those two numbers... but I'm not sure it is...

it may help if I explain... we have some 32 bit card readers on our printers and we use the same cards on the door access systems, which, for reasons known only to estates, have 26 bit readers. Now it wasn't a problem until now. They now want to segregate some of the doors off, but we have identified some 32 bit cards that are duplicated in the door system as they have different 32 bit numbers where the difference lies only in the last (or potentially first, depending on how the reader works) 6 bits... so the reader only gets the 26 bits that are the same... does this make sense

so... for example (using 14 bits as it's easier to see) if I had two 14 bit cards with the decimal numbers of 12345 and 14393 the binary streams would look like this

11000000111001
11100000111001

however, if we only read the first 10 (or last, depending on how you read it

) bits they would look like..

0000111001
0000111001

which both add up to 57, so the reader would think they were the same card...

I don't need to know how many are going to be actually identical, just how many could actually report the same as a number already used...

kaiowas · 02-11-2011, 18:06

I reckon it's a 1/(2^26) chance that the door readers would read 2 different 32 bit cards identically.

2^32 is the number of unique numbers that can be represented by the 32 bit cards.
2^26 is the number of unique numbers the door readers can scan.

Think of it this way, if you had a 'full set' of 2^32 unique cards and scanned them all through the door then seperated them out into little piles of which ones scanned with the same number you'd have 2^26 piles each containing 64 (2^32/2^26) cards. If you then took one of the piles and marked all of those 64 cards with an X then mixed all the cards up again and picked one at random there'd be a 64/(2^32) ) (which simplifies to 1/(2^26)) chance that it had an X on it.

EDIT - Was talking rubbish at first, think I've got my head around it now.

volospian · 03-11-2011, 10:36

So.... you're saying that there would be 2^26 "unique" numbers (which makes sense as there are that many potential permutations of the 26 bit portion..) BUT, 64 of the 32 bit cards would have a matching 26 bit number...

so if I had all the possible 32 bit numbers, there would be 64 of those cards that would have the same 26 bit number.

Now this is where my understanding of this branch of maths breaks down... you say it simplifies into a 1/(2^26) chance of getting a card that matches another.

Now, does that mean that if I ordered 2^26 cards, statistically I would only get one pair of cards that match... Kind of like my chances of winning the "matching card" lottery are 1 in 2^26?

Also, is that based upon the chances of hitting a specific number (for exmple, 57) or is this the chance of any card being duplicated at all (if you see what I mean) i.e. Does it make any difference if I don't want any cards to match any other card, not just one specific number?

And, if the chances are 1/(2^26) on a full range of cards, then the chances of hitting a duplicate card in, say 500 cards is, I presume, extremely small?

I ask because we had one yesterday and I really need to know if this is a potential issue that could affect some of our staff, or if it is so improbable that it could drive the starship "Heart of Gold"

Pheebs · 03-11-2011, 12:05

*mind explodes*

Pumpkinstew · 03-11-2011, 14:32

Quote:

Originally Posted by volospian

you say it simplifies into a 1/(2^26) chance of getting a card that matches another.

Now, does that mean that if I ordered 2^26 cards, statistically I would only get one pair of cards that match... Kind of like my chances of winning the "matching card" lottery are 1 in 2^26?

I *think* that 1/2^26 is the chance that two cards selcted at random return the same value.

If you had three cards the chance that 1 of those two returns the same value as the first is 2/2^26. If you had four it becomes 3/2^26. This is intuitive because you double then treble your chances of getting a match.

Now the tricky bit (which I'm a bit uncertain of). You also have to take into account that card two and three might match in a three card system. In which case the top of the fraction becomes 2! (two factorial, 1+2=3). Representing the cases that 1=2, 1=3 and 2=3. And then in a four card system becomes 3!/2^26 (ie 1+2+3 =6/2^26)

So the answer is (N-1)!/2^26 where N is the number of cards you have!

I'm about 90% confident that this is right.

Mark · 03-11-2011, 23:50

It's a variation of the 'birthday problem'...

http://en.wikipedia.org/wiki/Birthday_problem

I don't claim to come even close to understanding all that maths. Maybe 25 years ago I would have come closer, but I've forgotten all that stuff now!

volospian · 04-11-2011, 09:24

Mark, well spotted, that's very similar to what I'm trying to work out. I used to be able to do this about 25 years ago too, but I have forgotten so much of the maths I was taught since then.

Pumpkinstew · 04-11-2011, 13:22

Quote:

Originally Posted by kaiowas

I reckon it's a 1/(2^26) chance that the door readers would read 2 different 32 bit cards identically.

I was worried by this yesterday but now I'm satisfied this is correct since the addional numbers you are unable to read are distributed evenly across the numbers which can be read.
Err, if that's clear.

Once this is established you only have to make the assumption that the cards you have are randomly distributed across the 2^32 space for the equation I gave you to be valid.

Pumpkinstew · 04-11-2011, 14:19

And now I've realised that the equation above goes above 1 way before the 2^32 limit where it should.

I've tried following the Birthday Paradox maths in excel but it runs out of steam at about 150! and just spits out number errors.
You might need something else to get a solution to your problem out.

kaiowas · 04-11-2011, 15:12

Your numbers are getting too big because you are using factorials when you should be using triangular numbers

with n cards the number of pairs is 1+2+3...+(n-1) whereas you are using 1x2x3x...(n-1)

Triangular numbers are calculated as n(n+1)/2 so for 500 cards the total number of pairs would equal 500*501/2 = 125250

and the overall probability of a pair of cards scanning identically within that set of cards is 0.187%

125250/2^26 = 0.00187 (number of pairs x probability of 1 pair matching)

For the general case the probability of a conflict can be calculated as n(n+1)/2^27 where n is the number of cards you have

Incidently if you had 11585 cards you'd be guaranteed that at least one pair would conflict.

02-11-2011, 17:08	#1
volospian Vodka Martini Join Date: May 2009 Posts: 786	Binary possibilities Guys, I'm having a mental infarction today. I should be able to solve this puzzle, but I just can't get my head in gear... If I had a 32 bit binary stream, but I only read the first 26 bits... what percentage of the final numbers *could" be the same as any other number... I thought it was simply the highest 32 bit number minus the highest 26 bit number and then finding the percentage between those two numbers... but I'm not sure it is... it may help if I explain... we have some 32 bit card readers on our printers and we use the same cards on the door access systems, which, for reasons known only to estates, have 26 bit readers. Now it wasn't a problem until now. They now want to segregate some of the doors off, but we have identified some 32 bit cards that are duplicated in the door system as they have different 32 bit numbers where the difference lies only in the last (or potentially first, depending on how the reader works) 6 bits... so the reader only gets the 26 bits that are the same... does this make sense so... for example (using 14 bits as it's easier to see) if I had two 14 bit cards with the decimal numbers of 12345 and 14393 the binary streams would look like this 11000000111001 11100000111001 however, if we only read the first 10 (or last, depending on how you read it) bits they would look like.. 0000111001 0000111001 which both add up to 57, so the reader would think they were the same card... I don't need to know how many are going to be actually identical, just how many could actually report the same as a number already used...

02-11-2011, 18:06	#2
kaiowas The Stig Join Date: Jul 2006 Location: Fightertown USA Posts: 1,458	I reckon it's a 1/(2^26) chance that the door readers would read 2 different 32 bit cards identically. 2^32 is the number of unique numbers that can be represented by the 32 bit cards. 2^26 is the number of unique numbers the door readers can scan. Think of it this way, if you had a 'full set' of 2^32 unique cards and scanned them all through the door then seperated them out into little piles of which ones scanned with the same number you'd have 2^26 piles each containing 64 (2^32/2^26) cards. If you then took one of the piles and marked all of those 64 cards with an X then mixed all the cards up again and picked one at random there'd be a 64/(2^32) ) (which simplifies to 1/(2^26)) chance that it had an X on it. EDIT - Was talking rubbish at first, think I've got my head around it now. __________________ Anal Fish Porn Last edited by kaiowas; 02-11-2011 at 18:16.

03-11-2011, 12:05	#4
Pheebs Deep Throat Join Date: Jul 2006 Posts: 6,512	mind explodes __________________ http://www.spiffingdesigns.co.uk

03-11-2011, 23:50	#6
Mark Screaming Orgasm Join Date: Jul 2006 Location: Newbury Posts: 15,194	It's a variation of the 'birthday problem'... http://en.wikipedia.org/wiki/Birthday_problem I don't claim to come even close to understanding all that maths. Maybe 25 years ago I would have come closer, but I've forgotten all that stuff now! Last edited by Mark; 03-11-2011 at 23:53.

04-11-2011, 14:19	#9
Pumpkinstew Absinthe Join Date: Oct 2007 Location: Mostly Oxford, Sometimes Bristol Posts: 1,156	And now I've realised that the equation above goes above 1 way before the 2^32 limit where it should. I've tried following the Birthday Paradox maths in excel but it runs out of steam at about 150! and just spits out number errors. You might need something else to get a solution to your problem out. __________________ Get old, or die tryin' PSTEWREVIEWS - Chunks of Meaty Reviews, Mixed with Your Five a Day of News, Comment and Opinion, Floating in a Broth of Suspect Grammar and Seasoned Liberally with Mixed Metaphor. Tasty. Last edited by Pumpkinstew; 04-11-2011 at 14:43.

03-11-2011, 10:36	#3
volospian Vodka Martini Join Date: May 2009 Posts: 786	So.... you're saying that there would be 2^26 "unique" numbers (which makes sense as there are that many potential permutations of the 26 bit portion..) BUT, 64 of the 32 bit cards would have a matching 26 bit number... so if I had all the possible 32 bit numbers, there would be 64 of those cards that would have the same 26 bit number. Now this is where my understanding of this branch of maths breaks down... you say it simplifies into a 1/(2^26) chance of getting a card that matches another. Now, does that mean that if I ordered 2^26 cards, statistically I would only get one pair of cards that match... Kind of like my chances of winning the "matching card" lottery are 1 in 2^26? Also, is that based upon the chances of hitting a specific number (for exmple, 57) or is this the chance of any card being duplicated at all (if you see what I mean) i.e. Does it make any difference if I don't want any cards to match any other card, not just one specific number? And, if the chances are 1/(2^26) on a full range of cards, then the chances of hitting a duplicate card in, say 500 cards is, I presume, extremely small? I ask because we had one yesterday and I really need to know if this is a potential issue that could affect some of our staff, or if it is so improbable that it could drive the starship "Heart of Gold"

04-11-2011, 09:24	#7
volospian Vodka Martini Join Date: May 2009 Posts: 786	Mark, well spotted, that's very similar to what I'm trying to work out. I used to be able to do this about 25 years ago too, but I have forgotten so much of the maths I was taught since then.

04-11-2011, 15:12	#10
kaiowas The Stig Join Date: Jul 2006 Location: Fightertown USA Posts: 1,458	Your numbers are getting too big because you are using factorials when you should be using triangular numbers with n cards the number of pairs is 1+2+3...+(n-1) whereas you are using 1x2x3x...(n-1) Triangular numbers are calculated as n(n+1)/2 so for 500 cards the total number of pairs would equal 500*501/2 = 125250 and the overall probability of a pair of cards scanning identically within that set of cards is 0.187% 125250/2^26 = 0.00187 (number of pairs x probability of 1 pair matching) For the general case the probability of a conflict can be calculated as n(n+1)/2^27 where n is the number of cards you have Incidently if you had 11585 cards you'd be guaranteed that at least one pair would conflict. __________________ Anal Fish Porn