Suggest a change

These fields are all optional and need only
be supplied if you would like a direct reply.

Subject
Your email address
Your real name

You must answer this!

If you don't, my spam filtering will
ensure that I never see your email.

What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.

File: DecisionTreeForTennis

''' <link rel="alternate" type="application/rss+xml"
''' href="/rss.xml" title="RSS Feed">

********> width="25%"
|>>
''' <a title="Subscribe to my feed"
''' rel="alternate"
''' href="https://www.solipsys.co.uk/rss.xml">
''' <img style="border-width: 0px;"
''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png"
''' align="middle"
''' alt="" />Subscribe!</a>
_
''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
''' title="By: TwitterButtons.net"
''' width="212" height="69"
''' alt="@ColinTheMathmo"
''' /></a>
<<|
----
My lastest posts can be
found here:
 * ColinsBlog
----
Previous blog posts:
 * DecisionTreesInGames
 * AMatterOfConvention
 * DoYouNourishOrTarnish
 * BinarySearchReconsidered
 * TwoEqualsFour
 * TheLostPropertyOffice
 * TheForgivingUserInterface
 * SettingUpRSS
 * WithdrawingFromHackerNews
----
Additionally, some earlier writings:
 * RandomWritings.
 * ColinsBlog2010
 * ColinsBlog2009
 * ColinsBlog2008
 * ColinsBlog2007
 * ColinsBlogBefore2007
********
!! Decision Trees in Games (Part 2) - 2011/05/18

[[[>
https://www.solipsys.co.uk/new/images/DecisionTreeTennis.png
_ |>> Decision tree for tennis <<|
----
_
https://www.solipsys.co.uk/new/images/DecisionTreeDeuce.png
_ |>> Decision tree starting at Deuce <<|
]]]
In the last post we analysed a simple "First to Two" (or "Best of Three")
game of probability. More interesting, and more difficult, is something
like tennis, which adds the complication of "Deuce." In tennis, the winner
of a game is the person who not only has at least 4 points, but is also at
least 2 ahead of their opponent. When you each have 3 points the next
winner of a point doesn't win the game - they need to get two in front.

So we start drawing our tree of possibilities, then we realise it will be
too big and we collapse it into a DAG, and then we get the situation shown
at right.  I've marked each node with the score at that node and the number
of ways of getting there. In case you're wondering, the number of ways of
getting to a node is simply the sum of all the ways of getting to its
parents.  Some people find that obvious, others don't.

So we can see that "H" wins with loads of possible combinations, and we
can add them all up.  Using D for the probability of winning from Deuce
we get:

|>>
''' Prob(Win) = p4+4qp4+10q2p4+20p3q3D
<<|

But just what is the probability of winning from Deuce?  We can compute
the probability of getting to Deuce.  Now we just need to compute the
chances of winning once we're there.

Starting from being Deuce (which is 3 all), let's draw our DAG.  We could
get two heads, and then we've won, or we could get two tails, and then
we've lost.  Or we could get one of each (and there are two ways to do
that) and we get to 4 all.

And here's the clever bit.  Our chances of winning from 4 all are the
same as winning from 3 all.  We must again pull ahead by two, just as we
had to do from 3 all.  So our chances of winning from 4 all are again D.

So our chance of winning from 3:3 is the chance of getting HH, plus
twice the chance of winning from 4:4. Thus our chances of winning
from 3:3 are
''' p2+2pqD.
And that's D. So we have the equation:
''' D=p2+2pqD.

We can rearrange that, and we get
''' D-2pqD=p2,
and then
''' D(1-2pq)=p2,
and so finally we have
''' D=p2/(1-2pq).
It's worth checking what happens when p=0, p=1/2 and p=1. That lets us check our answer.

So now we get our final expression for the probability of winning a game
of tennis.  It's this:

|>>
''' P = p4+4qp4+10q2p4+20p3q3p2/(1-2pq)
<<|

It looks complex, but we can see where all the terms come from, and we've
been able to sneak up on it.  It's not that bad.

In my next post, however, we'll find that this hides within it
a rather surprising and slightly disturbing result.

----

|>>
| |>> <<<< Prev <<<< ---- DecisionTreesInGames <<| | : | |>> >>>> Next >>>> ---- AnOddityInTennis ... <<| |

----
********>
''' <a href="https://twitter.com/ColinTheMathmo">You should follow me on twitter</a>
********
''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
''' title="By: TwitterButtons.net"
''' width="212" height="69"
''' alt="@ColinTheMathmo"
''' /></a>
********<
<<|
----
!! Comments

''' <div id="disqus_thread"></div>
''' <script type="text/javascript">
''' /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
''' var disqus_shortname = 'solipsyslimited';
'''
''' // The following are highly recommended additional parameters. Remove the slashes in front to use.
''' var disqus_identifier = 'Solipsys_DecisionTreeForTennis';
''' var disqus_url = 'https://www.solipsys.co.uk/new/DecisionTreeForTennis.html?DQ';
'''
''' /* * * DON'T EDIT BELOW THIS LINE * * */
''' (function() {
''' var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
''' dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';
''' (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
''' })();
''' </script>
''' <noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
''' <a href="http://disqus.com" class="dsq-brlink">blog comments powered by Disqus</a>

********<