Probability

Well I think I understand the stars and bars thing. We have 14 stars for the 14 votes and 6 bars to separate the 7 candidates (bins). There are 15 possible positions for the bars, as they can go on either side of any star (ie on each end of the row of stars, or between any two stars). Hence you get the binomial:

(15)
( 6)

which is saying you have 6 things to put in 15 positions, and you don’t care about the order of the things, so it’s a standard combination thing.

That evaluates as: 15! / ((15-6)! * 6!) = 5005 different voting combinations, which is less than you might have thought.

Stoner, could you add in the number of times those other options occur? You seem to be on top of that, and my brain is a bit frazzled with working out what the stars and bars thing means (though it’s actually a lot simpler than it seems). We’ll then have an answer…

Definitely doable from 5005 possibilities by brute force, provided you can manage an efficient way of enumerating those possibilities.

Isn’t it 7 times 1/(7*7*7*7*7*7*7*7) ?
Once upon a time I could do maths, now it’s all gone. 🙁

…oh, but 5005 seemed far too small, and I realised why, and why the stars and bars thing is useless. That only counts one for each voting possibility, which doesn’t work for doing the probabilities as there are different probabilities of each voting possibility (clearly there is only one way for a single candidate to get 14 votes, but lots of different ways for each candidate to get 2 votes). Unfortunately Stoner’s options occurrence suffers from a similar problem, so back to the drawing board…

…so the actual number of possibilities is 7^14 and the question remains; out of those possibilities how many times do you get 2 candidates with 7 votes each, etc.

Though actually that one’s fairly easy: 7 * 6 * (14! / (7! * 7!)) = 144144

just 7 other options to go

…by jove I think I’ve got this:

possibilities for 2 candidates with 6 votes each: 7 * 6 * (14! / (6! * 8!)) * (8! / (6! * 2!)) = 3531528

…I reckon I can work out possibilities for all of Stoner’s original list, but it gets very tricky working out my extra ones

It’s easier as in the OP, just looking for a majority.
Excel is currently running a fairly simple macro randomly simulating this.
But not sure how to check for the revised question.

You’re doing a monte carlo? Brute force in C was looking like several hours at least (might leave that running overnight if I’ve got no further).

Not sure if it’s Monte Carlo (never had to do that for work).

Just an Excel macro, randomly picks a number between 1 and 7, repeat 14 times, stores the result in an array (adds to the existing score), checks if any have >= 8, increments score counter if true.
Repeat many times. (50000 takes about 5 minutes).

Looks like about 85 cases with a majority in 50000 attempts, or about 0.0017

It will be much harder to check for just a winner, I’d have to check each candidates score against all the others to find a winner.

What you describe there is a monte carlo sim https://en.wikipedia.org/wiki/Monte_Carlo_method

It is indeed harder to check for a clear winner – my brute force checks every possibility and whilst I have a test for that, it’s far more complex and will make a huge difference to run time. Not that I’ve run it with 14 voters even for the simple case – takes a while to do 12 voters.

Do you assume all 14 vote? (or 12)

I’m assuming as many vote as I’m running the code for. Clearly it takes 49 times longer to run for 14 as 12.

Probability for a majority is about 0.0017.

If you find the candidate with the most votes, then see if this value is unique, this should say if there’s a clear winner. Doesn’t seem to take too long.

A lot longer than just counting votes for one candidate, which is all I’m doing at the moment.

Takes 6 minutes for a run with 12 voters, so about 5 hours to do the run for 14. I’ll try timing the other test.

I suspect I could make my current algorithm a lot more efficient, but then what I’d do for that wouldn’t help at all with the more complex test. I was also just trying to use the brute force just to help with my understanding, which is where my efficiency improvements are taking me.

Seems a bit too easy. Excel says the probability of a clear winner is about 0.66.

What @rich has done sounds right to me in terms of the method and as he says that’s fairly quick to run which is what I’d expect.

Bingo! I reckon I can do it numerically, applying the same principles as before, but making use of again finding the inverse for the difficult ones.

So the cases we want to find where there isn’t a clear winner are (based on Stoner’s list):
a) 2 candidates get 7 votes each
b) 2 candidates get 6 votes each
c) 2 candidates get 5 votes each
d) 2 candidates get 4 votes each; none of the rest gets more than 4 votes
e) 2 candidates get 3 votes each; none of the rest get more than 3 votes
f) 7 candidates get 2 votes each – or 2 candidates get 2 votes each; none of the rest get more than 2 votes

Already done a and b, c follows the same formula. Do the same thing for d and e and then work out the number of cases where one of the remaining candidates gets more votes to subtract from that. Not quite sure how to do f yet…

