0.30 btc bounty: maths help (statistics)

[untitlednotepad]

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).

[kjj]

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.

[lemonginger]

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

[lemonginger]

also why is this in development section?

[untitlednotepad]

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?

yes

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.

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

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

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)?

[untitlednotepad]

also why is this in development section?

sorry i don't know where it needs to go

[AllYourBase]

also why is this in development section?

sorry i don't know where it needs to go

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

[kjj]

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.

[untitlednotepad]

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

[kjj]

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.

[untitlednotepad]

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.

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

[lemonginger]

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.

[untitlednotepad]

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.

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

[ByteCoin]

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

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

[kjj]

Ahh, good point.

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

[untitlednotepad]

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

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

[untitlednotepad]

it'll just be a binomial distribution.

i wish i remembered from school what that meant.

[ByteCoin]

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?

Essentially the latter. Do I get the money now?

doing that would assume 'hard-coding' of the number of product variations (6), which i'd rather avoid.

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

[untitlednotepad]

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

For each correct answer with detailed workings

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.

[UniverseMan]

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

I wrote a python code to get a better random sampling that just 5831 iterations.

Code:

from __future__ import division
import random

pairs =	[0]*7
iterations = 1000000
for iter in range(iterations):
    list = [ [random.randint(1,6) for i in range(6)] for j in 0,1]

    equalList = [ [a==b for b in list[1]] for a in list[0] ]

    equalCount = 0
    truePos = []
    for el in equalList:
	if len(truePos)>0:
            for	pos in truePos:
		el[pos] = False
        if any(el):
            equalCount += 1
            truePos.append( el.index(True) )

    pairs[equalCount] += 1

pct = [str(round(pair/iterations*100,4)) for pair in pairs]
print pct

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.