# Thread: probability and permutations

1. ## probability and permutations

Hi guys,
I'm not a math student, in fact math is not a strong subject for me at all, quite the opposite. I'm a graduate computing science student and I could use some help with a problem I'm having. It's gonna be hard to explain given I'm not very mathematical so please bare with me. Ok so here's my problem.

I have a program that asks a user a number of questions. For each question there are 3 possible answers, answers 1, 2, and 3. These answers have a value associated with them, a score if you will. Answer 1 has a value of 16, answer 2 has a value of 8, and answer 3 a value of 4. The layout would be something like this

Question1: is this patent likely to be unique
answer1: yes (value of 16)
answer2: maybe (value of 8)
answer3: no (value of 4)

A user can only pick one answer per question, and remember there are 3 questions. So lets say the user picked answer 1 for all three questions, their score would be 48 (16x3).

So what I need to do here is, calculate a result based on their score after they've answered the questions. So out of a possible highest score of 48, what percentage did the user get. If the user chose answer 1 for all three questions, the result is 100% obviously. If they chose answer1 for two of the questions, and answer3 for one of the questions, then the user scored 16 + 16 + 4 which is 36 out of a possible 48, 75%.....duh! I know this might seem pointless so far, stick with me as I need to explain this in order for my problem to make sense. So the result can mean different things depending on the percentage. There are 3 possible types of result, an SR1, SR2, and SR3. Don't worry what these mean, they make sense to the users. So if the user scored 75% or over the result is an SR1, if they scored 42% or over the result is an SR2, anything below that is an SR3. So it's like this

SR1 >= 75%
SR2 >= 42% and < 75%
SR3 < 42%

So if you're still with me, thanks. Here's where it gets a bit tricky for me. At the moment the program is asking the user 3 questions, but that number may increase and I need to allow for that in my score calculation algorithm. At the moment, with 3 questions the likelihood of an SR1 result, given all possible permutations of user selected answers, is roughly .33. The other probabilities are roughly,
SR2 = .44
SR3 = .22

What I'd like to know is, how scalable is this with the current setup. I've noticed by scaling up from 3 questions to 8 questions the probabilities do change, as you'd expect I suppose. Is there anything I can do with my algorithm, any sort of formula to say, if the number of questions increases adjust the bands which SR1,2 or 3 can fall into accordingly so that the probabilities of any one of them occurring don't increase or decrease disproportionately with the number of questions being increased. Really not sure if any of that made sense. Any input at all is greatly appreciated.

ps...my apologies if I've posted this under the wrong heading

2. ## Re: probability and permutations

There's two ways of tackling this that i know of:

Use the multinomial distribution
The problem you are describing can be described in terms of a standard distribution called the multinomial distribution, which you can look up. If your not comfortable with math you may find the notation difficult to follow though.

Use a generating function
this is easyish to do but hard to understand.

The number of permutations scoring $i$ in a test with $N$ questions is the coefficient of $x^i$ in the expanded version of: $(x^4 + x^8 + x^{16})^N$

You can then ratio these to get probabilities and hence work out the chance of falling in any particular range.

Worked Example
Lets take the case of N=3 as an example, our expansion is:

$(x^4 + x^8 +x^{16})(x^4 + x^8 +x^{16})(x^4 + x^8 +x^{16})={x^{12}+3 x^{16}+3 x^{20}+4 x^{24}+6 x^{28}+3 x^{32}+3 x^{36}+3 x^{40}+x^{48}}$
eg, the number of permuations resulting a score of 16 is the coefficient of $x^{16}$ which in the above expansion has been calculated as 3.

The total number of permutations will be the sum of the coefficients: 1+3+3+4+6+3+3+3+1=27

So, the probability of scoring 16 would be 3/27

In this case:
P(Score 12)=1/27
P(Score 16)=3/27
P(Score 20)=3/27
P(Score 24)=4/27
P(Score 28)=6/27
...etc

Now to find the score that 33% fall short of. (33% is the threshold probability you posted for SR1). Just add up probabilities of the lowest score until you get past 33%. The cumulative probabilities are:
P(Score 12 or less) = 1/27
P(Score 16 or less) = 1/27 + 3/27 = 14.8%
P(Score 20 or less) = 1/27 + 3/27 + 3/27 = 25.9%
P(Score 24 or less) = 1/27 + 3/27 + 3/27 +4/27 = 40.7%
P(Score 28 or less) = 1/27 + 3/27 + 3/27 +4/27 + 6/27 = 63%
...

So, your SR1 limit would be a score of either 20 or 24 (depending on whether you want the probability to be too low or too high).

Also, since your post sounds like a real world situation involving test results...you should not rely on anything i say without verifying it first.

3. ## Re: probability and permutations

Thanks Springfan25, really appreciate you taking the time to look at this for me. The test results are not critical by any means, but yes I'd like to have the algorithm be as reliable as possible.

T