gtMath

Karl and Richard are playing a series to 7 (no need to win by 2) in a two-player game, and their skill levels are such that Karl has a probability $p$ of winning any individual game in the series.

If we give Karl a handicap of 2 games so that he only needs to win 5 games to win the series, whereas Richard needs to win 7, what is the single-game probability $p$ that gives each player a 50% chance of winning the series?

I've tagged this post with "Billiards" since the question came from the director of my pool league (who I hear is an avid GTM reader). Actually, what he really wants to know is the best way to set up the scoring, tie-breakers, and handicaps in one of the leagues, but in order to answer these questions, I wanted to start by looking at just one series and then extend that to the more general questions. This analysis really has nothing to do with pool though, so it would work for any other game as well.

Binomial Coefficients

To start out, we'll need the binomial coefficients $\binom{n}{k}$, which are read as "$n$ choose $k$." $\binom{n}{k}$ is the number of ways to choose $k$ items from a set of $n$ distinct items, for example the number of $k$-person boards of directors that can be chosen from $n$ candidates. Note that choosing the $k$ candidates who are included in the board is the same as choosing the $n-k$ who are not included, which means that $\binom{n}{k} = \binom{n}{n-k}$. The formula for the binomial coefficients is $$\dbinom{n}{k} = \dfrac{n!}{k! (n-k)!}$$ from which the above-mentioned symmetry is obvious. Note that even though this is a fraction, it always comes out to be an integer.

The binomial coefficients got their name from the fact that they are the coefficients in the expansion of binomials: $$ (x+y)^n = \sum_{k=0}^{n}{\dbinom{n}{k} x^k y^{n-k}}
$$ This is because in the product $(x+y)(x+y)...(x+y)$ (with $n$ factors of $(x+y)$), each factor of $(x+y)$ contributes either an $x$ or a $y$ to a factor in the sum. If you have $k$ $x$'s in a term, the other $n-k$ factors of $(x+y)$ must have contributed a $y$. There are $\binom{n}{k}$ ways to get $k$ $x$'s and $n-k$ $y$'s, hence the formula. If anyone wants more detail on that, just ask in the comments, and I'll give a more detailed explanation.

Most identities about binomial coefficients can be proved either by using the formula with the factorials, or via a combinatorial argument. For example, for integers $n$, $m$, and $k$ with $0 \leq k \leq m \leq n$, we have the following identity, known as the subset of a subset identity: $$\dbinom{n}{m} \dbinom{m}{k} = \dbinom{n}{k} \dbinom{n-k}{m-k}
$$Algebraic proof: $$
\begin{align}
\dbinom{n}{m} \dbinom{m}{k} &= \dfrac{n!}{m! (n-m)!} \cdot \dfrac{m!}{k! (m-k)!} \\[3mm]
&= \dfrac{n!}{k!(n-m)!(m-k)!} \\[3mm]
&= \dfrac{n!}{k! (n-k)!} \cdot \dfrac{(n-k)!}{(n-m)! (m-k)!} \\[3mm]
&= \dbinom{n}{k} \dbinom{n-k}{m-k} \tag*{$\square$}
\end{align}
$$Combinatorial proof:
The left side of the identity is the number of ways to choose a board of directors with $m$ members from $n$ candidates, and then choose $k$ executive members from the $m$. The right side counts the number of ways to choose $k$ executive members from the $n$ candidates and then choose the $m-k$ non-executive board members from the $n-k$ remaining candidates. These count the same thing, so the two sides must be equal. $\tag*{$\square$}$

Winning a series to 7

In order to win a series to 7, without needing to win by 2, Karl needs to win 7 games, with Richard winning anywhere from 0 to 6 games in the series. If Karl wins 7 games, and Richard wins 3 games (for example), there will be a total of 10 games in the series. The 3 games that Richard does win can come anywhere in the 10 games, except for the 10th game- if it did, then Karl would have already won 7 and the series would not have made it to 10 in the first place. So we can choose from the first $10-1=9$ games where Richard's 3 wins go.