Which gives total cases for no clear winner – divide by 7^14 to get probability of no clear winner, and subtract that from one.

I’ve been watching the rugby. Now I’m off to bed. You’re on your own, aracer 🙂

I look forward to returning tomorrow to digest your crunchings

Not sure I’m going to do it by then, busy carving pumpkins.

Glad I did the brute force thing, as it’s helping to confirm my calcs (I’m scaling down the formulae to smaller numbers to check).

0.6612

Let me update you on where I am, some corrections from last night, having realised why I was getting differences from my brute force for fewer voters:

Total number of vote combinations = 7^14 = 678223072849

Cases where there isn’t a clear winner:
a) 2 candidates get 7 votes each
b) 2 candidates get 6 votes each
c) 2 candidates get 5 votes each
d) 2 candidates get 4 votes each; none of the rest gets more than 4 votes
e) 2 candidates get 3 votes each; none of the rest get more than 3 votes
f) 7 candidates get 2 votes each – or 2 candidates get 2 votes each; none of the rest get more than 2 votes

a) = (7! / (5! * 2!)) * (14! / (7! * 7!)) = 72072
b) = (7! / (5! * 2!)) * (14! / (6! * 8!)) * (8! / (6! * 2!)) * 5^2 = 44144100
c) = (7! / (5! * 2!)) * (14! / (5! * 9!)) * (9! / (5! * 4!)) * 5^4 = 3310807500
d) = (7! / (5! * 2!)) * (14! / (4! * 10!)) * (10! / (4! * 6!)) * 5^6
– probability of one candidate getting 5 or more votes from 6 voters = ?
e) = (7! / (5! * 2!)) * (14! / (3! * 11!)) * (11 / (3! * 8!)) * 5^8
– probability of one candidate getting 3 or more votes from 8 voters = ?

is officially confused and out of his depth

Assuming a majority winner means one candidate has 8 or more votes:

Number of voters N = 14
Number of candidates C = 7
Possible permutations = C^N = 6.78E11

Consider candidate A: they have a majority if they have 8,9,10,11,12,13 or 14 votes. Need to evaluate the number of permutations where this is the case.

Let number of votes A wins = K

Number of permutations where A wins K votes is given by:
(N!/K!(N-K!)) * ((C-1)^(N-K))

The first part gives permutations of K As vs Not A, the second part gives the permutations of candidates BCDEFG for the given K As

So possible votes for A are:
k………Permutations
14……..1 * 1 = 1
13…….14 * 6 = 84
12…….91 * 36 = 3276
11…….364 * 216 = 78624
10……1001 * 1296 = 1297296
9…….2002 * 7776 = 15567552
8…….3003 * 46656 = 140107968
etc
Total permutation of 8 or more = 157054801
There are the same permutations for candidates BCDEFG. These are mutually exclusive, a permutation with 8 or more votes for A cant also have 8 or more votes for another coandidate, so we can simply add hese up to give the total number of permutations that resukt in a majority winner:
157054801 * 7 = 1099383607
divide by the total number of voting permutations 6.78E11 gives:

0.00162

So pretty close to Richmars MC simulated 0.0017

That doesn’t answer the clarified question, but thanks – I was hoping somebody was going to do that as it helps with my solution, given I need to find the permutations for one of 5 candidates getting 5 or more votes from 6 voters or 3 or more votes from 8 voters.

1 – 1/e = 0.63

That doesn’t answer the clarified question,

Posted above.
0.6612 for a single winner with more votes than any one else.

Been doing halloween all day, but still working on this.

For d) permutations of one candidate in 5 getting 5 or more votes from 6 voters = (1 + 24) * 5 = 125
d) = (7! / (5! * 2!)) * (14! / (4! * 10!)) * (10! / (4! * 6!)) * (5^6 – 125) = 21 * 1001 * 210 * 15500 = 68423355000

fairly sure I have a method for e) and f), but they’re both a bit more complex.

Though whilst posting that I worked out a way to make the brute force method more efficient – easy to lose one layer of iteration, almost as easy to lose two. It might be possible to lose 14 layers of iteration, which would then no longer be brute force and probably a lot more efficient than my other method, though just losing 3 layers I should be able to brute force in ~15 minutes…

It’s amazing what some of us spend our Saturday nights doing 🙂 chapeau @aracer

It’s now become one of those stupid things I’m determined to finish off 👿

Yes, all good stuff aracer.
Some numbers for you to check!

Probability of one clear winner: 0.6616
Probability of 2 shared winners: 0.2156
Ditto 3 shared winners: 0.1062
Ditto 4 shared winners: 0.0155
Zero chance of 5 or 6 shared winners
Probability of 7 shared winners: 0.0010

