Topic: 0.30 btc bounty: maths help (statistics) (Read 14215 times)

Sorry for resurrecting this ancient thread, but I figure it is already in obsolete, so no one will care.

For some reason, I started thinking about this again.  I had forgotten the part about the Stirling numbers, but I had the "well, duh!" moment when I realized that 6^12 is only about 2 billion, and I might maybe be able to find some sort of computing device capable of iterating all of the combinations.

sorry i thought someone who is familiar with this kind of thing might be able to do it easily. i certainly didn't expect it to take 5 hours for the right person (although i admit it might take me 5 weeks to work it out).

You can check your solution against these exact answers:

0	_	738035/120932352
1	_	586435/10077696
2	_	4301435/20155392
3	_	33057475/90699264
4	_	33616325/120932352
5	_	1145495/15116544
6	_	737353/181398528

I don't think it's a particularly easy problem.
An exact formula for the probability of no matches is

6^-12 * Sum_{k=1..6}(6-k)^6 * C(6,k) * Sum_{j=0..k} (-1)^(k-j) * C(k,j) * j^n

where C(a,b)=a!/(b!*(a-b)!)

but this is a simpler case than the other numbers of matches.

Possibly proper mathematicians have more powerful tools to bring to bear on such problems.

Explaining even this simple formula would take quite a lot of work but if you're willing to crack open a maths book then "Stirling numbers of the second kind" would be a good place to start.

ByteCoin

hours to work out? Come on people this is a permutations 101 question.

I wrote a python code to get a better random sampling that just 5831 iterations.
After running for 1 million iterations it produced the following percents:
matches      count(matches)/1000000*100
0            0.6119
1            5.8219
2            21.3333
3            36.4260
4            27.7966
5            7.6010
6            0.4093

Hopefully this gives us a good check of the solutions we produce.

I'm working on the exact solution now. If you increased the bounty I'd be more inclined to work on it. It may take hours to work out; $6 is great for a 5 minute problem, but for a 5 hr problem it is less attractive.

unfortunately, my spec hasn't really been satisfied yet:


there's no particular real world example yet, although the dice are a good example IF the number is 6, or i suppose you could think of a 9-sided dice if you wanted to work with 9 numbers.

but this knowledge would be handy for many different purposes and i'm a bit sad that i don't remember any of this stuff from school. i'd like to try to get my head around the math again without resorting to buying some old books and studying it for months. combinations and permutations.

Essentially the latter. Do I get the money now?

Is this a real world problem you're trying to solve? What is the range of the "product variations" and how much do you care (in BTC)  about an exact answer?

ByteCoin

i wish i remembered from school what that meant.

thank you bytecoin that is very close to the random data.
to pay the bounty though, i must see how you arrived at your final numbers. did you use a formula or did you write out numbers on a page 46000 times?

i suppose instead of random data i could populate my test table with exactly 1 instance of every combo (46656*46656 records?) and then count the matches, but doing that would assume 'hard-coding' of the number of product variations (6), which i'd rather avoid.

Ahh, good point.

If order doesn't matter, I'm pretty sure it'll just be a binomial distribution.

I have solved the problem but the method would be tedious by hand. If it's an academic problem then there's a better way than mine.
No pairs   1 pair   2 pairs   3 pairs   4 pairs   5 pairs   6 pairs
0.61%   5.82%   21.34%   36.45%   27.80%   7.58%   0.41%

kjj's method cannot succeed. If one party chooses 123456 then we must have at least one match whereas if one party chooses 111111 then there's about 1/3 chance of no matches.

This thread should probably be moved to Bitcoin Forum > Economy > Marketplace > Buying

ByteCoin

Thank you for spotting this, I couldn't figure out why his numbers were so different.

yes he is assuming that the numbers have to be in the exact same order. hence the statement (only 1 out of all possible lists matches the other list 6 times). Numbers can match up in any order.

or your interpretation of my description

it seems extremely unlikely to me given the description, that 0 matches would occur 83% of the time.

here's a few example rows from the data:

