Re: [math-fun] optimal advance tournament scheduling
At 6/23/19, 5:25 PM, "Keith F. Lynch" <kfl@KeithLynch.net> wrote,
If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits.
It seems to me prior probabilities are necessary to talk about information. An idea like that matchups *tend* to be *somewhat* consistent and transitive is the beginning of a prior. If I think that the total probability of one or more violation of transitivity or consistency is one in a binary million (2**20), then that probability gets divided between all the violating outcomes, so there would be more than 20 bits of information in any one of them. On the other hand, the more unlevel the playing field, so to speak, the less *expected* surprise. From my impression of statistics, what you do is start with a general model of how things work, which has hidden parameters, and then given an actual outcome, try to derive the hidden parameters most likely to give that outcome. (I actually don't understand why the peak of the curve is given such importance.) So if each team has a "skill level", and the odds of A wins/B wins/tie are just a function of the two skills, then once the tournament is over you can back-figure the most likely vector of 8 skills, and from that pick the most skillful team! Easy peasy. But, even having no prejudices about the teams to start with (not to mention ideas about how they interact), the amount of information the outcome represents depends on both the model (of behind-the-scenes Truth, not the tournament plan) and the actual outcome. Or, you can calculate the expected number of bits and turn off the TV satisfied. I understand the Google pagerank algorithm is equivalent to applying one (linear?) model to this problem. Of course, the information everyone wants to know is, who's the best team? Which for 8 teams is 3 bits without any prejudices. Then the question is, what are the odds a given method of matching teams gives the right answer (given some model of "best teams")? Because the less likely you're right, the fewer bits you actually delivered. On the other hand, if the best you can deliver is three bits, there are diminishing... returns to even... talking about... this. --Steve
Perhaps this is interesting: if we have three players who have played three games and created a cycle (A beat B, B beat C, C beat A), a three-way tie in strength is NOT the maximum-likelihood solution; this cycle is most probable when, for some ordering, the stronger player wins with probability 2/3. Of course the likelihood is the same for any ordering; but the point is that if we arbitrarily choose, say, A>B>C, we have a 'better' estimate than declaring a 3-way tie. Maybe this is an example of maximum-likelihood going wrong? This assumes that probabilities are constrained to be consistent with some total ordering; the stronger player has at least 1/2 probability of winning, and if three players are ranked X>Y>Z then Prob(X beats Z) is at least as large as max(X-beats-Y , Y-beats-Z). On Wed, Jun 26, 2019 at 12:44 PM Steve Witham <sw@tiac.net> wrote:
At 6/23/19, 5:25 PM, "Keith F. Lynch" <kfl@KeithLynch.net> wrote,
If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits.
It seems to me prior probabilities are necessary to talk about information.
An idea like that matchups *tend* to be *somewhat* consistent and transitive is the beginning of a prior. If I think that the total probability of one or more violation of transitivity or consistency is one in a binary million (2**20), then that probability gets divided between all the violating outcomes, so there would be more than 20 bits of information in any one of them.
On the other hand, the more unlevel the playing field, so to speak, the less *expected* surprise.
From my impression of statistics, what you do is start with a general model of how things work, which has hidden parameters, and then given an actual outcome, try to derive the hidden parameters most likely to give that outcome. (I actually don't understand why the peak of the curve is given such importance.)
So if each team has a "skill level", and the odds of A wins/B wins/tie are just a function of the two skills, then once the tournament is over you can back-figure the most likely vector of 8 skills, and from that pick the most skillful team! Easy peasy.
But, even having no prejudices about the teams to start with (not to mention ideas about how they interact), the amount of information the outcome represents depends on both the model (of behind-the-scenes Truth, not the tournament plan) and the actual outcome. Or, you can calculate the expected number of bits and turn off the TV satisfied.
I understand the Google pagerank algorithm is equivalent to applying one (linear?) model to this problem.
Of course, the information everyone wants to know is, who's the best team? Which for 8 teams is 3 bits without any prejudices. Then the question is, what are the odds a given method of matching teams gives the right answer (given some model of "best teams")? Because the less likely you're right, the fewer bits you actually delivered. On the other hand, if the best you can deliver is three bits, there are diminishing...
returns to even...
talking about...
this.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
How transitive is strength in chess? On Thu, Jun 27, 2019 at 2:38 PM Michael Collins <mjcollins10@gmail.com> wrote:
Perhaps this is interesting: if we have three players who have played three games and created a cycle (A beat B, B beat C, C beat A), a three-way tie in strength is NOT the maximum-likelihood solution; this cycle is most probable when, for some ordering, the stronger player wins with probability 2/3.
Of course the likelihood is the same for any ordering; but the point is that if we arbitrarily choose, say, A>B>C, we have a 'better' estimate than declaring a 3-way tie. Maybe this is an example of maximum-likelihood going wrong?
This assumes that probabilities are constrained to be consistent with some total ordering; the stronger player has at least 1/2 probability of winning, and if three players are ranked X>Y>Z then Prob(X beats Z) is at least as large as max(X-beats-Y , Y-beats-Z).
On Wed, Jun 26, 2019 at 12:44 PM Steve Witham <sw@tiac.net> wrote:
At 6/23/19, 5:25 PM, "Keith F. Lynch" <kfl@KeithLynch.net> wrote,
If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits.
It seems to me prior probabilities are necessary to talk about information.
An idea like that matchups *tend* to be *somewhat* consistent and transitive is the beginning of a prior. If I think that the total probability of one or more violation of transitivity or consistency is one in a binary million (2**20), then that probability gets divided between all the violating outcomes, so there would be more than 20 bits of information in any one of them.
On the other hand, the more unlevel the playing field, so to speak, the less *expected* surprise.
From my impression of statistics, what you do is start with a general model of how things work, which has hidden parameters, and then given an actual outcome, try to derive the hidden parameters most likely to give that outcome. (I actually don't understand why the peak of the curve is given such importance.)
So if each team has a "skill level", and the odds of A wins/B wins/tie are just a function of the two skills, then once the tournament is over you can back-figure the most likely vector of 8 skills, and from that pick the most skillful team! Easy peasy.
But, even having no prejudices about the teams to start with (not to mention ideas about how they interact), the amount of information the outcome represents depends on both the model (of behind-the-scenes Truth, not the tournament plan) and the actual outcome. Or, you can calculate the expected number of bits and turn off the TV satisfied.
I understand the Google pagerank algorithm is equivalent to applying one (linear?) model to this problem.
Of course, the information everyone wants to know is, who's the best team? Which for 8 teams is 3 bits without any prejudices. Then the question is, what are the odds a given method of matching teams gives the right answer (given some model of "best teams")? Because the less likely you're right, the fewer bits you actually delivered. On the other hand, if the best you can deliver is three bits, there are diminishing...
returns to even...
talking about...
this.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Somewhere in Gerald Abrahams' "The Chess Mind" I recall reading about a trio of historically prominent (American?) chess masters constituting such a paradoxical cycle, though I am unable to locate the exact reference. WFL On 6/27/19, Tomas Rokicki <rokicki@gmail.com> wrote:
How transitive is strength in chess?
On Thu, Jun 27, 2019 at 2:38 PM Michael Collins <mjcollins10@gmail.com> wrote:
Perhaps this is interesting: if we have three players who have played three games and created a cycle (A beat B, B beat C, C beat A), a three-way tie in strength is NOT the maximum-likelihood solution; this cycle is most probable when, for some ordering, the stronger player wins with probability 2/3.
Of course the likelihood is the same for any ordering; but the point is that if we arbitrarily choose, say, A>B>C, we have a 'better' estimate than declaring a 3-way tie. Maybe this is an example of maximum-likelihood going wrong?
This assumes that probabilities are constrained to be consistent with some total ordering; the stronger player has at least 1/2 probability of winning, and if three players are ranked X>Y>Z then Prob(X beats Z) is at least as large as max(X-beats-Y , Y-beats-Z).
On Wed, Jun 26, 2019 at 12:44 PM Steve Witham <sw@tiac.net> wrote:
At 6/23/19, 5:25 PM, "Keith F. Lynch" <kfl@KeithLynch.net> wrote,
If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits.
It seems to me prior probabilities are necessary to talk about information.
An idea like that matchups *tend* to be *somewhat* consistent and transitive is the beginning of a prior. If I think that the total probability of one or more violation of transitivity or consistency is one in a binary million (2**20), then that probability gets divided between all the violating outcomes, so there would be more than 20 bits of information in any one of them.
On the other hand, the more unlevel the playing field, so to speak, the less *expected* surprise.
From my impression of statistics, what you do is start with a general model of how things work, which has hidden parameters, and then given an actual outcome, try to derive the hidden parameters most likely to give that outcome. (I actually don't understand why the peak of the curve is given such importance.)
So if each team has a "skill level", and the odds of A wins/B wins/tie are just a function of the two skills, then once the tournament is over you can back-figure the most likely vector of 8 skills, and from that pick the most skillful team! Easy peasy.
But, even having no prejudices about the teams to start with (not to mention ideas about how they interact), the amount of information the outcome represents depends on both the model (of behind-the-scenes Truth, not the tournament plan) and the actual outcome. Or, you can calculate the expected number of bits and turn off the TV satisfied.
I understand the Google pagerank algorithm is equivalent to applying one (linear?) model to this problem.
Of course, the information everyone wants to know is, who's the best team? Which for 8 teams is 3 bits without any prejudices. Then the question is, what are the odds a given method of matching teams gives the right answer (given some model of "best teams")? Because the less likely you're right, the fewer bits you actually delivered. On the other hand, if the best you can deliver is three bits, there are diminishing...
returns to even...
talking about...
this.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't think max likelihood goes wrong. A=B=C is unlikely because equality has measure zero compared to inequality. Realistically you need to consider how much inequality makes the cycle improbable. Brent On 6/27/2019 2:37 PM, Michael Collins wrote:
Perhaps this is interesting: if we have three players who have played three games and created a cycle (A beat B, B beat C, C beat A), a three-way tie in strength is NOT the maximum-likelihood solution; this cycle is most probable when, for some ordering, the stronger player wins with probability 2/3.
Of course the likelihood is the same for any ordering; but the point is that if we arbitrarily choose, say, A>B>C, we have a 'better' estimate than declaring a 3-way tie. Maybe this is an example of maximum-likelihood going wrong?
This assumes that probabilities are constrained to be consistent with some total ordering; the stronger player has at least 1/2 probability of winning, and if three players are ranked X>Y>Z then Prob(X beats Z) is at least as large as max(X-beats-Y , Y-beats-Z).
On Wed, Jun 26, 2019 at 12:44 PM Steve Witham <sw@tiac.net> wrote:
At 6/23/19, 5:25 PM, "Keith F. Lynch" <kfl@KeithLynch.net> wrote,
If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits.
It seems to me prior probabilities are necessary to talk about information.
An idea like that matchups *tend* to be *somewhat* consistent and transitive is the beginning of a prior. If I think that the total probability of one or more violation of transitivity or consistency is one in a binary million (2**20), then that probability gets divided between all the violating outcomes, so there would be more than 20 bits of information in any one of them.
On the other hand, the more unlevel the playing field, so to speak, the less *expected* surprise.
From my impression of statistics, what you do is start with a general model of how things work, which has hidden parameters, and then given an actual outcome, try to derive the hidden parameters most likely to give that outcome. (I actually don't understand why the peak of the curve is given such importance.)
So if each team has a "skill level", and the odds of A wins/B wins/tie are just a function of the two skills, then once the tournament is over you can back-figure the most likely vector of 8 skills, and from that pick the most skillful team! Easy peasy.
But, even having no prejudices about the teams to start with (not to mention ideas about how they interact), the amount of information the outcome represents depends on both the model (of behind-the-scenes Truth, not the tournament plan) and the actual outcome. Or, you can calculate the expected number of bits and turn off the TV satisfied.
I understand the Google pagerank algorithm is equivalent to applying one (linear?) model to this problem.
Of course, the information everyone wants to know is, who's the best team? Which for 8 teams is 3 bits without any prejudices. Then the question is, what are the odds a given method of matching teams gives the right answer (given some model of "best teams")? Because the less likely you're right, the fewer bits you actually delivered. On the other hand, if the best you can deliver is three bits, there are diminishing...
returns to even...
talking about...
this.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Brent Meeker -
Fred Lunnon -
Michael Collins -
Steve Witham -
Tomas Rokicki