Smaller or greater? – episode II

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])
	}
}
print(sum(pv)/((d-1)*m))

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?