{"id":1290,"date":"2016-09-18T13:45:13","date_gmt":"2016-09-18T18:45:13","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1290"},"modified":"2016-09-26T21:49:23","modified_gmt":"2016-09-27T02:49:23","slug":"randomized-team-drafting-strategy","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/randomized-team-drafting-strategy\/","title":{"rendered":"Randomized team drafting strategy"},"content":{"rendered":"<p>This <a href=\"http:\/\/fivethirtyeight.com\/features\/how-high-can-count-von-count-count\/\">Riddler Classic puzzle<\/a> explores a randomized team drafting strategy designed to prevent teams from throwing games.<\/p>\n<blockquote><p>You are one of 30 team owners in a professional sports league. In the past, your league set the order for its annual draft using the teams\u2019 records from the previous season \u2014 the team with the worst record got the first draft pick, the team with the second-worst record got the next pick, and so on. However, due to concerns about teams intentionally losing games to improve their picks, the league adopts a modified system. This year, each team tosses a coin. All the teams that call their coin toss correctly go into Group A, and the teams that lost the toss go into Group B. All the Group A teams pick before all the Group B teams; within each group, picks are ordered in the traditional way, from worst record to best. If your team would have picked 10th in the old system, what is your expected draft position under the new system?<\/p>\n<p><em>Extra credit:<\/em> Suppose each team is randomly assigned to one of T groups where all the teams in Group 1 pick, then all the teams in Group 2, and so on. (The coin-flipping scenario above is the case where T = 2.) What is the expected draft position of the team with the Nth-best record?<\/p><\/blockquote>\n<p>Here is my solution to the general case:<br \/>\n<a href=\"javascript:Solution('soln_teamdraft1','toggle_teamdraft1')\" id=\"toggle_teamdraft1\">[Show Solution]<\/a><\/p>\n<div id=\"soln_teamdraft1\" style=\"display: none\">\n<p>Number all the teams according to their original seeding order and suppose there are $K$ teams in total. Label the groups $1,2,\\dots,T$, where Group 1 gets picked first, Group 2 second, and so on.<\/p>\n<p>Let&#8217;s calculate team $N$&#8217;s expected draft position given that it was placed in Group $i$. For each other team $k$, define the random variable:<br \/>\n\\[<br \/>\nX_k = \\begin{cases}<br \/>\n1 &#038; \\text{if team }k\\text{ finishes ahead of team }N\\\\<br \/>\n0 &#038; \\text{if team }k\\text{ finishes behind team }N<br \/>\n\\end{cases}<br \/>\n\\]The final draft position of team $N$ is therefore $1 + \\sum_{k\\ne N} X_k$, where we sum over $k=1,2,\\dots,K$ but exclude team $N$. The expected value of this sum is the sum of expected values (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Expected_value#Linearity\">linearity of expectation<\/a>), so we can focus our attention on a particular other team $k$.<\/p>\n<ul>\n<li> If $1 \\le k \\le N-1$, then $X_k = 1$ if team $k$ ended up in groups $1$ through $i$. The probability of this occurring is $\\tfrac{i}{T}$.\n<li> If $N+1 \\le k \\le K$, then $X_k = 1$ if team $k$ ended up in groups $1$ through $i-1$. The probability of this occurring is $\\tfrac{i-1}{T}$.\n<\/ul>\n<p>The expected draft position of team $N$ is therefore:<br \/>\n\\[<br \/>\n1 + (N-1)\\frac{i}{T} + (K-N)\\frac{i-1}{T}<br \/>\n\\]Remember that this was conditioned on team $N$ ending up in Group $i$, which happens with probability $\\tfrac{1}{T}$. So the final expected draft position of team $N$ is therefore:<br \/>\n\\begin{align}<br \/>\n\\sum_{i=1}^T \\frac{1}{T} \\left( 1 + (N-1)\\frac{i}{T} + (K-N)\\frac{i-1}{T} \\right) \\\\<br \/>\n\\end{align}After simplifying (make use of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Triangular_number\">this<\/a> identity), we find that the expected final position for team $N$ is given by the formula<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\n\\frac{2N+(K+1)(T-1)}{2T}<br \/>\n$<\/span><\/p>\n<p>We can perform a few quick sanity checks to convince ourselves that this solution is correct.<\/p>\n<ul>\n<li> When $T=1$ (only one group), the formula yields $N$, the same as the original seeding, as it should.\n<li> When $K=N=1$ (only one team), the formula yields $1$, as it should.\n<li> More precisely, if the original seed is $N = \\tfrac{K+1}{2} + \\Delta$, where $\\Delta$ is the offset from the middle, the formula yields an expected draft position of $\\tfrac{K+1}{2} + \\tfrac{\\Delta}{T}$. In other words, if you started off better than average, you can expect to end up better than average and similarly if you started below average. The division by $T$ shows that as you add more groups, the randomized drafting strategy has an equalizing effect.\n<\/ul>\n<p>In the particular case mentioned in the problem statement, we have $K=30$, $N=10$, and $T=2$, which leads to an expected value of $\\frac{51}{4} = 12.75$.<\/p>\n<\/div>\n<p>While the expected draft position is not that difficult to characterize, one can also ask about the <em>distribution<\/em> of draft positions:<br \/>\n<a href=\"javascript:Solution('soln_teamdraft2','toggle_teamdraft2')\" id=\"toggle_teamdraft2\">[Show Solution]<\/a><\/p>\n<div id=\"soln_teamdraft2\" style=\"display: none\">\n<p>Finding the actual distribution of draft positions is more complicated that just finding its expected value. To find the distribution, we will answer the question: &#8220;what is the probability that team $N$ finishes with position $j$ given that it lands in Group $i$?&#8221;. We&#8217;ll compute the probability by counting the number of ways that $j-1$ other teams can end up ahead of team $N$ in the draft.<\/p>\n<ul>\n<li> Start by considering the teams $1 \\le k \\le N-1$, which are the teams that have a higher seed than team $N$. Suppose exactly $p$ of these teams end up in Group $i$. There are ${N-1 \\choose p}$ ways this can happen, each with probability $\\tfrac{1}{T}.$ Therefore we have a net probability of $\\color{red}{P_1 = {N-1\\choose p}\\left(\\tfrac{1}{T}\\right)^p}$.\n<li> Out of the remaining $N-1-p$ teams, suppose exactly $r$ of them end up in groups $1$ through $i-1$. There are ${N-1-p \\choose r}$ ways this can happen, each with probability $\\tfrac{i-1}{T}$. The net probability is $\\color{red}{P_2 = {N-1-p \\choose r}\\left(\\tfrac{i-1}{T}\\right)^r}.$ If $i=1$, then $P_2=0$ for all values of $p$.\n<li> The remaining $N-1-p-r$ teams must necessarily be in groups $i+1$ through $T$, each with probability $\\tfrac{T-i}{T}$. The net probability is $\\color{red}{P_3 = \\left(\\tfrac{T-i}{T}\\right)^{N-1-p-r}}.$ If $i=T$, then $P_3=0$.\n<li> There must be $j-1$ teams ahead of team $N$ in the final draft, and we have thus far accounted for $p+r$ of them. The rest must come from teams $N+1 \\le k \\le K$, which are the teams that have a lower seed than the team $N$. These must end up in groups $1$ through $i-1$. There are ${K-N \\choose j-1-p-r}$ ways to do this, each with probability $\\tfrac{i-1}{T}$. The net probability is $\\color{red}{P_4 = {K-N \\choose j-1-p-r}\\left(\\tfrac{i-1}{T}\\right)^{j-1-p-r}}.$ If $i=1$, then $P_4=0$.\n<li> The remaining $K-N-j+1+p+r$ teams must necessarily be in groups $i$ through $T$, each with probability $\\tfrac{T-i+1}{T}$. The net probability is $\\color{red}{P_5 = \\left(\\tfrac{T-i+1}{T}\\right)^{K-N-j+1+p+r}}.$\n<\/ul>\n<p>This accounts for every possible arrangement, so to find the probability that team $N$ finishes with position $j$, we must sum over all possible values of $p$ and $r$, and then sum over possible values of $i$ while including an additional $\\frac{1}{T}$ factor as we did in the solution to the first part. The final probability of interest is therefore:<br \/>\n\\[<br \/>\nP(K,N,T,j) = \\frac{1}{T}\\sum_{i=1}^T \\sum_{p=0}^{N-1} \\sum_{r=0}^{N-1} P_1P_2P_3P_4P_5<br \/>\n\\]Note that some terms will be identically zero. We use the convention that ${a \\choose b} = 0$ if $b < 0$.\n\nUnfortunately, this messy formula doesn't appear to simplify to anything nice, so we have to be content with computing it numerically. To illustrate what the result looks like, here is a plot of $P(30,10,T,j)$ as a function of $j$ and for increasing values of $T$ (the number of groups).\n\n<a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/09\/team_rankings.gif\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/09\/team_rankings.gif\" alt=\"team_rankings\" width=\"950\" height=\"455\" class=\"aligncenter size-full wp-image-1320\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/09\/team_rankings.gif 950w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/09\/team_rankings-300x144.gif 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/09\/team_rankings-768x368.gif 768w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<ul>\n<li>When $T=1$, the distribution is concentrated at $N=10$, since there is no probability involved; each team will always be drafted in seed order.\n<li>When $T=2$, the distribution is bimodal. Even though the initial seed was $N=10$ and the expected value of the final draft position is $12.75$ as we computed earlier, the probability of being drafted anywhere near the expected value is very low! This makes sense, because whether we end up in Group 1 or Group 2 has a substantial effect on our final draft position.\n<li>Similar multi-modal distributions occur for $T=2,3,\\dots$ Ultimately, the distribution converges to the uniform distribution. Again, this makes sense; if you imagine a <em>very<\/em> large number of groups, the probability that two teams end up in the same group is vanishingly small. So the final draft position is essentially determined by the group number only.\n<\/ul>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler Classic puzzle explores a randomized team drafting strategy designed to prevent teams from throwing games. You are one of 30 team owners in a professional sports league. In the past, your league set the order for its annual draft using the teams\u2019 records from the previous season \u2014 the team with the worst &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/randomized-team-drafting-strategy\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Randomized team drafting strategy&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1320,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[18,8,2],"class_list":["post-1290","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-linearity-of-expectation","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=1290"}],"version-history":[{"count":33,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1290\/revisions"}],"predecessor-version":[{"id":1328,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1290\/revisions\/1328"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1320"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}