The probability that Karl wins a given game is $p$, which means the probability that Richard beats Karl is $1-p$. Combining all this, we can see that the probability that Karl beats Richard in a race to 7, with Richard winning 3 games, is $$ \binom{10-1}{3} p^7 (1-p)^3
$$Since Karl can win the series with Richard winning anywhere from 0 to 6 games, the total probability that Karl wins the series is the sum over the possible outcomes, with the summation index $k$ being the number of wins Richard gets in the series: $$
\begin{align}
{\Bbb P}(\text{Karl wins the series}) &= \sum_{k=0}^{7-1}{\binom{7+k-1}{k} p^7 (1-p)^k} \\[3mm]
&= \sum_{k=0}^{6}{\binom{6+k}{k} p^7 (1-p)^k}
\end{align}
$$ Here's a graph of the probability that Karl wins the series, for different values of $p$:


Not surprisingly, if there's a 50% chance that either player wins an individual game, then there's also a 50% chance that either player wins the series.

Now, let's say we give Karl a handicap of 2 games so that to win the series, Karl needs to win 5 games and Richard needs to win 7. More generally, if we call the handicap $H$, where $0 \leq H \leq 6$, then by the same reasoning as we used above, we get the modified formula: $$
{\Bbb P}(\text{Karl wins the series}) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}
$$ Now Karl only needs to win $7-H$ games, and so the total number of games in the series for a given value of $k$ wins for Richard, is $7-H+k$, with the $k$ losses once again being placed anywhere but the last game.

Here are the graphs of Karl's probabilities of winning the series given different values of $p$ and $H$ (you can click to expand the picture):


Now, I'd love to be able say we're done here, but the fact is that for some real Karl and Richard, we have no idea what the value of $p$ is unless we are lucky enough to have a history of, say, 100 games between these two players. And even then, they could have improved over time or gotten rusty or whatever so that games they played a few months ago aren't so telling now as to the value of $p$.

We do know that every player in the league is assigned a ranking (which directly determines the handicap against an opponent) which is certainly partly subjective and determined based on observation by a few very experienced players who run, and possibly play in, the league. Instead of trying to guess $p$ and then assigning the rankings, which would be useless in the absence of a large history of games between each set of two players, we can use the handicaps to back out the value of $p$ that makes the match 50-50. For example, if Karl and Richard's rankings are such that Karl gets a handicap of 3, we can see from the graph above that the match will be 50-50 if Karl's probability $p$ of winning an individual game is about 35.5%.

Using Excel's Goal Seek functionality, I've backed out the values of $p$ that make a 7-game series 50-50 for different handicaps:


To test whether a player's handicap is appropriate, one could take all that player's games against opponents of different ranks and see what percentage of individual games he wins and how far off those percentages are from the table above (perhaps using a chi-square test for goodness of fit). If there are not enough games to do this analysis for individual players, then one could start by looking at the percentages for all games and then looking into the ranks furthest away from the table values and seeing if the stats of any particular player(s) are driving the difference. That's a bit of a manual exercise, but it's a start...

GTM Reader Challenge

"Backing out" $p$ basically means finding the inverse of the function $f(p) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}$. We know the function has an inverse because if you look at the graphs, they all pass the horizontal line test. To be more rigorous, they are polynomials in $p$ and thus continuous, and $f(0)=0$ and $f(1)=1$, so the intermediate value theorem tells us that $f$ is surjective. Furthermore, $f$ is increasing on the interval $p \in [0,1]$, so it's also one-to-one, and thus has an inverse.

Now, while Excel Goal Seek will certainly work for this, it would be kind of nice to know the inverse function, so I worked for a few hours today trying to figure out how to invert $f$, but couldn't quite figure it out. Maybe one of my more nerdy readers wants to take a crack at it? Otherwise, maybe I'll go post the question on stack exchange...

