6
$\begingroup$

In volleyball, a point is awarded for every "rally" and a game is won by the first team to get to $N$ points, but you must win a game (sometimes called a "set") by two or more points. (If one team gets to $N$ points but the other team has $N-1$ points, play continues until one team is ahead by two.) The team that has won the last point always serves to the next point. It is well known that a high levels of play, the serving side is at a disadvantage in the sense of having a lower probability of winning that point (since the receiving side has the first opportunity to "attack").

Let us say two teams are evenly matched, and the probability of the serving side winning a given point is $p$ with $0<p<\frac12$.

It might be thought that since you need to win a game by two points, there will be an even number of points played in any sufficiently close game, and the disadvantage of having to serve first will even out. This is not the case. For example, if $N=2$ (that is, you start out even and the first team to be ahead by two points will win), the probability of the initial server winning is $$ S_{22} = \frac{1}{3-2p} $$ Here I have introduced a notation: $S_{ab}$ is the probability of the server winning if the server needs at least $a$ more points, and the non-server needs at least $b$ more points. So for example, in a game to $N=21$, if the score is $20$ serving to $19$, that position would be represented by $S_{13}$.

My question is, for $k>2$, what is $S_{kk}$?

That is, in a game to $N=k$, what is the probability that the starting server will win (and thus how much of a disadvantage is the first serve)? I would guess that this probability can be obtained in closed form, but if not, I'd like to see the asymptotic behavior of $\frac12-S_{kk}$.

Calculation of $S_{22}$:

