A simple guessing game

Question

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?

Answer 1

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).

Answer 2

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%