| Life In 19x19 http://www.lifein19x19.com/ |
|
| Round-robin: Frequency of Ties http://www.lifein19x19.com/viewtopic.php?f=45&t=947 |
Page 1 of 2 |
| Author: | RobertJasiek [ Thu Jun 24, 2010 10:07 pm ] |
| Post subject: | Round-robin: Frequency of Ties |
Let P (even) be the number of players in a single round-robin and R = P-1 be the number of rounds. Let there be either a) no jigos or b) jigos. Advanced consideration: Assume a particular frequency for jigos. Each player's NumberOfWinsScore is the sum of his number of wins plus half his number of jigos. Let us ignore specific players but consider result tables in general regardless of player names. Let there be only one result criterion: the NumberOfWinsScore. Places with equal scores are tied. Depending on P, how many different result distributions (tables) do exist? Depending on P, how many of the result distributions have a tie on place 1? How many on place 2? Etc. How many on place P? |
|
| Author: | Harleqin [ Fri Jun 25, 2010 3:04 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Do you want to assume players of even strength? |
|
| Author: | tj86430 [ Fri Jun 25, 2010 3:43 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Harleqin wrote: Do you want to assume players of even strength? The questions posed by OP can be answered without knowing anything about the strength. Example: - two players: one possible distribution, no ties (unless jigo is possible) - four players: four possible distributions (again with no jigos), one of which contains three player tie for the first place, one of which contains a two player tie for the first place and another two player tie for the third place, one of which contains a three player tie for the second place and one of which contains no ties etc. e: there probably is an easy way to calculate these, but I'm not sure if I can figure it out. I may write a small program for this, unless someone does the calculations before me. |
|
| Author: | RobertJasiek [ Fri Jun 25, 2010 5:17 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Harleqin, the question is independent of player strengths. tj86430, maybe there is already some theory but it might be hard to find. Programmed calculations would be great! In practice, such questions are interesting up to P=16, e.g, for various components of EC systems. On http://en.wikipedia.org/wiki/Tournament_graph there is a bit of theory in what they call "score sets" but that does not answer my questions directly, except that "Let s(n) be the number of different score sequences of size n. The sequence s(n) (sequence A000571 in OEIS) starts as: 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ..." might for the even numbers extract answer my first question, if I interpret the cited text correctly. Then http://www.research.att.com/~njas/sequences/A000571 gives yet more numbers for Number of different scores that are possible in an n-team round-robin tournament: 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 915695102, 3251073303, 11605141649, 41631194766, 150021775417, 542875459724, 1972050156181 So the even case numbers are: 2 4 6 8 10 12 14 16 1, 4, 22, 167, 1486, 14805, 158808, 1799659, ... The numbers grow rapidly! So more theory is needed. (Manual calculation is already too tedious.) Not only different numbers but also frequencies of same score distributions will be relevant. |
|
| Author: | pwaldron [ Fri Jun 25, 2010 8:38 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
I get the following n | Number of distinct tournaments | Number of ties for first place 2 | 1 | 0 4 | 4 | 2 6 | 22 | 9 8 | 167 | 67 10 | 1486 | 561 12 | 14805 | 5419 14 | 158808 | 56461 16 | 1799659 | 625699 Does anyone know how to get tables to look pretty? |
|
| Author: | tj86430 [ Fri Jun 25, 2010 9:03 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
pwaldron wrote: n | Number of distinct tournaments | Number of ties for first place 6 | 22 | 9 I got 6 20 7, but I have probably overlooked something: 543210 543111 542220 542211 533310 533220 533211 532221 522222 444210 444111 444300 443310 443220 443211 442221 433320 433311 433221 432222 |
|
| Author: | xed_over [ Fri Jun 25, 2010 9:07 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
pwaldron wrote: Does anyone know how to get tables to look pretty? use code tags pwaldron wrote: Code: n | Number of distinct tournaments | Number of ties for first place 2 | 1 | 0 4 | 4 | 2 6 | 22 | 9 8 | 167 | 67 10 | 1486 | 561 12 | 14805 | 5419 14 | 158808 | 56461 16 | 1799659 | 625699 |
|
| Author: | pwaldron [ Fri Jun 25, 2010 10:04 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
tj86430 wrote: 6 20 7, but I have probably overlooked something: You're missing the set where the winner only wins three games. Also, [4 4 4 3 0 0] isn't valid. It's a round robin so you can't have two players without wins. |
|
| Author: | willemien [ Fri Jun 25, 2010 11:30 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
RobertJasiek wrote: Let P (even) be the number of players in a single round-robin and R = P-1 be the number of rounds. Let there be either a) no jigos or b) jigos. Advanced consideration: Assume a particular frequency for jigos. Each player's NumberOfWinsScore is the sum of his number of wins plus half his number of jigos. Let us ignore specific players but consider result tables in general regardless of player names. Let there be only one result criterion: the NumberOfWinsScore. Places with equal scores are tied. Depending on P, how many different result distributions (tables) do exist? Depending on P, how many of the result distributions have a tie on place 1? How many on place 2? Etc. How many on place P? What do you mean? Did some thinking for a round robin of 4 players A Round robin of 4 players means 6 games and excluding jigo's it means that there are 64 (2 power6) possible combinations of game results. of these 64 24 (4 faculty) are clear results (every player has a definite place without ties) the rest of them (40 or 62.5% has one of more ties) I need to do some more testing but my hunch is that for more players the percentage of ties will grow. |
|
| Author: | Bill Spight [ Fri Jun 25, 2010 11:50 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
4 person round robin Players A, B, C, D > means beats. Round 1 Without loss of generality (Wolog) A > B C > D Round 2 Wolog A > C B > D Round 3 A ? D B ? C The winner of B vs. C will have 2 wins. If A wins she will be the sole winner, if D wins there will be a tie. Assuming that the probability that A wins is 1/2, the probability of a sole winner is 1/2, and the probability of a tie is 1/2. Just as pwaldron's numbers indicate.  Edit: I see that this is wrong: Round 2 Wolog A > C B > D 
|
|
| Author: | pwaldron [ Fri Jun 25, 2010 1:37 pm ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
willemien wrote: I need to do some more testing but my hunch is that for more players the percentage of ties will grow. I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows. |
|
| Author: | daniel_the_smith [ Fri Jun 25, 2010 1:45 pm ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
pwaldron wrote: I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows. Oh no, I just saw an infinite crowd of go players checking into Hilbert's hotel to play a single round robin. Someone should tell them... 
|
|
| Author: | willemien [ Fri Jun 25, 2010 11:25 pm ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Bill Spight wrote: 4 person round robin Edit: I see that this is wrong: Round 2 Wolog A > C B > D You did got me wondering where i was wrong. (the results did differ) Guess that next time it will be me again that was wrong  (As usual) but i do think that A>C was Wolog (but agree that B>D was not) |
|
| Author: | willemien [ Sun Jun 27, 2010 9:55 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
pwaldron wrote: willemien wrote: I need to do some more testing but my hunch is that for more players the percentage of ties will grow. I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows. no that is not true n! is the amount of games without ANY ties. (for any place) While the question was of ties in the first 3 places. a quite more limited amound. and unfortunedly it will cost a lot odtf time to calculate t (even for an 6 persons round) |
|
| Author: | Bill Spight [ Sun Jun 27, 2010 11:34 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
willemien wrote: Bill Spight wrote: 4 person round robin Edit: I see that this is wrong: Round 2 Wolog A > C B > D You did got me wondering where i was wrong. (the results did differ) Guess that next time it will be me again that was wrong (As usual) but i do think that A>C was Wolog (but agree that B>D was not) I think you're right.
|
|
| Author: | RobertJasiek [ Mon Jun 28, 2010 2:23 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
The following numbers come closer to what I am interested in: FrequencyOfTies, FrequencyOfTopMostTies, FrequencyForPlayerToBeInTie. Code: No jigos P=2 Wins #PlayerCombinations 10 2 1 different distribution 0 ties Code: P=4
Wins #PlayerCombinations TiesOnPlaces #PlayersInTies 3210 24 - 0 3111 4 2 3 2220 4 1 3 2211 6 1+3 4 ---------------------------------------------------- 38 4 different distributions 3 with ties Place FrequencyOfTies 1 10/38 2 4/38 3 6/38 Place FrequencyOfTopMostTies 1 10/38 2 4/38 ---------------------------- 14/38 FrequencyForPlayerToBeInTie (4*3+4*3+6*4)/(4*38) = 48/152 |
|
| Author: | willemien [ Mon Jun 28, 2010 7:26 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Sorry but there are statistical errors on your overview for 4 players. I am not at home but provisionally corrected it should be something like: Quote: p=4 Wins #PlayerCombinations TiesOnPlaces #PlayersInTies 3210 24 - 0 3111 8 2 3 2220 8 1 3 2211 24 1+3 4 ---------------------------------------------------- 64 4 different distributions 3 with ties Place FrequencyOfTies 1 32/64 2 16/64 3 32/64 Place FrequencyOfTopMostTies 1 32/64 2 16/64 ---------------------------- 48/64 FrequencyForPlayerToBeInTie THIS NEEDS MORE INVESTIGATION (8*3+8*3+24*4)/(4*64) = 144/256 ?? I don't know where your factors 4 4 and 6 come from (I guess from combinatorix) but they are not the right weighting factors to use here. You ned to go back to base facts. not just start from halfway calculations. Always remember There are Lies, Dammed Lies and Statistics. 
|
|
| Author: | pwaldron [ Mon Jun 28, 2010 8:29 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
RobertJasiek wrote: Let us ignore specific players but consider result tables in general regardless of player names. ... Depending on P, how many different result distributions (tables) do exist? Your recent calculations don't treat the tournaments in a general way: 3210 is structurally the same as 0123. However, if you do distinguish those two cases, then a tournament of P players will have 2^(P*(P-1)/2 different outcomes if there are no jigos, and 3^(P*(P-1)/2) if there are. Willemien has shown the 64 possible outcomes of an event with 4 players and no jigos. A hint as you look for your error: simple permutations of the result vector aren't enough for enumeration. Players can end up with the same scores by beating different people. A 2211 result can occur with player D beating any of players A, B or C. |
|
| Author: | RobertJasiek [ Mon Jun 28, 2010 9:40 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
willemien's text retagged for greater reading pleasure: Code: p=4
Wins #PlayerCombinations TiesOnPlaces #PlayersInTies 3210 24 - 0 3111 8 2 3 2220 8 1 3 2211 24 1+3 4 ---------------------------------------------------- 64 4 different distributions 3 with ties Place FrequencyOfTies 1 32/64 2 16/64 3 32/64 Place FrequencyOfTopMostTies 1 32/64 2 16/64 ---------------------------- 48/64 FrequencyForPlayerToBeInTie THIS NEEDS MORE INVESTIGATION (8*3+8*3+24*4)/(4*64) = 144/256 ?? |
|
| Author: | RobertJasiek [ Mon Jun 28, 2010 10:23 am ] |
| Post subject: | Re: Round-robin: Frequency of Ties |
Oops. Thanks to willemien and pwaldron for pointing out my thinko. I thought: "3111. The 3 wins can belong to any of the 4 players. Then there is only way to get the 111 pattern." But I overlooked that actually the pattern itself is insufficient information. If A represents the 3 wins player, then it might mean either B>C>D>B or B>D>C>B, which are 2 possibilities to be combined with the 4. We get 4 * 2 = 8. I see. How to spell out 2211? There are 6 possibilities which two players can be those with 2 wins. Let us look at one of the 6 cases in detail by calling these two players A and B: A>B + A>C + D>A + B>C + B>D + C>D A>B + C>A + A>D + B>C + B>D + D>C B>A + A>C + A>D + B>C + D>B + C>D B>A + A>C + A>D + C>B + B>D + D>C There are these 4 subcases. So we get the 6 * 4 = 24. willemien, how do you get 3 | 32/64 as FrequencyOfTies? Must that not be 24/64? |
|
| Page 1 of 2 | All times are UTC - 8 hours [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|