Saturday, December 30, 2017

If you had read my first few posts, you would've known that am an amateur Badminton player. Now I don't find either the time or the energy to play the game, but it's a game that I've always enjoyed playing. This post is about combining my interest on Badminton and my passion for math.

Most of the important details of the post are borrowed from Score probabilities for serve and rally competitions. The paper was too good in analyzing a given serve-rally competition, be it tennis or Badminton or the likes, the paper did not stick to any one particular game and finish it off in style which is exactly what we plan to do here for Badminton.

Let's just list the rules to make sure we are all on the same page.

• A rally cannot end in a draw
• The winner of the current rally wins a point and serves next irrespective of who served the current rally
• The first player to reach 21 points wins the game unless the score was ever tied at 20 apiece
• If the score ever reached 20-20, then the first player to lead by two point or the reach 30 points wins the game

Let me stick to the notations used in the paper quoted above and call the two players $A$ and $B$. WLOG, we always consider $A$ to serve first. The game will be analyzed from $A$'s perspective and hence let $p_a$ denote the probability that $A$ wins the rally when $A$ serves and $p_b$ denote the probability that $A$ wins the rally when $B$ serves.

Then $q_x=1-p_x,\text{ }x=a,b$ be the corresponding winning probabilities for $B$.

Given these probabilities, we intend to find the probability of $A$ winning the game. But before we begin, assuming both the players are equally skilled, do you think that $A$ has an advantage because he is serving first?

Let $\mathbb{P}(X),\text{ } X=A,B$ denote the probability that $X$ wins the game and $\mathbb{P}(X_{i,j}),\text{ } X=A,B$ denote the probability that game is at a stage where $A$ has $i$ points, $B$ has $j$ points and $X$ has won the last point.

The paper doesn't go on to complete by taking into account the end conditions of the game. To do that, we extend it to cover the end cases as well.

$\mathbb{P}(A_{i,j})= \begin{cases} 0,& i \leq 0\\ p_a^i, &i\leq21,j=0\\ \displaystyle p_a^iq_b^j\sum_{r=1}^i\binom{i}{r}\binom{j-1}{r-1}\left(\frac{q_a p_b}{p_a q_b}\right)^r,&i < 21, j<21\text{ (or) }i=21,j<20\\ p_a\text{ }\mathbb{P}(A_{i-1,j})+p_b\text{ }\mathbb{P}(B_{i-1,j}),&0\leq i - j \leq 2, \text{ }i\leq30,j<30 \end{cases}$

$\mathbb{P}(B_{i,j})= \begin{cases} 0,& j \leq 0\\ q_a q_b^{j-1}, &j\leq21,i=0\\ q_a q_b^{j-1}p_a^i\left[1+\displaystyle\sum_{s=1}^{j-1}\sum_{r=1}^i\binom{i}{r}\binom{s-1}{r-1}\left(\frac{q_a p_b}{p_a q_b}\right)^r\right],&j < 21, i<21\text{ (or) }j=21,i<20\\ q_a\text{ }\mathbb{P}(A_{i,j-1})+q_b\text{ }\mathbb{P}(B_{i,j-1}),&0\leq j-i \leq 2, \text{ }j\leq30,i<30 \end{cases}$

Anything that doesn't fall in these categories is $0$.

Now,

$\mathbb{P}(A)=\displaystyle\sum_{r=0}^{19} \mathbb{P}(A_{21,r})+\sum_{r=22}^{30} \mathbb{P}(A_{r,r-2})+\mathbb{P}(A_{30,29})$ and $\mathbb{P}(B)=1-\mathbb{P}(A)$

Playing with this code, we now answer the question that I asked above. According to the model, when both the players are equally skilled (both while serving and defending), it makes no difference as to who serves first. This seemed a counter-intuitive to me because assuming everything else equal, I thought the first player has the initiative.

Let's look at the question of serve-advantage with the following graphic.

The probability of $A$ winning the game is plotted in the Y-axes. The orange curve is when both players are equally adept at winning the rallies when they serve. That 'adept-ness' is in the X-axis. The upper blue curve is when $A$ has a 'slight' serve-advantage over $B$ and vice verse for the lower green curve. (The 'slight' is 1% here)

The green curve clearly shows the second player can 'pull-down' $A$'s chances of winning the game by developing a serve-advantage though at professional levels this diminishes fast.

Yet another interesting graphic is the one where the first player has the same probability of winning a rally irrespective of who served.