[6,3,6,6,3,4] + [6,3,4,3,6,6] = 6 matches
[1,5,2,6,1,5] + [2,3,5,6,5,1] = 5 matches
[4,2,1,1,5,6] + [1,5,3,3,3,1] = 3 matches
[5,6,3,5,5,1] + [1,2,5,4,3,2] = 3 matches
[4,2,5,2,6,6] + [2,1,1,1,1,3] = 1 match
[3,5,5,4,4,5] + [1,1,6,1,6,2] = 0 matches

i can use random.org all day long but i'd much rather find out the actual mathematical formula.

edit: here's some more...

[1,5,2,6,1,5] + [2,3,5,6,5,1] = 5
[4,2,1,1,5,6] + [1,5,3,3,3,1] = 3
[5,6,3,5,5,1] + [1,2,5,4,3,2] = 3
[5,2,6,2,4,1] + [2,5,5,4,3,6] = 4
[1,2,2,5,6,2] + [1,4,3,6,5,6] = 3
[5,6,3,2,2,4] + [1,3,5,3,2,2] = 4
[2,4,3,6,4,1] + [1,5,2,2,2,6] = 3
[3,1,4,3,1,1] + [5,4,1,4,6,2] = 2
[6,3,3,1,3,3] + [4,1,5,6,1,4] = 2
[3,5,1,2,1,1] + [6,4,3,5,2,2] = 3
[5,4,6,3,2,5] + [4,4,3,3,2,1] = 3
[4,6,4,2,4,5] + [3,3,2,1,5,3] = 2
[4,2,5,2,6,6] + [2,1,1,1,1,3] = 1
[1,4,1,1,6,5] + [5,1,1,1,3,3] = 4
[2,2,6,4,4,1] + [1,6,5,3,2,6] = 3
[2,4,5,4,4,3] + [2,4,4,6,2,4] = 4
[3,3,1,5,3,3] + [2,3,2,5,5,6] = 2
[1,1,3,2,2,6] + [6,4,1,3,2,4] = 4
[5,1,2,6,2,1] + [4,6,2,3,3,6] = 2
[6,6,5,2,3,6] + [2,5,5,3,5,2] = 3
[2,1,6,4,2,4] + [4,1,2,6,5,4] = 5
[1,2,5,2,6,1] + [3,5,3,3,2,3] = 2
[3,5,5,5,5,6] + [5,6,6,6,5,1] = 3
[5,2,3,2,4,4] + [4,5,4,1,1,1] = 3
[6,1,5,2,1,4] + [3,3,5,3,3,2] = 2
[1,2,5,6,4,1] + [2,2,5,1,4,3] = 4
[6,2,6,2,3,6] + [3,6,3,1,2,3] = 3
[3,4,2,6,5,1] + [2,6,4,6,6,4] = 3
[6,6,2,2,6,4] + [2,5,5,4,4,3] = 2
[5,4,6,1,4,3] + [6,2,5,3,5,1] = 4
[3,2,4,5,2,2] + [1,5,6,6,3,4] = 3
[1,3,4,1,2,3] + [6,2,6,6,1,4] = 3
[4,1,4,5,4,3] + [5,4,4,6,1,6] = 4
[4,2,4,6,4,5] + [3,2,4,4,6,1] = 4
[6,3,4,6,2,3] + [3,5,1,2,3,4] = 4
[3,5,5,4,4,5] + [1,1,6,1,6,2] = 0
[3,5,1,4,6,1] + [2,3,2,4,3,2] = 2
[6,6,6,4,6,3] + [4,5,6,6,5,6] = 4
[3,2,3,3,6,4] + [3,2,5,6,5,5] = 3
[5,2,6,1,1,1] + [5,6,3,4,3,3] = 2
[3,1,6,6,5,4] + [1,1,1,3,4,5] = 4
[6,5,2,1,2,3] + [6,1,4,1,3,2] = 4
[5,3,4,3,4,4] + [6,6,1,2,5,2] = 1
[5,5,3,4,1,6] + [2,1,1,2,3,2] = 2
[6,5,5,5,1,6] + [4,3,3,6,5,5] = 3
[5,4,3,6,4,2] + [3,2,1,2,1,5] = 3
[2,3,5,1,1,6] + [6,4,5,6,3,2] = 4
[4,6,1,2,6,1] + [2,1,4,4,2,2] = 3
[3,3,1,3,4,1] + [1,4,6,5,4,6] = 2
[4,2,3,5,3,2] + [6,4,4,5,4,6] = 2
[5,2,4,1,6,1] + [6,1,1,2,2,4] = 5
[6,3,4,4,5,5] + [4,2,3,1,4,2] = 3
[5,1,1,1,2,1] + [5,4,6,1,6,5] = 2
[3,4,2,5,4,3] + [4,1,2,3,6,2] = 3
[5,1,5,1,6,3] + [2,1,5,5,5,6] = 4
[6,5,4,3,3,4] + [5,3,4,1,4,1] = 4
[1,3,1,6,6,3] + [1,1,1,4,4,1] = 2
[4,3,4,4,1,2] + [3,6,1,6,1,3] = 2
[5,5,1,1,6,1] + [2,1,1,4,1,2] = 3
[3,6,1,5,1,6] + [2,6,2,6,2,3] = 3
[6,3,5,6,4,5] + [3,1,3,3,1,3] = 1
[6,3,4,3,2,4] + [4,4,4,4,1,3] = 3
[4,2,3,3,5,1] + [5,2,4,6,2,3] = 4
[5,2,1,5,4,2] + [4,3,2,4,6,4] = 2
[6,4,4,3,3,4] + [2,5,4,1,4,5] = 2
[4,2,3,1,4,1] + [1,2,3,5,2,3] = 3
[1,2,4,1,3,3] + [1,6,2,2,3,6] = 3
[1,5,6,5,3,3] + [5,6,5,5,1,4] = 4
[4,5,5,6,1,5] + [4,2,6,4,2,1] = 3
[4,5,3,2,6,6] + [5,4,1,1,6,2] = 4
[1,2,2,5,4,6] + [3,6,2,5,2,1] = 5
[1,2,4,1,5,3] + [3,4,4,1,4,5] = 4
[5,2,5,5,2,1] + [6,2,1,4,3,4] = 2
[4,3,4,1,4,5] + [4,1,3,3,2,1] = 3
[3,1,2,3,2,1] + [1,2,4,1,1,1] = 3
[6,4,5,1,6,4] + [2,6,3,4,5,3] = 3
[4,1,3,5,6,2] + [5,3,1,4,5,4] = 4
[5,5,5,4,4,2] + [5,2,3,3,1,2] = 2
[4,1,5,1,2,5] + [1,5,2,4,4,4] = 4
[5,2,5,2,5,4] + [5,2,5,1,1,5] = 4
[4,3,5,3,4,3] + [1,3,3,4,5,2] = 4
[2,2,4,4,4,4] + [4,2,4,5,6,2] = 4
[4,6,5,3,2,4] + [5,4,5,5,4,6] = 4
[2,1,2,1,2,5] + [4,4,5,1,1,3] = 3
[1,4,6,6,3,6] + [6,5,4,1,4,3] = 4
[5,3,6,2,1,4] + [4,1,6,1,1,6] = 3
[3,2,3,6,3,2] + [6,5,5,4,3,4] = 2
[3,1,5,2,1,1] + [4,3,5,2,2,2] = 3
[4,5,6,2,5,3] + [2,5,4,2,1,3] = 4
[6,6,6,1,4,2] + [2,4,4,5,6,3] = 3