$$S_{22} = p S_{13} + (1-p) ( (1-S_{13}) \\ S_{13} = p + (1-p) (1-S_{22} ) $$ Take the value of $S_{13}$ from the second equation and plug it into the first. Group terms to get $$ S_{22}(3p-2p^2) = p $$

$\endgroup$
1
$\begingroup$

Just computed some of the initial values (I have them up to $S_{20,20}$, but they get longer and harder to type).

$$ \begin{align}\frac12 - S_{3,3} &= \frac{(1-2p)(1 - 2p^2 + 2p^3)}{6 - 4p} \\ \frac12 - S_{4,4} &= \frac{(1-2p)(1 - 6p^2 + 16p^3 - 18p^4 + 8p^5)}{6 - 4p} \\ \frac12 - S_{5,5} &= \frac{(1-2p)(1 - 12p^2 + 52p^3 - 114p^4 + 144p^5 - 100p^6 + 30p^7)}{6 - 4p} \\ \frac12 - S_{6,6} &= \frac{(1-2p)(1 - 20p^2 + 120p^3 - 390p^4 + 808p^5 - 1100p^6 + 960 p^7 - 490p^8 + 112p^9)}{6-4p} \\ \frac12 - S_{7,7} &= \frac{(1-2p)(1 - 30p^2 + 230p^3 - 990p^4 + 2848 p^5 - 5760 p^6 + 8280 p^7 - 8330 p^8 + 5600p^9 - 2268p^{10} + 420p^{11})}{6-4p} \end{align}$$

Some observations:

  1. $S_{k,k} = \frac12$ when $p = \frac12$ by symmetry, as there is no difference between the serving and receiving team. Hence $1-2p$ appears as a factor in the numerators above.
  2. The second factor always seems to have constant term $1$ and no linear term.
  3. The coefficient of $p^2$ in this second factor of the numerator of $\frac12 - S_{k,k}$ appears to be quadratic in $k$. In fact, I would go as far as to speculate that the coefficient of $p^r$ appears to be a degree $r$ polynomial in $k$.

One possible way to approach the asymptotic question is to note that in the period where one team wins service to when they next lose service, the number of points gained is a geometric distribution with parameter $p$. The only exception is the very first stretch of serves, when the serving team does not start with a point for having won service.

Hence the number of points each team has after $r$ exchanges of service can be expressed as a sum of independent geometric random variables. Hence perhaps something like the central limit theorem could be used to analyse the asymptotics of $\frac12 - S_{k,k}$: how quickly does the disadvantage from that missing initial point dissipate for the serving team?

$\endgroup$
  • $\begingroup$ Nice. Two further observations, one of which is surprising: For very small non-server advantage, if we write $p=\frac12-\epsilon$, to second order in $\epsilon$ the first-server disadvantage as a function of $N$ is $\frac{\epsilon}{3}-\frac{2\epsilon^2}{9}$, that is, to first order the disadvantage does not change as $N$ increases!! Also, the coefficient of $p^2$ is simply $-N(N-1)$. I'm waiting for Lovsovs' next attempt, see heis comment, to mark the question as answered. $\endgroup$ – Mark Fischler Aug 27 '16 at 13:06
  • $\begingroup$ My first observation is not correct: Since $p = \frac12 - \epsilon$, the higher order terms in the polynomial do make a big difference, because of the $\frac12$, $\endgroup$ – Mark Fischler Aug 27 '16 at 20:16
  • $\begingroup$ When $p = \frac12 - \epsilon$ for very small $\epsilon$, the disadvantage, as a function of $N$ is to first order in $\epsilon$ equal to $$2\frac{(2N-3)!!}{(2N-2)!!}$$ $\endgroup$ – Mark Fischler Aug 27 '16 at 20:34
  • $\begingroup$ @MarkFischler Indeed, we sadly cannot afford to ignore the higher order terms in the polynomial. Is $p = \frac12 - \varepsilon$ the range you're most interested in? Where did you get that formula from? $\endgroup$ – Shagnik Aug 29 '16 at 15:34
1
$\begingroup$

This answer offers an crude algorithm that calculates the desired probability for any starting state, but does not arrive at a closed form solution. I don't know anything about Markov chains, so sorry if this overly complicates the matter, but it was fun to work out either way. :)


The difference in scores in the $n$th round, $C_n \equiv A_n-B_n$ is given as $$C_n=C_0+\sum_{i=1}^n a_i-\overline{a}_i$$ Here $C_0$ is the difference in score in the initial state, $a_i =\cases{1 \quad \text{if }A\text{ scores in the }i\text{th round} \\ 0 \quad \text{otherwise}}$ and $\overline{a}_i=\vert1-a_i \vert$.

Who has the serve $s_i=\cases{1 \quad \text{if }A\text{ has the serve in the }i\text{th round} \\ 0 \quad \text{otherwise}}$ is given by $$s_i=\begin{pmatrix}a_{i-1} &\overline{a}_{i-1}\end{pmatrix}\begin{pmatrix}0 & 0 \\ 1 & 1\end{pmatrix}\begin{pmatrix}s_{i-1} \\ \overline{s}_{i-1}\end{pmatrix}=\overline{a}_{i-1}.$$

In the same way, we can calculate the probability $p_i$ for a given outcome in the $i$th round as

$$p_i=\begin{pmatrix}a_{i} &\overline{a}_{i}\end{pmatrix}\begin{pmatrix}p & 1-p \\ 1-p & p\end{pmatrix}\begin{pmatrix}a_{i-1} \\ \overline{a}_{i-1}\end{pmatrix}.$$

For every route to $C_n=N$, where $A$ wins, there is a probability which is the product of the states $p_i$ for that route, which is given uniquely by the set $\{a_i\}$. Adding the probabilities for all such routes gives the probability that $A$ wins.

We can organize these routes after how long they are. The shortest is $N_0\equiv N-C_0$ long. We thus have

$$\boxed{P(A \text{ wins}\vert a_o)=\sum_{k=0}^\infty\sum_{j=1}^{J(k)}\prod_{i=1}^{N_0+k}p_{ji}(a_{ji},a_{ji-1})}$$ where $a_0 =\cases{1 \quad \text{if }A\text{ serves initially} \\ 0 \quad \text{otherwise}}$, the product is the probability for the $j$th route that has length $N_0+k$, and $J(k)$ is the number of possible ways from $C_n$ to $N$ (which is the same as from $0$ to $N_0$) that are $N_0+k$ unit steps long.

This is perhaps calculable with a computer, assuming that contributions larger than some $k$ can be ignored (the longest set ever (for $N=2$) was 87:85, in the Czechoslovak League of 1979).

$\endgroup$
  • $\begingroup$ A good start. Plus 1 for your comment about the Czech league (LOL). In those days, the scoring was different (you had to be serving to win a point) but the set went to deuce and then the serving team lost the next 171 points. Which is the same as (in modern scoring) getting to a score of $86:85$ and then the serving team winning the last point. $\endgroup$ – Mark Fischler Aug 27 '16 at 12:46
  • $\begingroup$ @MarkFischler Interesting! It was probably for the better that they changed it then! I'm still working on the problem, and I think I'm making progress - watch out for future updates for a possible closed form! :D $\endgroup$ – Bobson Dugnutt Aug 27 '16 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.