Which all add up to 1.

To be precise, 0.00100421296069889995775111869959

How long would you need to run your monte carlo to get that level of precision? 😉

There’s a very simple formula for that one!

ok, I admit that one is easy for you!
What’s really cool is the macro runs ok (just a bit slower) on my £99 Windows 8 tablet.
It’s also fun watching the numbers tick over, and how uneven some events are (sometimes).

It’s all good – I’m glad somebody did the monte carlo.

So that was my f):

The number of permutations of one candidate getting 2 votes from 14 voters
= 14 * 13 / 2 * (number of permutations of 6 candidates votes from 12 voters).

But the number of permutations of one candidate getting 2 votes from 12 voters
= 12 * 11 / 2 * (number of permutations of 5 candidates votes from 10 voters).

…

So the number of permutations of each candidate getting 2 votes
= 14 * 13 * 12 … / 2^7 = 14! / 2^7

So the probability of each candidate getting 2 votes = 14! / (2^7 * 7^14)

So the probability of each candidate getting 2 votes = 14! / (2^7 * 7^14)

It’s one thing getting the answer, but always better to know why.

Anyway I decided to resort to (optimised) brute force for a bit to get some numbers I could check my calculations against. By brute force I mean checking all possible voting combinations, which means 14 nested loops with a check in the middle of all of them.

A trivial optimisation is to realise that you get the same result whoever the first voter votes for, so you can set that to a single value and multiply your result by 7. Which reduces you to 13 nested loops and decreases run time by 7.

There are two distinct possibilities for the first two voters: they both vote for the same candidate or they vote for different candidates. Out of the 49 possible voting combinations they vote the same 7 times and differently 42 times. Now we’re down to 12 nested loops but have to run twice, for a ~24 times speed improvement.

There are 3 distinct possibilities for the first 3 voters: they all vote for the same candidate, two of them vote for the same candidate or they all vote for different candidates. Out of the 343 possible voting combinations they all vote the same 7 times, two vote the same 126 times, they all vote differently 210 times. We’re down to 11 nested loops but have to run 3 times for a ~110 times speed improvement.

I could consider the options for the first 4 voters – there are 5 possible voting patterns, but it starts getting a bit hard working out the permutations and we’re already at a manageable run time with the previous optimisation.

The results:
1 winner (CBA copying vote breakdown): 448610617777
2 winners with 7 votes: 72072
2 winners with 6 votes: 44144100
2 winners with 5 votes: 3310807500
2 winners with 4 votes: 63126063000
2 winners with 3 votes: 79459380000
2 winners: 145940466672
3 winners with 4 votes: 1765764000
3 winners with 3 votes: 70630560000
3 winners: 72396324000
4 winners with 3 votes: 10594584000
4 winners: 10594584000
7 winners with 2 votes: 681080400
7 winners: 681080400

Divide by 7^14 for probability:
1 winner: 0.661450
2 winners: 0.215181
3 winners: 0.106744
4 winners: 0.015621
7 winners: 0.001004
so the sim results are pretty good, but only to about 3 DPs.

About 6 minutes runtime on my not incredibly powerful computer (probably not much more powerful than your tablet), rather better than 11 hours for the full strength brute force.

Now I’ve got to work out why my calc for d) is wrong – a, b, c and f match those results.

The results:
1 winner (CBA copying vote breakdown): 448610617777
2 winners with 7 votes: 72072
2 winners with 6 votes: 44144100
2 winners with 5 votes: 3310807500
2 winners with 4 votes: 63126063000
2 winners with 3 votes: 79459380000
2 winners: 145940466672
3 winners with 4 votes: 1765764000
3 winners with 3 votes: 70630560000
3 winners: 72396324000
4 winners with 3 votes: 10594584000
4 winners: 10594584000
7 winners with 2 votes: 681080400
7 winners: 681080400

+1

Just in case anybody is still following this, I’ve finally come up with a fully numeric non-iterative method which can be worked out with a piece of paper and a calculator (I’m sure you could dispense with the calculator, but I’m not quite that masochistic). It’s not pretty and involves quite a few terms, but I can explain it in a single post a bit shorter than War and Peace.

I’m still working with the method based on Stoner’s original idea I outlined in http://singletrackworld.com/forum/topic/probability-1/page/2#post-7275914 – I’ve already given solutions for cases a,b,c and f, but was having trouble with d and e.

