6 ms·

I find this type of statistical trick (to handle people lying) to be extraordinarily cool, despite (or because of) how trivial it is. An especially elegant ver

• aprescott 15y ago
  Just to make this technique a bit clearer, since "subtract 50 and double" was a bit vague to me: you ask 100 people the question about illegal activity, and assume they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are due to following the protocol and can just be ignored. The remaining yes/no answers are from the tails results and that's the data you use to get a final answer. As an illegal opiate producer in Afghanistan who answers "yes", you have plausible deniability by just saying "I got heads." The fairness of the coin toss means the researcher asking the question doesn't need to know who got which coin result so it can be kept secret.
  • SpikeGronim 15y ago
    This is a cool concept that is formalized in the "Dining Cryptographers" paper: http://en.wikipedia.org/wiki/Dining_cryptographers_problem http://en.wikipedia.org/wiki/Dining_cryptographers_problem . You can use this basic idea to create a completely anonymous broadcast channel.
  • noja 15y ago
    Isn't the very key to this that the researcher doesn't see the coin result?
    • joeyo 15y ago
      That's correct. The researcher doesn't know the outcome of any particular coin toss but knows the outcome, in expectation, for a large number of coin tosses.
    • Terretta 15y ago
      The explanation was missing a crucial point: http://news.ycombinator.com/item?id=3810854 http://news.ycombinator.com/item?id=3810854
  • grabastic 15y ago
    Thanks for the explanation... I didnt quite get the trick as it was described in the parent.
  • tagawa 15y ago
    Thanks for the further explanation. I love it when HN throws up gems like this.
  • Terretta 15y ago
    You explained the subtract 50, but not really the and double. Revised: "You ask 100 people the question about illegal activity, and explain they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are yes due to the coin being heads, regardless of whether true yes or false positive, so subtract those yesses out. The remaining yes answers are from the tails results and are not false positives. Because heads/tails is 50% chance, half of your true yesses were on tails, and half on heads. To get back the "hidden" half of yesses you tossed out with the 50 heads results, you double the yesses that came up with tails. That's the data you use to get a final answer."
    • aprescott 15y ago
      I figured it would be obvious enough from what I outlined that the yes/no answers from the tails results gives you a proportion of "yes" answers, such as, say, 20/50, which is the proportion you want. The doubling is just 20/50 = 20*2/100. But I can appreciate that maybe someone else doesn't quite see it! :)
• ngkabra 15y ago
  This description is a bit confusing, so I'll assume that the protocol was this: 100 people are asked a possibly self-incriminating question - "Are you indulging in bad activity X?" They are expected to toss a coin. If the coin said tails, they are expected to give a truthful answer. If the coin said heads, they are expected to say "Yes." Now, no single person needs to worry about self-incrimination, since they can always claim that their "Yes" answer was the result of a "heads" on the coin toss. But still, you can get an estimate of the percentage of bad activity X going on, by subtracting 50 from the number of "Yes" answers and doubling. (This is assuming of course that the subjects believe your claim that there is no way for individuals to self-incriminate - which is certainly not a given, IMO.)
  • ams6110 15y ago
    Yeah, I think you still have to assume your "yes" count is going to be somewhat low because some number of subjects will not trust you regardless of the coin-flip cover.
