1

How do I estimate the probability P(skill(player1)>skill(player2)) when all of the following apply:

  • I know the number of wins and losses of player1 and player2.
  • I can assume that the wins and losses are all against randomly drawn opponents from the same population for each of player1 and player2.
  • Equality is out of the question.
  • The skill measure is a relative position in the list of all players. The skill measure is now to be treated as a random variable with some distribution that depends on the wins and losses of the player measured.
?

I need this for improving a compare-sort algorithm where I am constantly trying to choose the comparison that, through transitive closure, gives the outcome where fewest further comparison actions are needed. Since a comparison can lead to two results, I will weight the possible outcomes by their estimated probability, in order to make better choices of comparisons. I do not care too much about computational efficiency, as there will be relatively small datasets involved.

Elias Hasle
  • 123
  • 6
  • What you really have are _four_ random variables? Because, normally one thinks of $a$ and $b$ as _constants_, and there is no _probability_ associated with $a > b$. – Dilip Sarwate Sep 23 '14 at 19:15
  • It's possible I've misunderstood something, but it seems like the information in your first paragraph (all randomly drawn from the same population) should yield trivial answers (at least, assuming continuity; and almost-as-trivial answers otherwise, leaving only probabilities of equality as an issue). Are there additional variables/information that forms the basis from which one might infer more than P(Y>Z|Y>X,Z>X)=1/2 (at least in the continuous case)? – Glen_b Sep 24 '14 at 00:39
  • I voted to close this question for the following reasons. After many changes, it remains unclear what "Z" might be and how it is intended to be related to "X" and "Y"; unclear what precisely is meant by "distribution" and "estimate," since they seem to be used interchangeably; and unclear what the unexplained notation "Est" might mean. It does not seem possible to make reasonable guesses about these because the context is too vague: in particular, information is lacking about the data used to make these "estimates" and how they were computed. Edits to address these gaps would be appreciated. – whuber Sep 30 '14 at 16:31
  • 1
    I understand. Z is out now, which has been my intention for a while. I used "estimate" and "distribution" rather interchangeably, because I did not understand their relation properly. Est meant "estimate of". You are right that the information used to make the estimates was lacking. I have now rewritten the entire question in light of our feedback. – Elias Hasle Oct 01 '14 at 08:43

2 Answers2

1

I will answer my own question:

I solved it, with help from here: What is the intuition behind beta distribution? (Davi Robinson's answer) and here: Is that meaningful to compare two random variables? (Michael Chernick's answer)

  1. Generate beta distributions for each player by inputting wins+1 as alpha and losses+1 as beta. +1 adds a prior saying "I know that win and loss are both possible outcomes". *
  2. Join the Probability Density Functions like this: F(x,y)=f(x)*g(y), where f(x) is the beta PDF of skill(player1) (or relative position in the sorted list of all players), and likewise for g(y) and player2.
  3. Integrate numerically over the Joint PDF in points where x>y (x=y counts half each way).
  4. Ta-da! There's an estimated probability.

It works well, but my tests seem to show that it works better to just choose the comparison that has the best outcome as a possibility, regardless of my estimated probability for that outcome. EDIT: This may well be because my estimator is bad.

*In my particular problem the opponents are not really drawn at random. (I have specifically avoided any comparisons that can mess with the transitivity of the relation.) To perhaps acommodate for this, and more important, to narrow down the beta distributions, I used all applicable comparisons from the transitive closure instead. EDIT: ...which gives bad results in situations such as the one where an uncompared player plays one who has players above and below, and the new player will get a very low or very high estimated rating, though a less extreme one would be reasonable.

Community
  • 1
Elias Hasle
  • 123
  • 6
  • The beta distribution is nice when you (I) have stats on successes and failures. What if all you have is an estimate of skill, that is to be interpreted as the expected value of an unknown distribution? What distribution would be appropriate in that case? Would it be reasonable to, say, average over all distributions on (0,1) that have that expectation? – Elias Hasle Oct 01 '14 at 10:14
  • see http://stats.stackexchange.com/questions/117451/what-probability-distribution-to-use-for-a-variable-x-for-which-only-an-estimate – Elias Hasle Oct 01 '14 at 10:29
0

Suppose Y=0 with probability $p$ and Y=1 with probability $(1-p)$. Since the distribution of X is known and $P(Y>X)$ is known, you can solve for $p$. Similarly, suppose Z=0 with probability $q$ and Z=1 with probability $(1-q)$. You can also solve for $q$. With $p$ and $q$ in hand, you can easily work out $P(Y>Z) = (1-p)q$. This approach satisfies property 1 in the question, but not property 2 (consider the case $P(Y>X)=1$ and $P(Z>X)=1$).

Tom Minka
  • 6,610
  • 1
  • 22
  • 33