As I expected, my optimisation of the brute force method provided the inspiration required. In a similar way to what I was doing with that, I can enumerate the possible voting patterns which would lead to no clear winner, with each term being votes for a candidate and candidates with no votes not mentioned (categorised as before):
a) 7,7
b) 6,6,2; 6,6,1,1
c) 5,5,4; 5,5,3,1; 5,5,2,2; 5,5,2,1,1; 5,5,1,1,1,1
d) 4,4,4,2; 4,4,4,1,1; 4,4,3,3; 4,4,3,2,1; 4,4,3,1,1,1; 4,4,2,2,2; 4,4,2,2,1,1; 4,4,2,1,1,1,1
e) 3,3,3,3,2; 3,3,3,3,1,1; 3,3,3,2,2,1; 3,3,3,2,1,1,1; 3,3,2,2,2,2; 3,3,2,2,2,1,1;
f) 2,2,2,2,2,2,2

(the observant might think I’ve missed some patterns – that’s because there are only 7 candidates and the missing patterns have more than 7 terms)

Now to evaluate the permutations for those voting patterns.
permutations = (combinations of candidates) * (combinations of voters) / (factor to compensate for the other terms both having order which are interdependent)
= (c! / z!) * (v! / (t1! * t2! * t3! * t4! * t5! * t6! * t7!)) / (d1!*d2!)
where:
c = number of candidates
z = number of candidates with zero votes
v = number of voters
t1…t7 = terms in enumeration (if less than 7 terms, implied tx = 0, tx! = 1)
d1,d2 = number of candidates drawing (there may only be one draw)

So lets start from the bottom (I have my reasons!)
f)
2,2,2,2,2,2,2 permutations = (7!/0!) * (14!/(2!*2!*2!*2!*2!*2!*2!)) / 7!
which happily evaluates to = 14! / 2^7 which is the same formula I had a few posts ago

…now we move into the unknown
e)
3,3,3,3,2; p = (7!/2!) * (14!/(3!*3!*3!*3!*2!)) / 4! = 3531528000
3,3,3,3,1,1; p = (7!/1!) * (14!/(3!*3!*3!*3!*1!*1!)) / (4!*2!) = 7063056000
3,3,3,2,2,1; p = (7!/1!) * (14!/(3!*3!*3!*2!*2!*1!)) / (3!*2!) = 42378336000
3,3,3,2,1,1,1; p = (7!/0!) * (14!/(3!*3!*3!*2!*1!*1!*1!)) / (3!*3!) = 28252224000
3,3,2,2,2,2; p = (7!/1!) * (14!/(3!*3!*2!*2!*2!*2!)) / (2!*4!) = 15891876000
3,3,2,2,2,1,1; p = (7!/0!) * (14!/(3!*3!*2!*2!*2!*1!*1!)) / (2!*3!*2!) = 63567504000
total for e) = 3531528000 + 7063056000 + 42378336000 + 28252224000 + 15891876000 + 63567504000 = 160684524000

d)
4,4,4,2; p = (7!/3!) * (14!/(4!*4!*4!*2!)) / 3! = 441441000
4,4,4,1,1; p = (7!/2!) * (14!/(4!*4!*4!*1!*1!)) / (3!*2!) = 1324323000
4,4,3,3; p = (7!/3!) * (14!/(4!*4!*3!*3!)) / (2!*2!) = 882882000
4,4,3,2,1; p = (7!/2!) * (14!/(4!*4!*3!*2!*1!)) / 2! = 15891876000
4,4,3,1,1,1; p = (7!/1!) * (14!/(4!*4!*3!*1!*1!*1!)) / (2!*3!) = 10594584000
4,4,2,2,2; p = (7!/2!) * (14!/(4!*4!*2!*2!*2!)) / (2!*3!) = 3972969000
4,4,2,2,1,1; p = (7!/1!) * (14!/(4!*4!*2!*2!*1!*1!)) / (2!*2!*2!) = 23837814000
4,4,2,1,1,1,1; p = (7!/0!) * (14!/(4!*4!*2!*1!*1!*1!*1!)) / (2!*4!) = 7945938000
total for d) = 441441000 + 1324323000 + 882882000 + 15891876000 + 10594584000 + 3972969000 + 23837814000 + 7945938000 = 64891827000

c) nah, already done that, CBA doing it again

So in summary
a) p = 72072
b) p = 44144100
c) p = 3310807500
d) p = 64891827000
e) p = 160684524000
f) p = 681080400
total for no clear winner = 72072 + 44144100 + 3310807500 + 64891827000 + 160684524000 + 681080400 = 229612455072

So probability of no clear winner = 229612455072 / 7^14 = 0.338550
probability of clear winner = 1 – 0.338550 = 0.661450

phew – congratulations if you made it to here – I think that’s me done! I still have a horrible feeling there’s a much easier way, but I won’t be trying to find it.