2
$\begingroup$

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and lies 1/5 times. If he does not have the bag, he is honest and says he does not. How do I devise an algorithm that would calculate the minimum probability p that he always tells the truth after n attempts - where each attempt is a question asking Tom if he has a bag of candy.

I realise that this is a Monte Carlo problem with 1 sided error and that in n attempts, if all the questions asked were if he had the bag, it would be $$(\frac{4}{5})^n$$ and if independently asked when he doesnt have it, it would be 1^n but when combined, how will this work? Is it just a binomial probability summation like $$\sum_{i=1}^{n}{n \choose x}\frac{4}{5}^i*1^{n-i}$$

As a follow up, if he also starts to lie when he does not have bag, with again say 1/5 probability - says truth 4/5 of the times he is asked, how would you generate an algorithm to calculate the minimum probability of telling truth after n attempts.

$\endgroup$
2
  • $\begingroup$ What does "always tells the truth after n attempts" mean? What is an attempt? Do you mean tells the truth every time, or at least once, or what? Where did you encounter this task? Can you credit the original source where you saw this problem? Note that we require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Dec 6 '21 at 5:20
  • $\begingroup$ This was taken from a homework problem and paraphrased to look different, its not available online. N attempts here means N trials at asking the question 'do you have a bag of candy' to Tom. Each time he has a probability of telling the truth or a lie based on the condition that he has the bag(or does not) @D.W. $\endgroup$ Dec 6 '21 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.