Hacker News Reader

Comment by verteu | Hacker News Reader

Fun post. I'd be interested to know: How many consecutive Truth Booths (or: how many consecutive Match Ups) are needed to narrow down the 10! possibilities to a single one?

Discussing "events" (ie, Truth Booth or Match Up) together muddles the analysis a bit.

I agree with Medea above that a Truth Booth should give at most 1 bit of information.

View on HN

Based on my research, MUs perform better than TBs. For my simulated information theories, the MUs gained ~2 bits of information on average vs ~1.1 for TBs.

So if only MUs, we're talking around 10 events - meaning you could get enough information on MUs alone to win the game! Conversely, it would take about 20 events to do this just for TBs.

It's not super obvious from the graphs, but you can just about notice that the purple dots drop a bit lower than the pink ones!

Hope this helps

If you can only check pairings one at a time I’m not sure it’s possible to do better than greedily solving one person at a time.

Agreed. There's an argument elsewhere about how a truth booth can possibly have an expected return of more than 1 bit of information, but in reality most of the time it's going to give you way less than that.

So, for 10 pairs, 45 guesses (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) in the worst case, and roughly half that on average?

It's interesting how close 22.5 is to the 21.8 bits of entropy for 10!, and that has me wondering how often you would win if you followed this strategy with 18 truth booths followed by one match up (to maintain the same total number of queries).

Simulation suggests about 24% chance of winning with that strategy, with 100k samples. (I simplified each run to "shuffle [0..n), find index of 0".)

Reply on news.ycombinator.com