Smaller or greater? – episode II

[This article was first published on infoRύχος » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

In a previous post I introduced the following game:

Suppose you play the following game: Someone holds a set of cards with the numbers {1,2,…,N} in random order, opens up the first card and asks if the next card is greater or smaller. Every time you predict correctly, you get one point, while every wrong prediction gives a point to the opponent – the card holder. The first card gives no points. What is the best strategy?

I still don’t seem to possess a theoretical solution to the problem, neither the time to look for one, but I will try to use R as a helping hand. So I will create a tiny script that calculates the win rate for a given problem dimension. First, the package gtools need to be installed. In Debian it exists in the repositories, but in any case you can install it within the program.

Let’s go to the coding now. Note that this little script hasn’t been optimised in terms of neither elegance nor efficiency. Also, care should be taken regarding the dimension, since the number of permutations grows rapidly. The function “permutations” from the package gtools is used to create a matrix with all permutations as rows. Then, for each row a serial check is performed and the decision is being based on probabilities, as explained in episode I. Finally, the win rate is printed out.

library(gtools)    # Load the gtools package
d <- 8    # Specify the number of cards
pm <- permutations(d,d)    # Find number of permutations
m <- nrow(permutations(d,d))    # Create the permutation matrix
pv <- rep(0,m)
for (j in 1:m) {
	v <- pm[j, ]
	n <- pv[j]
	for (k in 2:d) {
	a <- sum(v[-(1:(k-1))]>v[k-1])
	b <- sum(v[-(1:(k-1))]<v[k-1])
	pv[j] <- pv[j] +
		(a <= b)*(v[k]<v[k-1]) +
		(a >  b)*(v[k]>v[k-1])

Let’s take a look of the win rate versus the number of cards:

2      1.0
3      0.9166667
4      0.8888889
5      0.8666667
6      0.8533333
7      0.8420635
8      0.8340136
9      0.8269841
10    0.8215168

For dimension greater than 10 the script takes too long to finish. So, the next step will be a theoretical investigation. I wonder if, given a code optimisation, it would be possible to solve the problem with the whole set of 52 playing cards (as stated in episode I) using R. What do you think?

To leave a comment for the author, please follow the link and comment on their blog: infoRύχος » R. offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)