• waterhouse 15y ago
  In middle school, some of my friends and I discussed systems for transmitting information about crushes. Wouldn't it be nice if some trusted person knew everything, and could tell you whether your crush liked you? But then we faced a certain use case. One of my friends liked a girl; if she liked him back, obviously he would like to know that; but, he said, if she didn't like him back, then he didn't want to know that, and would prefer to keep hope alive. So, we thought of this: Have some trusted person learn her preferences, and then flip a coin: if heads, then tell him if she likes him (and say nothing otherwise), and if tails, say nothing either way. This seemed to serve pretty well. [This was all hypothetical, of course.] I think this is a good koan--something to provoke further thought. For example: 1. This is sort of how a scientific investigation may go. Suppose you have some theory, and some test that only yields results sometimes: 50% of the time, the test will yield result A, but 50% of the time, it will work properly, and in that case, if your theory is right, then the test will yield result A, and if your theory is wrong, then the test will yield result B. (Example: "There are no animals in this area", and imagine that they'll try to avoid being caught and that you can conduct an exhaustive search of only half of some area at once. Or: "Bob isn't holding a key in his hands", and he'll only let you look at one hand at a time and can switch from hand to hand between searches.) Repeated testing will let you approach certainty about your theory (but never really reach it). 2. One could talk about Bayesian probability and priors. Especially if one varies the coin's heads/tails probability. 3. I think this sort of thing is an actual trope in human interactions. Some people give "hints" of various sorts; to hint proposition P might be defined as "to decide to do some action X such that, if not-P, then there's a small probability that a generic human in your position would do X, but if P, then there's a high probability that a generic human in your position would do X". Other people (well, probably the same people) may perform tests, to put some other person in a position where he might do X or something else, and if P were true, he would do X with high probability, but if not-P, then he would do X with low probability. And people who resent such "tests" may deliberately randomize (or genericize) their behavior. Consider this: Imagine that someone has asked me a question to which, if P, then my answer is rather embarrassing, and if not-P, then my answer is not embarrassing; suppose lying is not an option. Suppose I am a naive person. Then, if not-P, I will simply give the non-embarrassing answer, and if P, then I will refuse to answer or something. Now, if everyone knows I am naive, and P is true, then refusing to answer is futile; everyone can see that and deduce P anyway. Considering the above, I might decide to be a defensive person. I will recognize questions like that, and at least some of the time, I will simply refuse to answer even though the answer is non-embarrassing. It seems people do exactly this: refusing to answer "personal questions", as they are called, seems to be relatively common behavior. Even on the scale of just you and someone else, you can establish yourself as a defensive person by refusing to answer a personal question when the answer is innocuous, and maybe revealing the answer through some other means or at another time (be a bit careful: e.g. if you refuse to answer, he pressures you to answer, and you say the innocuous answer, then it would still seem to make sense next time you are pressured and still refuse to answer to deduce the embarrassing answer); then, the next time you refuse to answer a personal question, you have demonstrated that this doesn't necessarily imply that the answer is embarrassing. It seems to me polite to act as though someone has won his status as "defensive" without making him work for it, and rude to do the opposite. Or to make it irrelevant. "May I ask <personal question>" makes it easy for the person to say "No" (much more so than just asking the question), which establishes that "no answer" might easily happen even if the answer is innocuous. (I also take the parallel approach that it shouldn't be embarrassing to tell me anything. I think embarrassment is the anticipated feeling that someone might tease you/put you down for something, and so if telling me something won't lead to that happening, then you needn't be embarrassed to tell me. Then my task is merely to make that true.) Consider also encryption. Suppose people are naive. Then they won't encrypt anything (and do other things to make their information inaccessible to others) unless they have "something to hide". Then goddamn authorities can say "This person is hiding his stuff, so he is probably guilty, and that's all the evidence we need to justify using forceful means to make him reveal his secrets", and there is little defense against this. (In some situations, you may have an obviously "legitimate" reason to hide things, like hiding your company's information from your competitors. But there are other situations, like if the government comes and demands that information (ignore the possibility that they'll leak anything--I imagine the government will claim that's ridiculous, and I imagine most people would buy that), in which those reasons don't apply.) Meanwhile, if people are defensive about encrypting and hiding their stuff, then statements like "If you had nothing to hide, then you wouldn't be hiding anything" are obviously false. Imagine trying to make that accusation of Bruce Schneier or Colin Percival. Now if only people like that were extremely common, and considered the norm. (Oh, another example is the "Don't talk to the police" crowd.) If nothing else, I consider it rude to demand potentially embarrassing or incriminating information from someone who isn't willing to give it up, and use their response to get that information anyway; and I'd rather rude people not win out relative to non-rude people.
• ismarc 15y ago
  Similar methods are widespread in interrogation tactics as well. With enough lies, you can determine the truth (eliminate all contradictory statements and what remains is either the truth or an amazingly executed piece of misinformation). Along the same lines, in SERE training, you're instructed to not answer any questions, and if you can't hold out from answering anymore, just tell the truth because lying helps as much as telling the truth.
• gwern 15y ago
  Think it's called "Bayesian truth serum" usually: http://www.sciencemag.org/content/306/5695/462.abstract http://www.sciencemag.org/content/306/5695/462.abstract