Binary possibilities

[volospian]

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:shocked::confused:;D

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]

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]

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]

*mind explodes*

[Pumpkinstew]

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.:cool:

[Mark]

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]

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]

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.:o

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]

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

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]

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.

[Pumpkinstew]

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

Hmm, not sure about that. If you have 2^26 'bins' of 64 cards available to you and you assume that the cards are randomly and equally distributed through the entire range of values then you must need 2^26+1 cards to guarantee a duplicate.

You're right that I wrongly used factorial in my first post though. The wiki description of the birthday problem uses factorials in the soultion though and as best I can tell it's the same problem.

[Mark]

For 100% probability of a duplicate, you would indeed need 2^26+1 cards. I'll take a guess that 11585 is the 'on average' (i.e. 50%) probability.