#1
|
|||
|
|||
Probability question, cross post
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 |
#2
|
|||
|
|||
Re: Probability question, cross post
[ 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. |
#3
|
|||
|
|||
Re: Probability question, cross post
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. |
|
|