4
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Great answer and analysis. $\endgroup$ Feb 2, 2022 at 21:43
  • $\begingroup$ 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? $\endgroup$
    – justhalf
    Feb 3, 2022 at 9:16
  • 2
    $\begingroup$ @justhalf That's why I asked on MSE. There has to be a strong dependence on the number of possibilities (10 here), though. $\endgroup$ Feb 3, 2022 at 11:55
2
$\begingroup$

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)

enter image description here


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%

$\endgroup$
4
  • $\begingroup$ Interesting. How does this compare to the other answer? $\endgroup$ Feb 3, 2022 at 1:47
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 3, 2022 at 4:39
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 3, 2022 at 4:41
  • 1
    $\begingroup$ @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! $\endgroup$ Feb 3, 2022 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.