Multiparticipant events and pairwise probabilities

[cosmicminer]

TL;DR Summary

multiparticipant event probabilities from the head to head probabilities

Is there a formula for this ?
Consider the following simple looking problem.
We have three contestants A, B and C, there is a competition between them and the best wins.
For example a race, discus throw, javelin throw ...
We know that A beats B with a probability 0.6, A beats C with a probability 0.8 and B beats C with a probability 0.7.
That is we know the head to head probabilities but what about the probabilities when they are all together competing ?

My approach was this:
Suppose C is left out and A fights against B and then the winner fights against C.
Or B is initially left out, or A is initially left out.
There may be psychological factors which make this different from the real event but we neglect them. We assume independence.

So if C is initially left out then A goes forward with prob. 0.6, then it's 0.8 against C, equals 0.48. For B it is 0.4 then 0.7, equals 0.28. For C it is the remainder, 0.24.
If B is left out then similarly A has probability 0.48, C has 0.06 and B has 0.46.
If A is left out then B has 0.28, C has 0.06 and A has 66%

The three possibilities are equivalent so for the real situation we take the averages and finally:

P(A) = 0.54, P(B) = 0.34 and P(C) = 0.12

Now the real problem is when there are N participants and we know the head to head probabilities (Pij).
It becomes tedious, how to write a computer code ?
Is there a general formula ?

 

[FactChecker]

For example a race, discus throw, javelin throw ...
We know that A beats B with a probability 0.6, A beats C with a probability 0.8 and B beats C with a probability 0.7.
That is we know the head to head probabilities but what about the probabilities when they are all together competing ?

My approach was this:
Suppose C is left out and A fights against B and then the winner fights against C.

Does "the winner fights C" imply a new race, independent of the A vs B race? Most of your examples: "a race, discus throw, javelin throw" would not be like that.

Or B is initially left out, or A is initially left out.
There may be psychological factors which make this different from the real event but we neglect them. We assume independence.

Ok, but independence can only be assumed if the winner vs C race is a new race.

So if C is initially left out then A goes forward with prob. 0.6, then it's 0.8 against C, equals 0.48. For B it is 0.4 then 0.7, equals 0.28. For C it is the remainder, 0.24.

That sounds right, given the independence assumption. The probabilities simply multiply.

If B is left out then similarly A has probability 0.48, C has 0.06 and B has 0.46.
If A is left out then B has 0.28, C has 0.06 and A has 66%

The three possibilities are equivalent so for the real situation we take the averages and finally:

P(A) = 0.54, P(B) = 0.34 and P(C) = 0.12

Now the real problem is when there are N participants and we know the head to head probabilities (Pij).
It becomes tedious, how to write a computer code ?

That is a completely different question and it depends on what computer language you are talking about.

Is there a general formula ?

Good question. Thinking about this.

 

[cosmicminer]

Does "the winner fights C" imply a new race, independent of the A vs B race? Most of your examples: "a race, discus throw, javelin throw" would not be like that.

Ok, but independence can only be assumed if the winner vs C race is a new race.

That sounds right, given the independence assumption. The probabilities simply multiply.

That is a completely different question and it depends on what computer language you are talking about.

Good question. Thinking about this.

Look, suppose it's a race.
The winning attribute is speed and it may follow a normal distribution if we go into the details.
So if we ignore psychological factors it's going to be the same with or without C present. So the rest follow.

Look at this

https://www.untruth.org/~josh/math/normal-min.pdf

Although it does n't follow my logic of splitting things pairwise it's the same problem really.
Now this fellow Hill in the link uses the normal distribution -as is more logical- but to simplify things
I 'm going to use the Laplace distribution with which pair probabilities can be expressed analytically.
Then I 'm going to verify the A-B-C approach above using Monte Carlo.
One can use Monte Carlo for the bigger problem or even the Hill integral with Simpson's rule but I wonder if there is something simpler.

 

[FactChecker]

Look, suppose it's a race.
The winning attribute is speed and it may follow a normal distribution if we go into the details.
So if we ignore psychological factors it's going to be the same with or without C present. So the rest follow.

My point is that if these are comparisons of A, B, C in one race, then the fact that A was faster than B tends to imply that A might have run faster than his average. That changes the odds that A also beat C. So the probabilities would be dependent. I do not think that is what you had in mind. I think your scenario is that there are two independent races, A vs B and then another race between the winner and C.

Look at this

https://www.untruth.org/~josh/math/normal-min.pdf

Although it does n't follow my logic of splitting things pairwise it's the same problem really.

This is not the same. The link given is about "We have a race of n runners". That is one race with n runners, not a series of independent races between the winner of a prior race and a new contestant. The probabilities are different.

 

[Dale]

The winning attribute is speed and it may follow a normal distribution if we go into the details.

This is called a latent trait.

I know that there are other contexts in which latent traits arise, but I have seen them in the context of item response theory and in the context of league competitions like the Elo scores in chess or the TrueSkill rating for online games

 

[cosmicminer]