Again the Y-axis shows the probability of $A$ winning the game and the X-axis, his probability of winning the rally (irrespective of the serve). The graph pretty much says that once a player reached about 2/3rd chance of winning the rally, there is pretty much nothing more he has (or need) to do.

Hope you enjoyed this. Wish you all a very Happy New Year!!

Yours Aye,
Me

Wednesday, December 20, 2017

An Iterated Sum

I recently saw a very nice problem. It's a problem on Continuous distribution but I recognized it's one of those problems where the reasoning can be applied exactly to the discrete case too. So here it is.

Consider the following sum.

$T(n)=\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$

One interpretation of the above sum can be as follows: The sum counts the number of $k$-tuples of positive integers such that each integer in the tuple is less than or equal $n$ and the sum of any two consecutive elements in the tuple in less than or equal to $n$ as well.

To find this sum, let's modify the notation a bit. Let

$T_k(m)=\displaystyle\sum_{j_1=1}^{n-m}\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$

So we are solving for $T_k(0)$ given $n$. Now we take advantage of the iterative structure of the sum to write it as,

$T_k(m)=\displaystyle\sum_{j=1}^{n-m}T_{k-1}(j)$

with $T_0(m)=1$. This may be a little confusing but a moment of thought clears it up easily. Now this renders itself to the idea of generating functions. We define,

$f(z,m)=\displaystyle\sum_{j=0}^\infty T_j(m)z^j$

Let's do some algebraic manipulations in the above sum.

\begin{align} f(z,m)&=1+z\sum_{j=1}^\infty T_j(m)z^{j-1}\\ &=1+z\sum_{j=1}^\infty z^{j-1} \sum_{i=1}^{n-m}T_{j-1}(i)\\ &=1+z\sum_{i=1}^{n-m} \sum_{j=1}^\infty T_{j-1}(i)z^{j-1}\\ &=1+z\sum_{i=1}^{n-m} f(z,i)\\ \end{align}

We can infer that

$(1):$    $f(z,h+1)-f(z,h)=-z f(z,n-h)$

$(2):$    $f(z,h+2)-2f(z,h+1)+f(z,h)=-z (f(z,n-h-1)-f(z,n-h))$

$(3):$    $f(z,n)=1$

$(4):$    Using $h=0$ in $(1)$, we have $f(z,1)-f(z,0)=-z$      (using $(3)$)

Using $h=n-m-1$ in $(1)$, we have $f(z,n-m)-f(z,n-m-1)=-z f(z,m+1)$. Substituting this in $(2)$, we finally arrive at,

$f(z,m+2)-2f(z,m+1)+f(z,m)=-z^2f(z,m+1)$

This is a simple difference equation of the second order. The characteristic equation of this is,

$x^2+(z^2-2)x+1=0$ with roots $z_{+,-}=\displaystyle\frac{1}{2}(2-z^2\pm z\sqrt{z^2-4})$

Therefore, $f(z,m)=c_1 z_+^m+c_2 z_-^m$. Note that our point of interest $f(z,0)=c_1+c_2$

We use $(3)$ and $(4)$ to solve for these constants. Finally,

$T_k(0)=[z^k]f(z,0)=[z^k]\displaystyle\frac{z_+^n-z_+^{-n}+\sqrt{z^2-4}}{\frac{z}{2}(z_+^n-z_+^{-n})+\frac{\sqrt{z^2-4}}{2}(z_+^n+z_+^{-n})}$

Honestly, the entire idea so far has been adapted to the discrete case from the original source. Moreover, the given expression looks complicated. It seems we can simplify this and somehow get rid of the radical terms but I was not able to.

But I did all these because, first of all, it was fun and second, I was able to notice something very nice which would be my original contribution to this post.

Let $f_j(z)=z+\displaystyle\frac{1}{f_{j-1}(-z)}$ with $f_0(z)=1$. Then $T_k(0)=[z^k]f_n(z)$. That is,

$\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1=[z^k] \text{ }[z;-z,z,-z,\cdots,(-1)^{n-1}z,1]$

in continued fraction notation. Note that there are $n$ $z$'s on the RHS and the sign alternates with every iterate.

I really liked how an iterated sums occur on one side, a continued fraction on the other and levels on both sides $k$ and $n$ in a twisted way. Not only does this make the sum compact (also freeing it of any radicals), it also makes it easier to program. I used this idea to make a Python program for different $k$.

Yeah, my original idea was very small compared to the length of the post but it was great learning experience for me going through a problem in both continuous and discrete cases side-by-side, understanding how each steps transpires in both of them. Hope you enjoyed this.

Until then
Yours Aye
Me.