mathematics

ticket risk in Ticket to Ride

Wed, 2016-08-31 19:47

I've been playing a lot of Ticket to Ride recently. Jenni and I play with the 1910 cards. There are 69 cards total (so maybe this is the "Mega" game?). Each card has a point value. A player may choose to draw three cards: what is the expected minimum value of the cards drawn? This value can be interpreted as an upper bound on the "risk" associated with drawing tickets (cards): the worst case scenario when drawing is that you lose this minimum value worth of points.

The values on the cards are distributed like this:
A=[0,1,0,3,3,5,7,7,4,6,7,4,5,2,1,2,3,0,4,3,2]
That is, there is 1 card worth 2 points, 0 cards worth 3 points, 3 cards worth 4 points, etc., up to a maximum of 21 points (on two cards).
A little PARI/GP code:
B=vector(21);\
B[1]=0;for(i=2,21,B[i]=A[i]+B[i-1]);\
C=vector(21);\
for(i=2,21,if(A[i]>0,\
C[i]=A[i]*binomial(69-B[i],2)+binomial(A[i],2)*(69-B[i])+binomial(A[i],3)));\
print(C);\

Yields the array C:
[0, 2278, 0, 6436, 5860, 8560, 9660, 7259, 3202, 3683, 2856, 1060, 860, 225, 91, 144, 136, 0, 74, 10, 0]

Out of the "69 choose 3" possible hands, 2278 have a minimum card value of 2, 6436 have a minimum value of 4, etc.

From this we can calculate the expected value:
sum(i=1,21,i*C[i]*1.)/binomial(69,3) = 7.0304424170706...

What about the median?
Here's the array of partial sums of C:
[0, 2278, 2278, 8714, 14574, 23134, 32794, 40053, 43255, 46938, 49794, 50854, 51714, 51939, 52030, 52174, 52310, 52310, 52384, 52394, 52394]

So about 44% of the time the minimum will be 6 or less, and 62.6% of the time it will be 7 or less.
In fact, 89.6% of the time, the minimum will be 10 or less.

That's nice to know.

By the way, the average ticket value is 10.927... .

curves from lines

Thu, 2015-10-15 10:31

An old-school image created with modern tools. Click to embiggen on Flickr.

curves from lines (3)

Tour de France and multidimensional scaling

Thu, 2015-07-30 19:09

I've had the following idea for a long time and finally took the time to try it out.

In the Tour de France, every rider receives a rank (i.e., placing) on each stage. In the 2015 tour, there were 20 stages (exclusing the team time trial which works differently). Each rider who finishes the tour (i.e., finish all stages) has then a 20-dimensional vector of their placings. For example, Rohan Dennis had the vector

<1,88,122,88,107,156,183,142,139,101,77,106,101,108,106,98,85,65,80,151>.

We can thus embed the set of finishing riders into a 20-dimensional space. What is this embedded set "like"?
Twenty dimensions is too many to hope to have an easy way to, say, visualize, the set.
Fortunately, there is an amusing technique called multidimensional scaling (mds). The idea of mds is to take a high dimensional data set and model it in a space of lower dimension. The key idea is to maintain, as much as possible, some measure of proximity: if two points are "close" in the original space, we want them to be "close" in the lower dimensional space. How we measure close is up to us, of course.

I applied this technique to the rider data and made a 2-d model for easy viewing. The goodness of fit (GOF) is not great, about 0.548, but the visualization is nice (click on it to go to Flickr for a somewhat larger version, or see this pdf):

2015 Tour de France MDS

Some things we can see in this plot:

  • The top GC riders and climbers all cluster in the upper right, with Froome (the winner) in the most extreme position.
  • In the bottom left we find all the sprinters (in particular the cluster of Greipel, Kristoff, Cavendish, Degenkolb, Coquard, and Boasson Hagen).
  • I don't know what to say about the cluster of nine riders above the main sprinter cluster.
  • Most noticeably, we see Peter Sagan on his own at the bottom, right of center. Sagan achieved high placings on many stages that pure sprinters could not, and fared very well on the sprint stages, too. On the other hand, he didn't get high places on some mountain stages.

I pulled the stage data off the web and processed the files into a csv file with names and placings with a bit of Perl. I then processed the csv file with R like this:

ranks <- read.csv(file.choose(new=FALSE),head=FALSE,sep=",")
ranksplusnames <- read.csv(file.choose(new=FALSE),head=TRUE,sep=",")
myfun <- function(x) {return(x^0.3)}
ll <- cmdscale(dist((apply(ranks,MARGIN=c(1,2),myfun)),method="minkowski",p=2),k=2,eig=FALSE)
textplot(ll[,1],ll[,2],gsub("(^[^\\s]+\\s{1})","",ranksplusnames$rider,perl=TRUE),xlim=c(-4,7),cex=0.6)

I actually used two different csv files, one with nothing but ranks, and the other with names and headers. I'm sure you could get by with one.

I defined myfun to "adjust" the rankings. This is based on the idea that nobody really cares whether they finish 120 versus 140, but care a lot whether than finish 3rd versus 23rd. I thought applying a "concave down" function to the rankings should make comparisons more "realistic" (other functions would give similar results, including, say 1/x, as it groups larger rankings closer together). However, I was surprised to find that this did not seem to make a great difference. Hmmm.

The cmdscale command does the real work. The first thing is to calculate a matrix of distances between each rider (using the dist function). There are lots of options on calculating the distance; here, I used Minkowksi distance with p=2 (i.e., plain-old-euclidean distance). This distances array gets handed to cmdscale which finds a set of points in the specified dimensional space (k=2) that best captures this distance information. With eig=FALSE, you just get a set of points; setting this to true gives more information.

Then this set of points is given to textplot (which is part of the wordcloud package) which plots the points using the names of the riders. Textplot makes sure that the names do not overlap, which is useful here, since the upper left is so crowded. There is a bit of grep in there to extract just the last name of each rider, which also helps with the crowding.

eigenvideo 1

Sun, 2013-01-20 23:04

A video of eigenvalues of a 200x200 real matrix with entries defined by functions of time.

Click through for much bigger on Vimeo.

eigenvideo 1 from Matthew Conroy on Vimeo.

more dice problems!

Fri, 2012-12-21 00:54

A new version of my dice collection. Problem 10 is new.

animated eigenvalues

Fri, 2012-08-31 13:51

I made a similar animation over ten years ago, and have been looking for a nice way to do this since. I finally worked out how to add a java library to Processing (processing.org) which did the trick, making it really easy to experiment with this.

The idea is to take a square matrix and plot its eigenvalues (as points in the complex plane). Then vary one entry of the matrix (in this case, back and forth over a range of values), and plot the eigenvalues as this entry changes. Some of the results are quite visually interesting.

The ij-th entry of the matrix is M[i][j]=sin(cos(j)+j*cos(i+cos(2*j))).

animated eigenvalues 1

a little bit of tikz/pgf

Sat, 2012-05-26 15:32

I've been working with tikz/pgf, a system for creating figures in LaTeX. I've been encouraged to do this partly as a result of my frustration with Inkscape, which is excellent in places, but crashes often and frequently fails to be able to do exactly the thing I need.

Today, I figured out the use of variables in tikz. Here is an example:

\documentclass[12pt]{report}
\usepackage{tikz}
\begin{document}

%%% this is the tikz code
\begin{tikzpicture}[auto,scale=1]
\def\n{10}; % the number of circles
\def\wid{5}; % the width of the drawing
\def\r{2.0}; % radius of each circle
\foreach \j in {1,2,...,\n} {
\foreach \i in {1,2,...,\n} {
\pgfmathparse{1.0*\i/(\n)*360}\let\ang\pgfmathresult;
\pgfmathparse{ 0.5*\wid*(\j)/(\n)*cos(\ang) }\let\xx\pgfmathresult;
\pgfmathparse{ 0.5*\wid*(\j)/(\n)*sin(\ang) }\let\yy\pgfmathresult;
\draw (\xx,\yy) circle (\r);
}
}

\end{tikzpicture}
%%% end of tikz code

\end{document}

This example shows the use of variables, nested for loops, and mathematical calculations.

Here is the output:

the game of threes

Thu, 2011-12-01 15:46

I have added to my dice problems collection pdf. I added a solution to the question "What is the expected value of a single player in the game of Threes?" assuming the player is playing optimally.

You can read about Threes at Wikipedia.

My collection is here. The Threes solution starts on page 31.

envelopes

Sat, 2011-11-26 17:38

I've been playing around with envelopes lately. I've got a pdf of examples I'm adding to. Here is one nice one of shifted (both x and y) sine curves.

an envelope

I don't know yet what the bounding curve is...

falling ladder applet

Mon, 2011-11-21 22:13

I was thinking about the motion of stationary points on a falling ladder, and then thought: what if the point moves along the ladder (at a constant speed) as the ladder falls? So I wrote this applet.