[Update 7/29/2015: there's been some confusion on the question I'm asking, so just to clarify, for the purposes of finding the inverse of $f(p)$, assume that the $H$ in the formula above is a constant. So technically, there is a different function $f$ for each value of $H$, which I guess you could call $f_{H}(p)$ or something.]

What I was trying (and maybe this isn't the best way to go about it) was to find a not-too-awful formula for the coefficient of $p^n$ in the sum above and then try to use the Lagrange inversion formula, but it gets a bit messy with all the binomial coefficients. I tried to expand the $(1-p)^k$, turning the sum into a double sum, then switch the order of summation (making sure to adjust the summation limits- the Iverson bracket is helpful at this step), and finally simplify somehow using identities of the binomial coefficients such as the subset of a subset identity above, but said simplification proved elusive, so I didn't even bother with the inversion formula.

Anyone have any thoughts on that or maybe a different way to find the inverse of $f(p)$? Let me know in the comments or email me, and I can provide more details of the computation I tried.

Thanks for reading, and I will try to do a follow-up on this post soon. As always, feel free to ask questions in the comments section.

Prerequisites: Pool Part 1, Similar Triangles

In part 1, we showed how to pocket an object ball with some basic physics. In part 2, we'll derive simple methods for making bank and kick shots using similar triangles.

For all of the below, we'll assume, unless explicitly stated otherwise, that we can ignore the effects of spin on the balls that would alter their trajectories. In practice, English (side-spin) as well as topspin and backspin (sliding) will affect the trajectories and need to be taken into account for more complicated shots. For example, if the target ball is to be banked off a rail very close by, it will still be sliding upon contact, which changes its trajectory coming off the rail. Ball speed also affects the trajectory off the rails, since a faster ball compresses the rail more and changes the angle a bit. We'll ignore these effects in our analysis, which should suffice for most easier bank and kick shots you'll encounter, where you just need to hit the cue ball with medium speed and at center. If any good players are reading this, commentary is welcome on how to use spin on some of these shots.

The one-rail bank

In part 1, we looked at a straight shot into the side pocket. Now, suppose we have the following situation where the purple 4 ball is blocking the line to the side pocket:
We need to find an alternative to the shot from part 1. One solution would be to take the long-distance shot to the top-right corner pocket, but we're going to look at an alternative, the bank shot, where we hit the 2 off the top rail and into the bottom side pocket.

The key to executing this shot is the reflection principle, that the 2 will bounce off the rail at the same angle with which it bounces into the rail- angle in equals angle out. The problem is to find the correct point on the rail to hit the 2 into, where angle in = angle out will get the ball on a trajectory to the side pocket.

Take a look at the following diagram, which is the same layout, but with two triangles drawn on.
The angle $\theta$ is the angle in and out. If the contact point with the rail, $Q$, is chosen correctly, then the angle $\theta$ will be the correct one to send the 2 to the target pocket. Now, because the two $\theta$ angles are equal and the yellow line is drawn at a 90 degree angle to the rail, we know that angles $OQP$ and $SQR$ are also equal. Since angles $OPQ$ and $SRQ$ are both right angles and thus equal, the triangles $OPQ$ and $SRQ$ are similar by angle-angle.

Let's use the notation $L(\overline{AB})$ for the length of a line segment $\overline{AB}$. The similarity of triangles $OPQ$ and $SRQ$ implies that the ratios $\dfrac{L(\overline{PQ})}{L(\overline{QR})}$ and $\dfrac{L(\overline{OP})}{L(\overline{SR})}$ are equal.

Remember that $Q$ is still at an unknown position, but given the equality of those ratios, we can find it. $L(\overline{OP})$ and $L(\overline{SR})$ are known lengths, which can be measured in units of segments. One segment is the distance between two of the white diamonds (or sometimes they are circles) running along the sides of the table. In the diagram above, $L(\overline{OP})$ is just shy of 2 segments, and $L(\overline{SR})$ is just shy of 4 segments. Thus $\dfrac{L(\overline{PQ})}{L(\overline{QR})} \approx \dfrac{1}{2}$. Since $L(\overline{PR})$ is about 2 segments, we see that the correct position for $Q$ puts $L(\overline{PQ}) \approx \dfrac{2}{3}$ and $L(\overline{QR}) \approx \dfrac{4}{3}$.

Alternative method: parallel shifts

The ratio calculation above is relatively simple and works, but can be a bit annoying to work out while playing. There is an alternative method that achieves the same result without having to think about any ratio calculations.

Below is the same diagram as the previous one, but with the blue lines added in:
The slope of line $OQ$ is the same as the slope of line $MR$, i.e. the lines are parallel. You can prove this by assigning coordinates to each of the points and calculating the two slopes (it's probably easiest to assign $O=(0,0)$ and go from there). This being the case, we have an easier method for finding point $Q$:

1. Find the midpoint $M$ between the 2 ball and the target pocket.

2. Make a line (with your cue stick) from $M$ to the opposite pocket.

3. Move your cue, keeping it parallel, over to the 2 ball, and where it intersects the top rail is the target contact point $Q$.

A similar method will work for kick shots as well.

The one-rail kick

The kick shot is similar to the bank, except we hit the cue ball off a rail and into an object ball, as opposed to the bank, where we hit the cue ball straight into the object ball, which then bounces off a rail.

Take a look at the following diagram:
Here, we have the cue ball and 2 ball in the same places as before, but the cue ball's line to the 2 is blocked by the purple 4. In order to make contact with the 2, we need to hit the cue ball off a rail first to avoid hitting the 4 before the 2 (for example, if we're playing 9-ball, where you need to hit the lowest-numbered ball first or else give your opponent ball-in-hand).
The red triangles above show a set-up just like the bank above, with the two red triangles being similar. Now, instead of going to a pocket, the blue line goes to the point where the target ending spot lines up with the rail. I won't go through the whole thing again, since it's basically the same thing. Find $M$, draw a line from $M$ to the spot where the target ending position lines up with the rail, and parallel shift the line over to the cue ball to see where it needs to hit the rail.

The two-rail kick

This is a very difficult shot, but if you can make contact on these, then you'll save yourself from giving a good opponent ball-in-hand and running the table on you. Suppose we now have this set-up where there is no way to execute a one-rail kick and hit the 2 first:
Once again, the translucent cue ball is the desired position of the cue ball at contact, and as you can see, the only way to get it there is by hitting the cue ball off of at least two rails. We'll start by drawing a diagram similar to the ones above:
Note that this diagram is not exactly to scale, so some of the lines that should be parallel look a bit off. The same reason it is difficult to draw the diagram is the reason that this shot is trickier to work out than the one-rail kick: we need to work out the unknown contact point $C$, but the trouble is that a change in $C$ changes the angle off the bottom rail and thus also changes the unknown contact point $E$ on the second rail.

The reflection principle will hold at both $C$ and $E$, and we need to work it out so that the cue ball ends up at $G$. The three red triangles are all similar by angle-angle, and this fact gives us a few equations we can use to solve for the location of point $C$.

Define $x_1$ to be the length $L(\overline{BC})$ (unknown), $L_1 = L(\overline{BD})$ (known), $x_2 = L(\overline{DE})$ (unknown), and $L_2 = L(\overline{DF})$ (known). The known quantities can be measured in units of diamonds on the side of the table. Because of the similarity of the red triangles, we have: $$
\begin{align}
\dfrac{x_1}{L_1-x_1} &= \dfrac{L(\overline{AB})}{x_2} \tag{1} \\[3mm]
\dfrac{x_2}{L_2-x_2} &= \dfrac{L_1-x_1}{L(\overline{FG})} \tag{2}
\end{align}
$$ Solving $(1)$ and $(2)$ for $x_1$ gives the location of point $C$. One can do this by solving $(1)$ for $x_2$ and then plugging in the answer every time $x_2$ occurs in $(2)$. This is not very practical while playing, so once again, there is a midpoint/parallel shift method that you can implement easily.

1. Find the midpoint $M$ between $A$, the cue ball starting position, and $G$, the desired cue ball position at contact.

2. Make a line (with your cue stick) from $M$ to $D$, the corner pocket between the two rails off which you're kicking.

3. Move your cue, keeping it parallel, over to the cue ball, and where it intersects the bottom rail is the target contact point $C$.

So there you have it. The two-rail kick.

Now, there's an important point we completely ignored, and that's the effect of spin and, related to that, the fact that the rails are not rigid, but rather have some give and will compress when a ball contacts them and potentially alter the ball's trajectory coming off.

On the two-rail kick, in practice, we want to hit the ball along the lines we calculated above, but with a bit of running English, which means topspin + a bit of spin in the direction the ball will be moving (right English in the example above). I can't find anywhere on the internet why this is the case, but I suspect that it's because when the rail compresses and then launches the cue ball back out, the "launch" makes the angle off the rail greater. Running English compensates for that angle boost and also gives the ball some speed to "run" around the table.

The amount of spin depends on how close the contact point is to the corner pocket (point $D$ in the diagram) and also the speed with which the cue ball is hit.

For the simpler one-rail shots above, especially when the distances involved are relatively small and the cue ball isn't hit too hard (and thus the rail does not compress much), there is a bit of margin for error, and no fancy spin is necessary, but it is important for the two-rail kick where the ball must travel a long distance and with enough speed to go that distance.

I defer to better players to add to the spin point in the comments section or let me know if anything above is off.

Thanks for reading.

Prerequisites: Vectors

In this two-part post, we'll go through some of the basic geometry of pool/billiards.

In Part 2, we'll derive simple methods to make one-rail bank and kick shots (to be defined below). We'll also go briefly into an example of a two-rail kick, with which it's extremely difficult to actually pocket the target ball, but at least you can work your way out of some sticky situations and avoid giving your opponent ball-in-hand.

This analysis also works for mini-golf on flat surfaces, by the way.

How to pocket a ball

This section involves a bit of physics, which I'll explain for those who don't know it already, but you may need to quickly read up on vectors here before proceeding.

Suppose we have the following set-up:
The white ball is the cue ball, and we want to hit it into the 2 ball (the blue one, also known as the object ball) to pocket the latter in the side pocket on the top of the image.

In order to accomplish this, we need the cue ball, upon contact with the 2, to impart a force upon the latter which makes it move in the direction of the pocket. The way to make the force be in that direction is to hit such that the point of contact of the two balls lies along the line between the center of the pocket (where we want the object ball to go), and the center of the object ball as in the next diagram:
It's a subtle difference, but please note that you are aiming for the point of contact, and not the center of the cue ball, to lie along the yellow line upon contact with the 2. The translucent cue ball in the above diagram shows the desired cue ball position upon contact.

If you get this right, and hit the cue ball at center with a reasonable speed, then the force imparted on the 2 will be along the yellow line, and thus it will roll along the yellow line and into the pocket. This is Newton's second law at work, which states that if the mass (i.e. how many kilograms) of the 2 ball is $m$, and the force the cue ball imparts on the 2 is ${\bf F}$ (note that this is a vector quantity, which is why it has a direction, while the mass is a scalar), then ${\bf F} = m {\bf a}$, i.e. the 2 will gain an acceleration ${\bf a}$ due to the force ${\bf F}$. The units of the acceleration are meters per second squared, and thus the units of the force are killograms*meters per second squared, also called Newtons after the same Isaac Newton we were just talking about.

Acceleration is the change, both of magnitude and direction, in velocity per unit time (thus change over one second, in how many meters per second the ball is traveling at that moment). Velocity is just the vector quantity whose magnitude is the speed (in units of meters per second) and whose direction is the direction of motion of the ball. These quantities can all vary over time, as can the force. The ball's mass $m$ is a scalar quantity that is constant over time and is a measure of how much matter is contained in the ball. The heavier the ball, the more force it takes to accelerate the ball by an equivalent amount. That's what the magnitude part of the vector equation ${\bf F} = m {\bf a}$ tells us. The direction part tells us that the acceleration is in the same direction as the force.

Make sense? Ok good- if there are questions on that, they can go in the comments section or maybe I can do a separate post, but my point was that since the cue ball is round and thus contacts the (also round) 2 at exactly one point, the cue ball must impart a force on the 2 i the direction of the yellow line in the diagram above, and thus the 2 will accelerate along that line after the contact. Since no forces act on the ball that would cause it to deviate off of that line after the contact, it will continue along that line and thus into the side pocket.

Where does the cue ball go after the contact?

That's an important question, and good players need to take this into account when planning a series of shots.

As it turns out, the cue ball bounces off perpendicular to the yellow line as in the next diagram:

To see why this is the case, we need to use conservation of momentum. What does this mean? Well, momentum is the vector quantity $m{\bf v}$ where $m$ and ${\bf v}$ are mass and velocity as above. To say that momentum is conserved means that the momentum vector of a system of objects (for a system of multiple objects, this would be the vector sum of the individual momenta) remains constant in the absence of a net external force. In our system of two balls, the force between the balls would not qualify as external. Gravity would, but it is counteracted by the force of the table pushing back up on the balls, which causes them to not fall to the ground. Thus, ignoring friction, energy loss due to the sound of the balls' hitting, etc., the momentum of the system of the two balls is the same right before and right after the collision.

In the diagram above, we have labeled the velocities, and let's assume the cue and 2 have the same mass $m$. Momentum is conserved before and after the collision, which means: $$m{\bf v}_0 = m{\bf v}_1 + m{\bf v}_2
$$
Note that the 2 ball had no velocity initially, so the left-hand side of the equation has only the cue ball's momentum. The $m$'s cancel out to give the vector equation $${\bf v}_0 = {\bf v}_1 + {\bf v}_2 $$ which actually comprises 2 algebraic equations, one in the $x$-component and one in the $y$-component:
$$
\begin{align}
v_{0x} &= v_{1x} + v_{2x} \tag{1}\\[2mm]
v_{0y} &= v_{1y} + v_{2y} \tag{2}
\end{align}
 $$Now, we can use $(1)$ and $(2)$ to obtain: $$
\begin{align}
\| {\bf v}_0 \|^2 &= v_{0x}^2 + v_{0y}^2 \\[2mm]
&= (v_{1x} + v_{2x})^2 + (v_{1y} + v_{2y})^2 \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2v_{1x}v_{2x} + 2v_{1y}v_{2y} \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2({\bf v}_1 \cdot {\bf v}_2) \tag{3}
\end{align}
$$ We also know that the energy of the system is conserved. The energy of an object of mass $m$ and speed $v$ is $\frac{1}{2}mv^2$. Technically, this is only the kinetic energy (energy due to motion of a massive particle), but there is no potential energy in this system (e.g. an object high up about to fall and gain speed, and thus kinetic energy, would have potential energy).

Conservation of energy tells us that $$
\begin{align}
&\frac{1}{2} m \| {\bf v}_0 \|^2 = \frac{1}{2} m \| {\bf v}_1 \|^2 + \frac{1}{2} m \| {\bf v}_2 \|^2 \\[2mm]
\Longrightarrow \ &\| {\bf v}_0 \|^2 = \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 \tag{4}
\end{align}
$$ Subtracting equation $(4)$ from equation $(3)$ shows that ${\bf v}_1 \cdot {\bf v}_2 = 0$, i.e. ${\bf v}_1$ and ${\bf v}_2$ are perpendicular. This means that the cue ball indeed bounces off at a right angle to the direction of the 2 after contact.

In part 2 of this post, we'll explore bank and kick shots...