No.
Forget how these head to head probabilities are derived (elo, speed distributions, whatever).
We assume they are independent.
Perhaps not in real life, but for our purposes they are.
If you talk about races, in real life the jockey sees the rest of the field stretches and miles behind him (sometimes) and because there is no danger he slows down to a trot, or other things happen. But this does not concern us. We assume the jockey tries to get the best out of his horse.
So Hill's formula is ok whichever way you look at it.
With three horses I could say "let A and B race together today and the winner against C the day after tomorrow". I don't see anything bad happening to J. Hill's formula, the shortest time wins anyways.
Except of course I have to do this three ways, so I can only do it in imagination but it does n't change things mathematically.

I assume that the head to head probabilities have somehow been established.
So this is really an effort of mine to simplify the formulas (if possible) and the question is, is there a neat addition formula to go from pair to pair probabilities to total probabilities, for any number of competitors ?

 

[cosmicminer]

The way the simple problem is stated in the first post it's not readily amenable to simulation using Monte Carlo.
But I can do it using the integral in the link of post no 3.

Suppose it concerns three race horses running a race of 5 furlongs.
We know from past measurements their mean times from start to finish and the stds:

Horse 1, μ = 57 sec, σ = 0.5 sec
Horse 2, μ = 57.3 sec, σ = 0.6 sec
Ηorse 3, μ = 57.7 sec, σ = 1 sec

I can do the integral to compute pair probabilities.
For the sake of simplicity I assume Laplace distribution.
Logically the times are distributed normally about the mean, but Laplace makes it easier to do the integration:

For means μ(i), μ(j) and stds σ(i), σ(j) the formula for the probability of i beating j is then:

a) If σ(i) = σ(j) = σ

Q(i,j) = 1 - Exp((-z / σ) * (2 + (z / σ)) / 4

b) if σ(i) <> σ(j%)

Q(i,j) = 1 - 0.5 * (Exp(-z / σ(i)) / σ(j) ^ 2 - Exp(-z / σ(j)) / σ(i) ^ 2) / (1 / σ(j) ^ 2 - 1 / σ(i) ^ 2)

where z = μ(j) - μ(i)

Using this formula I compute:

Q(1,2) = 0.6311446
Q(2,3) = 0.6207114
Q(1,3) = 0.7100428

(and Q(2,1) = 1 - Q(1,2), Q(3,2) = 1 - Q(2,3), Q(3,1) = 1 - Q(1,3))

Using the logic of post no 2:

P(1) = ( 2 . Q(1,2) . Q(1,3) + Q(2,3) . Q(1,2) + Q(3,2) . Q(1,3) ) / 3 = 0.5191164
P(2) = ( 2 . Q(2,1) . Q(2,3) + Q(1,3) . Q(2,1) + Q(3,1) . Q(2,3) ) / 3 = 0.2999295
P(3) = ( 2 . Q(3,1) . Q(3,2) + Q(1,2) . Q(3,1) + Q(2,1) . Q(3,2) ) / 3 = 0.1809541

(those add to 1).Now I can verify using the Monte Carlo method.

If x stands for the machine generated random number (in (0,1)) the Laplace distributed variables are:

t(i) = μ(i) + σ(i) * f(x)

where:

f(x) = -ln(2.(1 - x)) for x >= 1/2 , ln(2.x) for x < 1/2

and the shortest t value of the three wins the trial.

I do 1000000 trials and find:

P(1) = 0.49
P(2) = 0.29
P(3) = 0.22

So, there appears to be a discrepancy !
A small one but it is a discrepancy.
The original simple (looking) problem was not solved correctly by me.
I checked the Q values with Monte Carlo (0.63, 0.62, 0.71) in case something was wrong with my formula for the Q(i%,j%) and those were correct.
Why this discrepancy ???

Let me restate what I am looking for:
I 'm looking for a fast track formula for the Hill integral (post no 3).
For a once through computation doing it by Monte Carlo is fast enough, by numerical integration also. But for other uses, such as research, we need repeated computation and these methods are not fast enough.

 

[Dale]

No.
Forget how these head to head probabilities are derived (elo, speed distributions, whatever).
…
So Hill's formula is ok whichever way you look at it.

What do you mean “No”. Hill’s formula is explicitly derived from a normally distributed latent trait.

 

[cosmicminer]

What do you mean “No”. Hill’s formula is explicitly derived from a normally distributed latent trait.

From some distribution he says.
Normal is the logical thing to assume, could also be flat topped.
What is a latent trait ?

But it baffles me now.
Forget the horses I mention before and say we throw javelins.
Me and my friends Tom and Dick.
We have all been training for the past year and our trainers know our means and standard deviations.
When we throw a javelin we always try for the record, from first to last attempt and each of us does n't care what the others do.
So if we take turns or if it's a two way competition today and the winner with the third guy tomorrow what's the difference ?
It's baffling is n't it ?

 

[Dale]

I 'm looking for a fast track formula for the Hill integral (post no 3).

