Skip to main content
corrected equation to equate random variables
Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

The expected rank for player $i$ is $ER_i=1 + \sum_{j \ne i} I(i,j)$$R_i=1 + \sum_{j \ne i} I(i,j)$ where $I(i,j)$ is an indicator random variable for whether player $j$ has a higher score than player $i$, so $E[R_i] = 1 + \sum_{j \ne i} E[I(i,j)]$. The expected value of this indicator random variable$E[I(i,j)]$ can be computed by considering the $2^{2n-3}$ possible results of players $i$ and $j$ against the other players instead of the $2^{n \choose 2}$ tournaments. You can also write a recurrence for the distribution of the difference between the scores of players $i$ and $j$ after facing the first $k$ opponents which takes $O(n^2)$ steps to compute for numerical skill values.

I would not expect to find a closed form. Here is a way to eliminate some possible closed forms: Compute the exact value for particular choices of the skill parameters, possibly with some left as variables, and factor the numerator and denominator. A complicated factorization involving large primes suggests that there isn't be a simple closed form expression, or at least that it would have to be a sum of multiple terms.

For example, suppose there is one player with skill $3$, and $3$ players each with skills $1$ and $2$. The expected rank of the player with skill $3$ is $25439/9600$, and $25439$ is prime. If $0$-based ranks are more natural, $25439-9600$ is a product of two primes, $47\times 337$.

The expected rank for player $i$ is $ER_i=1 + \sum_{j \ne i} I(i,j)$ where $I(i,j)$ is an indicator random variable for whether player $j$ has a higher score than player $i$. The expected value of this indicator random variable can be computed by considering the $2^{2n-3}$ possible results of players $i$ and $j$ against the other players instead of $2^{n \choose 2}$ tournaments. You can also write a recurrence for the distribution of the difference between the scores of players $i$ and $j$ after facing the first $k$ opponents which takes $O(n^2)$ steps to compute for numerical skill values.

I would not expect to find a closed form. Here is a way to eliminate some possible closed forms: Compute the exact value for particular choices of the skill parameters, possibly with some left as variables, and factor the numerator and denominator. A complicated factorization suggests that there isn't be a simple closed form expression, or at least that it would have to be a sum of multiple terms.

For example, suppose there is one player with skill $3$, and $3$ players each with skills $1$ and $2$. The expected rank of the player with skill $3$ is $25439/9600$, and $25439$ is prime.

The rank for player $i$ is $R_i=1 + \sum_{j \ne i} I(i,j)$ where $I(i,j)$ is an indicator random variable for whether player $j$ has a higher score than player $i$, so $E[R_i] = 1 + \sum_{j \ne i} E[I(i,j)]$. The expected value $E[I(i,j)]$ can be computed by considering the $2^{2n-3}$ possible results of players $i$ and $j$ instead of the $2^{n \choose 2}$ tournaments. You can also write a recurrence for the distribution of the difference between the scores of players $i$ and $j$ after facing the first $k$ opponents which takes $O(n^2)$ steps to compute for numerical skill values.

I would not expect to find a closed form. Here is a way to eliminate some possible closed forms: Compute the exact value for particular choices of the skill parameters, possibly with some left as variables, and factor the numerator and denominator. A factorization involving large primes suggests that there isn't be a simple closed form expression, or at least that it would have to be a sum of multiple terms.

For example, suppose there is one player with skill $3$, and $3$ players each with skills $1$ and $2$. The expected rank of the player with skill $3$ is $25439/9600$, and $25439$ is prime. If $0$-based ranks are more natural, $25439-9600$ is a product of two primes, $47\times 337$.

Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

The expected rank for player $i$ is $ER_i=1 + \sum_{j \ne i} I(i,j)$ where $I(i,j)$ is an indicator random variable for whether player $j$ has a higher score than player $i$. The expected value of this indicator random variable can be computed by considering the $2^{2n-3}$ possible results of players $i$ and $j$ against the other players instead of $2^{n \choose 2}$ tournaments. You can also write a recurrence for the distribution of the difference between the scores of players $i$ and $j$ after facing the first $k$ opponents which takes $O(n^2)$ steps to compute for numerical skill values.

I would not expect to find a closed form. Here is a way to eliminate some possible closed forms: Compute the exact value for particular choices of the skill parameters, possibly with some left as variables, and factor the numerator and denominator. A complicated factorization suggests that there isn't be a simple closed form expression, or at least that it would have to be a sum of multiple terms.

For example, suppose there is one player with skill $3$, and $3$ players each with skills $1$ and $2$. The expected rank of the player with skill $3$ is $25439/9600$, and $25439$ is prime.