How do I estimate P(skill(player1)>skill(player2)) when I know the number of (presumably independent) 'wins' and 'losses' of player1 and player2? 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.
 A: 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)


*

*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". *

*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.

*Integrate numerically over the Joint PDF in points where x>y (x=y counts half each way).

*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.
A: 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$).