The chance of no matches is what's left, 38880 out of 46656 (6^5 in 6^6) or ~ 83.333%.

Either your simulation, or your description of the problem is wrong, they don't match.

thank you kjj, should i send to your signature address or a different one?

also, for a bonus 0.05, what's the chance that there are no matches?

thanks

edit: i ran the numbers with a lot of data from random.org and after 5831 tries, i got the following ratios, which disagree quite a lot with your figures:

matches   count(matches)   (count(matches)/5831*100)
0   37   0.6345
1   359   6.1567
2   1222   20.9570
3   2099   35.9973
4   1676   28.7429
5   417   7.1514
6   21   0.3601

There are 6^6 possible lists for each party.  The second party's list doesn't matter at all.

6^6 = 46656.

One of the lists matches all six in the second list, so that chance is 1 in 6^6 or 1 in 46656 or ~ 0.0021433%.

Six (6^1) of the lists match in at least 5 places, but one was the answer above, so 5 in 46656 or ~ 0.010716%

Thirty six (6^2) of the lists match in at least 4 places, but 5 matched in 5 places, and 1 matched in six, so 30 in 46656 or ~ 0.0643%

Two hundred sixteen (6^3) of the lists match in at least 3 places, but 36 matched more, so 180 in 46656 or ~ 0.3858%