There may not be a fast way to compute Hill’s integral. However, it seems like you are not firmly tied to using a normally distributed latent trait. In which case Hill’s integral is unnecessary.

Have you considered using Baye’s formula?

 

[cosmicminer]

There may not be a fast way to compute Hill’s integral. However, it seems like you are not firmly tied to using a normally distributed latent trait. In which case Hill’s integral is unnecessary.

Have you considered using Baye’s formula?

Hmm.
I used Laplace for the only reason that it computes the integral analytically for two contestants (and maybe for more but it gets difficult).
This I did together with Monte Carlo two posts above to verify my Bayesian (or quasi-Bayesian) approach.
Strangely it does n't verify.
Have I made numerical mistakes ? I doubt it.

 

[cosmicminer]

For the original problem I said (AB)C, (BC)A, (AC)B are equivalent arrangements.
This gives probabilities that add to 1, but it's a false indicator. Therein must lie the error.
So is there no way to solve the simple problem if we know the head to head probabilities but we know nothing about the Physics of the situation (the normal distributions and the rest) ?

 

[cosmicminer]

I think I found what went wrong.
With the Q values (pair to pair) we find an approximation.
The Monte Carlo method / integral are more precise.
What goes on ?
Consider the following thought experiment:
The race between 1, 2 and 3 takes place and is recorded on video.
A tv assistant photoshops the 3 out of the race and leaves the 1 and the 2. He is using super perfect techniques and it's like real. He gives the photoshopped video to us in an adjoining room and we watch a race between the 1 and the 2.
The 1 wins and the assistant says "ok, you saw that, the 1 has beaten the 2, now I 'm going to bring you another photoshopped version with the 2 missing and you will see the 1 racing against the 2".
In the thought experiment this can go on for an infinity and with all possible alterations of order.
So the probability of 1 against 2 comes out as Q(1,2) but sometimes the 1 wins by a narrow margin, some
other times the 1 demolishes the 2 and wins by a mile. So in the second phase, between the 1 and the 3, the situation is not always the same. Sometimes the chances of the no 1 are less than the typical Q(1,3), sometimes they are bigger.
Hence the difference in the end result.

Now if we actually agree to use the Q formulas as an approximate solution and if there are N (>3) runners what we have to do is make imaginary pairs and proceed by elimination. This looks easy for N up to 15 I imagine but I don't know how fast compared to other methods. For N > 25-30 it will take millions of ages and can't be done.

 

[Dale]

I know you explicitly rejected it earlier, but this is exactly what the Elo or TrueSkill ratings are for. You are describing a latent trait. Also, those approaches are designed to handle thousands of competitors easily.

 

[cosmicminer]

I know you explicitly rejected it earlier, but this is exactly what the Elo or TrueSkill ratings are for. You are describing a latent trait. Also, those approaches are designed to handle thousands of competitors easily.

I did not reject anything.
I know the ELO ratings.
I just said that -somehow- we know the head to head probabilities.

The ELO ratings apply to football.
From those we derive probabilities (not great stuff in terms of achieving the most accurate of predictions but acceptable).
The anomaly encountered before can also be explained using three football teams as our guinea pigs.
It's A, B and C and by the nature of things two of them have to be set against one another while the lucky third goes straight to the final.
So we can compute Q values and P values in the simple way I described early on.
Suppose our semifinal is A v B and A's chance to eliminate B is 60% - from ratings.
But B wins and do so rather decisively, 5 goals to nil.
What happen's ? B's rating is given a boost and their chances against C are no longer 70% but something like 75%.
With the draw (A v B, C waits) and with the initial ratings B's chances for the trophy seem to be 28% (because B v C is a nominal 70%) but given their win against A they could be anything from say 26% to 30%.
Hence the discrepancy and in the case of Hill's integral with the runners this is taken account of.

Now if I say this error is to be tolerated, I believe one can proceed ergodically with pair selections, but
as the number of contestants increases it looks to me now that it's going to be a very slow indeed algorithm.

 

[Dale]

Now if I say this error is to be tolerated,

Well, you could look at it as an error, or you could look at it as an uncertain win probability. In other words, in one case there is a true value and you have deviated from it, and in the other case there is no true value but rather the value itself is a random variable with some statistical distribution.

as the number of contestants increases it looks to me now that it's going to be a very slow indeed algorithm.

As the number of contestants increases the number of pairwise ratings scales by $N^2$. I don't think the algorithms scale non-linearly, but the number of comparisons do.

 

[cosmicminer]

As the number of contestants increases the number of pairwise ratings scales by $N^2$. I don't think the algorithms scale non-linearly, but the number of comparisons do.

Now I rememeber I did something like that in 2008.
The European nations football cup tournament in Austria-Switzerland.
With 16 teams and pair to pair eliminations I got something. It only needed tenths of seconds to compute.
So powerful Spain was indeed the favourite and possible closeups were Germany, Croatia if I remember right.
Next came the world cup series of 2010 in South Africa. Now 32 teams and no joy. It would still be running.