Min time to find an item on identical lists checked at different rates?
July 2, 2017 10:00 PM Subscribe
I have a weird question about how long it would take to find a random item included on two lists that are identical, except that the item is missing from one of the lists, and that list is hidden from me, and there are other restrictions too.
Twenty-six cards are labelled with the letters A to Z. One of the cards is removed at random and kept secret from me. The remaining cards are shuffled into a deck and handed to me face down. I need to find out which letter card was removed from the deck through a process of elimination.
I have a list of all of the letters from A to Z on a piece of paper. I can choose four letters from this list and cross them out. I then draw two letter cards from the shuffled deck and can also cross them off my list, if they haven't already been crossed out. If I cross off the letter that was removed from the deck, the removed card will be revealed to me. Letters can't be chosen again once they've been crossed out, and drawn cards are discarded.
If I don't find it on the first try, I can then choose five letters and draw two cards, then six letters and two cards, then seven letters and two cards, then eight letters and two cards. Thereafter, I can't choose more than eight letters. I can never draw more than two cards.
How many tries will it 'usually' take for me to identify which card was removed from the deck? I get that this is an imprecise question (particularly the 'usually' bit), but I've learned that others here seem to be much better at phrasing these sorts of things in a way that's useful (eg 'this is the shortest, this is the longest, 80% of the time it'll be in this range', etc), so feel free to interpret.
(Board game geeks will recognise this as a simplification of the Empire trying to find the hidden base in Star Wars: Rebellion, where the deck is the probe droid deck and the list is the map of systems, less those occupied by the Empire at the start of the game. I'm interested to know what would happen if the Empire just deployed its four starting leaders to neighbouring worlds and landed a single ground unit, then repeated this with five leaders, then six, up to the maximum of eight, eschewing all other missions or projects in order to maximise coverage of the board.)
Twenty-six cards are labelled with the letters A to Z. One of the cards is removed at random and kept secret from me. The remaining cards are shuffled into a deck and handed to me face down. I need to find out which letter card was removed from the deck through a process of elimination.
I have a list of all of the letters from A to Z on a piece of paper. I can choose four letters from this list and cross them out. I then draw two letter cards from the shuffled deck and can also cross them off my list, if they haven't already been crossed out. If I cross off the letter that was removed from the deck, the removed card will be revealed to me. Letters can't be chosen again once they've been crossed out, and drawn cards are discarded.
If I don't find it on the first try, I can then choose five letters and draw two cards, then six letters and two cards, then seven letters and two cards, then eight letters and two cards. Thereafter, I can't choose more than eight letters. I can never draw more than two cards.
How many tries will it 'usually' take for me to identify which card was removed from the deck? I get that this is an imprecise question (particularly the 'usually' bit), but I've learned that others here seem to be much better at phrasing these sorts of things in a way that's useful (eg 'this is the shortest, this is the longest, 80% of the time it'll be in this range', etc), so feel free to interpret.
(Board game geeks will recognise this as a simplification of the Empire trying to find the hidden base in Star Wars: Rebellion, where the deck is the probe droid deck and the list is the map of systems, less those occupied by the Empire at the start of the game. I'm interested to know what would happen if the Empire just deployed its four starting leaders to neighbouring worlds and landed a single ground unit, then repeated this with five leaders, then six, up to the maximum of eight, eschewing all other missions or projects in order to maximise coverage of the board.)
(Started trying to work out the exact numbers, but I'm just confirming dilaudid's simulation at this point.) If I'm understanding correctly, you pick four guesses on your first go, which gives you a 4/26 or ~15.4% chance of hitting the target.
Then you rule out zero, one or two more possibilities with the following odds:
4/25 * 3/24 = 0.02 (Draw two cards you've already picked.)
4/25 * 21/24 = 0.14 (Draw one card you have picked and one you haven't.)
21/25 * 4/24 = 0.14 (Draw one card you haven't picked and one you have.)
21/25 * 20/24 = 0.7 (Draw two cards you haven't picked.)
Your second go only happens given the 22/26 odds your first four picks were wrong. Now you pick five guesses, which — depending on how many possibilities you've previously ruled out — gives you:
22/26 * (5/22 * 0.02 + 5/21 * 0.28 + 5/20 * 0.7) ≈ 20.8% chance of hitting the target.
The third go onwards gets a bit too confusing for me.
posted by lucidium at 12:29 PM on July 3, 2017
Then you rule out zero, one or two more possibilities with the following odds:
4/25 * 3/24 = 0.02 (Draw two cards you've already picked.)
4/25 * 21/24 = 0.14 (Draw one card you have picked and one you haven't.)
21/25 * 4/24 = 0.14 (Draw one card you haven't picked and one you have.)
21/25 * 20/24 = 0.7 (Draw two cards you haven't picked.)
Your second go only happens given the 22/26 odds your first four picks were wrong. Now you pick five guesses, which — depending on how many possibilities you've previously ruled out — gives you:
22/26 * (5/22 * 0.02 + 5/21 * 0.28 + 5/20 * 0.7) ≈ 20.8% chance of hitting the target.
The third go onwards gets a bit too confusing for me.
posted by lucidium at 12:29 PM on July 3, 2017
Best answer: Wait, I got it in the end, so just in case it's useful. Taking into account the three different ways your first and second draws might go, your odds of guessing correctly with your six guesses on your third go are:
0.02 *
(7/23 * 6/22 * 6/17 +
7/23 * 16/22 * 2 * 6/16 +
16/23 * 15/22 * 6/15)
+ 0.28 *
(8/23 * 7/22 * 6/16 +
8/23 * 15/22 * 2 * 6/15 +
15/23 * 14/22 * 6/14)
+ 0.7 *
(9/23 * 8/22 * 6/15 +
9/23 * 14/22 * 2 * 6/14 +
14/23 * 13/22 * 6/13)
= 3999/9350 or ~42.8%
The odds of actually having to take a third turn are 22/26 * (1 - (5/22 * 0.02 + 5/21 * 0.28 + 5/20 * 0.7)) or 199/312.
Multiplied by the above, that's 265267/972400 or ~27.3% chance of your third go being when you hit the target.
In terms of strategy, you can see the difference the "bonus" cards ruled out by drawing make. If you're very unlucky and only draw cards you've already crossed out, you have a 6/17 or ~35.3% chance on your third go. On the other hand, if the four cards you draw are all good (which should happen about half of the time), you have a 6/13 or ~46.2% chance.
posted by lucidium at 1:30 PM on July 3, 2017
0.02 *
(7/23 * 6/22 * 6/17 +
7/23 * 16/22 * 2 * 6/16 +
16/23 * 15/22 * 6/15)
+ 0.28 *
(8/23 * 7/22 * 6/16 +
8/23 * 15/22 * 2 * 6/15 +
15/23 * 14/22 * 6/14)
+ 0.7 *
(9/23 * 8/22 * 6/15 +
9/23 * 14/22 * 2 * 6/14 +
14/23 * 13/22 * 6/13)
= 3999/9350 or ~42.8%
The odds of actually having to take a third turn are 22/26 * (1 - (5/22 * 0.02 + 5/21 * 0.28 + 5/20 * 0.7)) or 199/312.
Multiplied by the above, that's 265267/972400 or ~27.3% chance of your third go being when you hit the target.
In terms of strategy, you can see the difference the "bonus" cards ruled out by drawing make. If you're very unlucky and only draw cards you've already crossed out, you have a 6/17 or ~35.3% chance on your third go. On the other hand, if the four cards you draw are all good (which should happen about half of the time), you have a 6/13 or ~46.2% chance.
posted by lucidium at 1:30 PM on July 3, 2017
Response by poster: Impressive. Most impressive.
I started out with lucidium's approach, but probability math is not my strength. dilaudid - I'm curious. Was this a trivial problem for you to solve? Did you have the probability math approach in your head when you smashed out that Python code, or did you just say 'eh, I'll just build each of the moving parts as described and see what happens'?
posted by obiwanwasabi at 4:45 PM on July 3, 2017
I started out with lucidium's approach, but probability math is not my strength. dilaudid - I'm curious. Was this a trivial problem for you to solve? Did you have the probability math approach in your head when you smashed out that Python code, or did you just say 'eh, I'll just build each of the moving parts as described and see what happens'?
posted by obiwanwasabi at 4:45 PM on July 3, 2017
Fairly trivial yes. You gave a good description of the problem so it was easy to translate that to code. I'm not great at actually formalizing these types of problems with equations so I'll usually just go the simulation route.
posted by dilaudid at 5:34 PM on July 3, 2017 [1 favorite]
posted by dilaudid at 5:34 PM on July 3, 2017 [1 favorite]
This thread is closed to new comments.
The full probability distribution is approximately: (1 try, 15%), (2, 21%), (3, 27%), (4, 34%), (5, 3%). (note that it's impossible to have more than 5 tries).
I assumed that if you had fewer options on your list than the number of letters you could choose you chose as many as possible.
Here is the Python code I used for this answer.
posted by dilaudid at 11:06 PM on July 2, 2017 [2 favorites]