1296 (6^4) of the lists match in at least 2 places, but 216 already matched, so 1080 in 46656 or ~ 2.314%

7776 (6^5) of the lists match in at least 1 place, but 1296 have already matched, so 6480 in 46656 or ~ 13.88889%

I hope that better explains where all the minuses came from in my first post.

I'd post this in the market place, under the buying subforum, since you're spending bitcoins for a service.

sorry i don't know where it needs to go

yes
sounds correct, give me a few minutes to think about it


Can you simplify them into a % for me? I don't get how to take that statement and work out the 'chance' that it occurs.

Should P1 be equal to P6 (1 in 46656) or am I just guessing wrong on that (wild guess)?

also why is this in development section?

Wording on this one is a little confusing. Don't let the product thing confuse you. You could just as easily say they each roll a die six times (if I am understanding the wording correctly) . and ask if they have matching numbers.

so for example your first "complementary pair" exercise would be translated from

"They have exactly 1 complimentary pair
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B1, B1, B1, B1, B1)"

to
Alice rolled [1,2,3,4,5,6] Bob rolled [1,1,1,1,1,1,]

Since all numbers have an equal chance of being rolled, we can think of the problem as A) What are the chances that Alice and Bob each rolled one 1, B) what are the chances that Alice and Bob each rolled 2 ones, C) What are the chances that Alice and Bob each rolled three ones, etc

I don't want to do your homework for ya, even for money (someone else might though!) but this might help you on your way

In question 6, for example, would lists A1,A1,A1,A1,A1,A1,B1,B1,B1,B1,B1,B1 be equivalent to A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6 for your purposes?

If so, each party will pick one of 6^6 lists, and the other person's choices don't matter, so the chances are 1 in 6^6.

Moving on to question 5, there are 6^1 ways to pick a list that matches in at least 5 places, but one of them is the answer to #6, so the chances are 1 in 6^5 minus 1/6^6.

In question 4, there are 6^2 ways to pick a list that matches in at least 4 places, but some match more, so we have to remove them again.  So, 1 in 6^4 minus 1/6^5 minus 1/6^6.

Question 3, 6^3 possible, minus the extras, so: 1 in 6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Q2: 1 in 6^2 minus 1/6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Q1: 1 in 6^1 minus 1/6^2 minus 1/6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Fact 1:
Alice chooses 6 items from the following list of products:
A1, A2, A3, A4, A5, A6

Fact 2:
Bob chooses 6 items from the following list of products:
B1, B2, B3, B4, B5, B6

Fact 3:
They are free to choose the same product more than once, so for example, Alice might choose to buy the following 6 items:
A1, A1, A2, A2, A2, A6

Fact 4:
Each 'A' product is used with a corresponding 'B' product, so for example, an A5 needs exactly one B5 to be of any use, and a B5 needs exactly one A5 to be useful (Let's call this match a 'complimentary pair').

Questions:

From Bob and Alice's 12 items, what are the chances that:

• They have exactly 1 complimentary pair
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B1, B1, B1, B1, B1)
  
  
• They have exactly 2 complimentary pairs
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B1, B1, B1, B1)
  
  
• They have exactly 3 complimentary pairs
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B1, B2, B3)
  
  
• They have exactly 4 complimentary pairs
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B4, B4)
  
  
• They have exactly 5 complimentary pairs
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B5, B2)
  
  
• They have exactly 6 complimentary pairs
  (eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B5, B6)
  
  

For each correct answer with detailed workings I will give 0.05 btc (~$1) for a total of 0.30 btc (~$6).