Probability question, cross post

[CallMeIshmael]

I posted this in SMP.. after having written it out, I realize it probably belongs here, so Ill post here. Ill leave it over there since it seems the two forums to inter mingle too much.

OK, imagine you are playing a game against one person

You are both going to be dealt a number. Your number is is going to be in the range [50,100], and will be any real number, from an identically distributed continous variable.

The opponent will be dealt a number. There is a 30% chance that his number will be taken from [0,50] and a 70% chance from [50, 100]. (again, assume random continous, with a constantly increasing integral over the two ranges).

What are the chances that my number is going to be higher?

This seems easy, 30% + (1/2)70% = 65%.


Now, suppose I am playing against two players. The first has the same distribution as my opponent above, and the second is 60% chance to be taken from [50,100] and 40% from [0,50].

What are the chances that I am dealt a higher number than both?

One way to do it, is: (0.3)*(0.4) + 1/2(0.3)*(0.6) + 1/2(0.7)*(0.4) + 1/3(0.7)*(0.6)

(the first term represents the times when both of their numbers are in the [0,50] range, the second and third are when exactly one opponent has a chance to beat you, and the fourth occurs when both are in the [50,100] range)

But, as you add more players (say, third, fourth and fifth), the above method a breaking it down into discreet categories becomes rather long.

Im wondering if there is a better way to do this.


Specifically, we should be able to break this down into a formula such as:


P(highest number) = prob(beating p1)*prob(beating p2|beaten p1)*prob(beating p3|beaten p1,p2)...


Can anyone come up with a formula for prob(pN|beaten p1..N-1)??

thanks

[pzhon]

[ QUOTE ]
as you add more players (say, third, fourth and fifth), the above method a breaking it down into discreet categories becomes rather long.

[/ QUOTE ]
Not really.

Let p_i be the probability player i is a contender (in [50,100]).

Product ((1-p_i)+p_i x)

is a generating polynomial for the number of contenders you face. The coefficient of x^n is the probability there are exactly n contenders.

The probability you win when there are n contenders is 1/(n+1). Conveniently, the probability you win is the integral of the above polynomial from 0 to 1. I don't know of a simpler method.

This isn't just a trick. The product evaluated at x=X is the conditional probability that you win when your number is X of the way from 50 to 100. The incremental conditional probabilities are a mess to work out uwithout this conditional probability.

[AaronBrown]

pzhon is correct but if everyone has the same chance of having a number from 50 to 100, and all the events are independent, it's not too bad. If there are k other players, each with chance p of being in 50 to 100, your chance of winning is the sum from i = 0 to k of:

C(k,i)*p^i*(1-p)^(k-i)/(i+1)

Which is 1/[p*(k+1)] times the sum from i = 0 to k of:

= C(k+1,i+1)*p^(i+1)*(1-p)*(k-i)

The sum is the sum from j = 1 to k+1 of:

C(k+1,j)*p^j*(1-p)^(k+1-j)
= 1- (1-p)^(k+1)

So the answer is:

[1 - (1-p)^(k+1)]/[p*(k+1)]

If the p's are not equal, but there are a lot of them without too much variation, you might get a decent approximation by putting an average p into the formula above; or take the average using the maximum and minimum p's.