HP Forums - Birthday paradox, 8^8, etc.

I came across this interesting site earlier this morning:

http://www.8x8x8x8x8x8x8x8.com/

Essentially, it's 8 multiple choice questions, each with 8 different answers, and the goal is to try to match people up with others who provided the same responses for all 8.

I immediately thought of the birthday paradox (which probably says as much about me as my answers would), and ran a few numbers.

The stats at the bottom of the page call out "59,295 TESTS 914 MATCHES". The number of matches seems surprising, but then this wouldn't be a "paradox" if the results weren't counter-intuitive. With a selection space of 8^8 (16,777,216), you hit 50% odds of a collision with a sample size of about 4,822. (Based on solving the approximation 1-e^(-n^2/(2*p))=0.5, where p is the selection space, i.e. 8^8. Running a looping product program on my 32S confirms 49.99% after crunching numbers for a few minutes.)

Now, that's all based on purely random selections, which I'm reasonably certain this data set is not. Some responses will be more popular than others, and there are surely correlations between certain responses on different questions.

How does one calculate the expected number of matches given a sample size (whether it's with the same person or different people is irrelevant)? It wouldn't be a binomial probability distribution, as these are not independent trials. Better yet, how can we empirically obtain a normal distribution of the expected number matches? I'd be interested in finding out how much above the mean they currently are.

Or would it be easier to just break out Visual Studio and Monte Carlo method it for an hour? Smile

I ran a 10,000 trial Monte Carlo using a selection space of 8^8 (16,777,216), and the current population size given on the web site (66,320 tests), and got these results:

Mean number of collisions: 130.9364
Standard deviation: 11.4617

The site reports the current number of matches as 930. I'd say that's just a few standard deviations above the mean! I kind of figured the data would be far from a random distribution.

Hello!

(05-18-2015 02:39 PM)Dave Britten Wrote: [ -> ]I kind of figured the data would be far from a random distribution.

That would be my guess as well. Unfortunately I am not allowed to read the eight questions ("Sorry 8^8 is not yet available in your country at this time. Hopefully a translated version will be available soon." - what nonsense! I don't need a translated version...). I suspect that the eight possible answers will not be randomly distributed, but weighted by to the cultural context - only people from the US seem to be allowed to take the test. So for each question there will be two or maybe three answers getting the majority of clicks. This effectively reduces the 8x8x8x8x8x8x8x8 combinations to something like 2x3x2x3x2x3x2x3.

Regards
Max

(05-19-2015 08:52 AM)Maximilian Hohmann Wrote: [ -> ]Hello!

(05-18-2015 02:39 PM)Dave Britten Wrote: [ -> ]I kind of figured the data would be far from a random distribution.

That would be my guess as well. Unfortunately I am not allowed to read the eight questions ("Sorry 8^8 is not yet available in your country at this time. Hopefully a translated version will be available soon." - what nonsense! I don't need a translated version...). I suspect that the eight possible answers will not be randomly distributed, but weighted by to the cultural context - only people from the US seem to be allowed to take the test. So for each question there will be two or maybe three answers getting the majority of clicks. This effectively reduces the 8x8x8x8x8x8x8x8 combinations to something like 2x3x2x3x2x3x2x3.

Regards
Max

That's kind of weird. You aren't missing too much as far as the questions, though. It's just basic personality/values kind of stuff.

I hope they release the raw data at some point for recreational statistical analysis. Just the 8 selected answers, and the user's country (obtained via IP address) would be all that's necessary.

It's also worth noting that we don't know exactly how they're counting "matches". When I ran the simulation, I counted any insertion collision as one match (10 with the same answers = 9 "matches"). But if they count two in one bucket as one match, three as three, four as six, etc. (i.e. polygon sides + diagonals, n+(n*(n-3))/2), then their numbers would be a lot higher.