# A simple guessing game

You and your friend play a simple guessing game. Your friend thinks of a secret whole number between 1 and 10, inclusive. If you ask your friend what the number is, the following happens:

• With 80% probability he will tell you a number chosen uniformly at random between 1 and 10, inclusive.
• Otherwise he will tell you his secret number.

You can repeat the question as many times as you want. How can you find the secret number with a high degree of confidence (greater than 99%) and what is the least number of questions needed to achieve that?

You are told the secret number with probability $$\frac15+\frac45\cdot\frac1{10}=\frac7{25}$$ and some other specific number with probability $$\frac45\cdot\frac1{10}=\frac2{25}$$. The Bayesian/maximum likelihood approach to the problem thus goes like this:
1. Initialise $$10$$ probabilities $$p_1=\dots=p_{10}=\frac1{10}$$.
2. Make queries. If your query results in $$c$$, multiply $$p_c$$ by $$7$$ and all other $$p_i$$ by $$2$$ (or just $$p_c$$ by $$3.5$$), then normalise to make $$\sum_ip_i=1$$.
3. If at any point one of the $$p_i$$ exceeds $$0.99$$, you are that confident that $$i$$ is the secret number and may stop.

The above is a Las Vegas algorithm; you always have the required confidence at the end, but your number of trials may vary. My simulation of around 4 million games shows a mean of about $$35.47$$ and a median of $$32$$ queries needed. The frequentist approach to the problem is to merely ask the question $$75$$ times and take the most common value. This is a Monte Carlo algorithm and gives the secret number more than 99% of the time (this was also verified by bootstrapping).

• Great answer and analysis. Feb 2, 2022 at 21:43
• I'm quite surprised about the spike in your chart. So is 4 million games not big enough to make a smooth graph, or is there really something in that spike? Feb 3, 2022 at 9:16
• @justhalf That's why I asked on MSE. There has to be a strong dependence on the number of possibilities (10 here), though. Feb 3, 2022 at 11:55

This is a partial answer to the problem.

Let $$X=(X_n:n\in\mathbb{Z}_+)$$ be a sequence of i.i.d. numbers uniformly distribute on $$\{1,\ldots, 10\}$$. the number that one of the friend chooses. Let $$(\varepsilon_n:n\in\mathbb{N})$$ be a sequence of i.i.d Bernoulli numbers with parameter $$p=1/5$$ and independent form $$X$$.

The outcome the game $$n$$ in the problem you are referring to is $$Y_n=\varepsilon_n X_0 + (1-\varepsilon_n)X_n$$

$$E[\frac1n\sum^n_{k=1}Y_k|X_0]=\frac15X_0+\frac{22}5$$

An estimator for $$X_0$$ is $$\widehat{X}_{0,n}=\frac{5}{n}\sum^n_{k=1}Y_k - 22$$ or $$\lfloor \hat{X}_{0,n}+.5\rfloor$$.

Here is an R implementation of this game:

    ################

x0 <- sample(1:10,1)  # friend's choice

myprediction <- function(ngames,x0){
epsilon <- 1*(runif(ngames) <= .2)  # games at which x0 is actually reveil purposely
xgame <- sample(1:10, ngames, replace = T)
y <- epsilon*x0 + (1-epsilon)*xgame  # number revieal by friend
floor(5*mean(y)-22+.5)
}

myprediction <- Vectorize(myprediction, vectorize.args = "ngames")

## example
c(x0,myprediction(ngames =100, x0=x0))

ypred <- myprediction(1:5000,x0)

## estimate number of times prediction was correct

gamesize <- seq(10,5000, by = 15)
freq <- vector(mode = 'numeric', length = length(gamesize))
for(n in 1:length(gamesize)){
games <- sapply(1:10000,function(x){myprediction(gamesize[n],x0)})
freq[n] <- length(which(games == x0))/ length(games)
}

plot(gamesize,freq, type = 'l')
abline(h=.9, col = 'red', lwd=3, lty=2)


Here is a plot of the frequency of success in 10000 repetitions of games of different sizes (10 to 5000 increments by 15 games) Edit: The simulations above show that around playing a game of size larger than 2000, the probability of success (predictor matching the friend's secret number) is above 90%

• Interesting. How does this compare to the other answer? Feb 3, 2022 at 1:47
• @DmitryKamenetsky Using the Hoeffding bound I get that $859$ trials are needed to get the probability of the estimated secret value being farther than $0.5$ from its expected value below $0.01$. This answer is not exploiting the fact that there are only $10$ possible underlying distributions. Feb 3, 2022 at 4:39
• @DmitryKamenetsky: I made some edits to my answer. I simulated games of sizes 10 to 5000 increasing the number of games by 15. Each game of a given size is simulated 10000 times. My estimates suggest that after 2000 the probability of the predictor given revealing the secret number is above 90%. Playing a game of size 400 will give the secrete number with probability 50%. I will study Parcly's method to see the probability of success of his/her scheme in terms of the size of the game. Feb 3, 2022 at 4:41
• @DmitryKamenetsky: after further analysis I can say that I am getting more appreciation for Bayesian methods. My point of view in the estimator I proposed was all based on law of large numbers and this, due to the slow convergence in, for example the Central limit theorem $(O(1/sqrt{n})$ large sampling (long games) are require. Parcly's methods which basically updates posterior distribution according to the observations seems to be very accurate (by design) and most importantly, requires a relatively short number of games. It was a fun puzzle! Feb 3, 2022 at 22:51