A game of seemingly mutually independent events

In summary: Yes, it is possible to have a strategy which doesn't fix the starting box for each player making it look random or pseudorandom while still giving better results than 1/16.
  • #1
SrivastavaHarsh
2
1
TL;DR Summary
A game where n (let n=4; n is always even) players try to find their number inside n boxes by opening at most n/2 boxes.
There are 4 players numbered 1 to 4. There is a room with an entrance door to one side and exit door to opposite side. Inside the room, there are 4 boxes numbered 1 to 4. Inside each box, there is a chit containing a number (with equal probability) from 1 to 4 (inclusive). No two chits can have the same number or more than one number. Players can enter the room one at a time. They can open atmost 2 boxes to find the chit with their number and then exit the room. The players who have exited the room cannot interact with the players who are yet to enter the room. After a player exits the room and before the new player enters, the room is reset to its initial condition. The player who is in the room cannot interact with any other player while inside the room. The winning condition is that all the players find the chit corresponding to their number. Players are allowed to strategize before the start of the game, but cannot change strategy mid-game. What is the probability that the players win the game (also mention the strategy)?

Case 1: The players do not strategize and open 2 boxes at random. Probability that a player finds the chit with his/her number is 1/2. Each players probability of finding the chit is independent of others players. So, Probability of winning = probability that all of the players find their chit = (1/2)^4 = 1/16. This is the lowest possible probability of winning.

Case 2: The players adopt a strategy where they first open the box having the same number as them. If they find the chit with their number inside that box, then they exit the room. Else, they open the box corresponding to the number on the chit that they found inside the first box that they opened. Probability of winning with this strategy is 5/12 which is significantly greater than 1/16 (probability in case 1). Also the probability of individual player to find the chit with his/her number remains 1/2.

In case 1, each player randomly opens boxes with a 50% chance of finding the chit. In case 2, observer sees that each player's starting points is fixed but the chits are placed randomly inside the boxes and so each player still has 50% chance of finding the chit. But unlike case 1 where each player's turn was not only random but also mutually not correlated, in case 2 each player's turn is still random but it follows the distribution of how the chits are placed in the boxes, which is same for all players, making each player's turn mutually correlated. This is the cause of dependence. So, the probability of winning the game in case 2 will depend on how the chits are being distributed (Probability of winning = 1 - Probability of distribution with cycles greater than 2. Example of a cycle greater than 2 : 1st box has 2, 2nd box has 3 and 3rd box has 1).
Can it be said that the increase in probability is due to information being circulated/stored inside the system, here via the structure of the system itself (the system stores the information about how the turns of each player is correlated to one another) which correlates the seemingly independent events? But this behaviour is possible only when the players collude within themselves about how they will interact with the system. If so then should the strategy in case 2 give better results as the number of players increases (Number of players = number of boxes = even. Number of boxes that can be opened by any player =n/2)?

What other strategies are possible for probability of winning higher than 1/16? Is it possible to have a strategy which doesn't fix the starting box for each player making is look random or pseudorandom while still giving better results than 1/16? Also, 1/16 (or 1/2^n in case of n players) seems to be the least possible probability of winning but how to prove it?
 
  • Like
Likes FactChecker
Physics news on Phys.org
  • #2
SrivastavaHarsh said:
What other strategies are possible for probability of winning higher than 1/16? Is it possible to have a strategy which doesn't fix the starting box for each player making is look random or pseudorandom while still giving better results than 1/16?
Sounds like something you could investigate.
SrivastavaHarsh said:
Also, 1/16 (or 1/2^n in case of n players) seems to be the least possible probability of winning but how to prove it?
It's definitely not the least. If all players agree to open boxes 1 and 2 then the probability of them all finding their number is 0.
 
  • Like
Likes SrivastavaHarsh and FactChecker
  • #3
SrivastavaHarsh said:
What other strategies are possible for probability of winning higher than 1/16?
Can you think of any?
It is trivially easy to find some by altering Strategy 2 slightly which means that this is not a very interesting question.

SrivastavaHarsh said:
Is it possible to have a strategy which doesn't fix the starting box for each player making is look random or pseudorandom while still giving better results than 1/16?
Why don't you try modifying Strategy 2 and see what happens?

SrivastavaHarsh said:
Also, 1/16 (or 1/2^n in case of n players) seems to be the least possible probability of winning but how to prove it?
Now that IS an interesting question but I'm afraid the proof is not easy and uses techniques which you need a few more years of study to appreciate. If you want to know more it will help to know that the problem was first posed where the players were imagined to be 100 prisoners.
 
  • #4
pbuk said:
Now that IS an interesting question but I'm afraid the proof is not easy and uses techniques which you need a few more years of study to appreciate. If you want to know more it will help to know that the problem was first posed where the players were imagined to be 100 prisoners.
The least probability across all strategies is zero.
 
  • #5
You observed that an interesting element of the second strategy is that the players' turns are correlated. Can you think of a way for them to take correlated turns that doesn't require them to use information in the room?
 
  • Like
Likes SrivastavaHarsh
  • #6
PeroK said:
The least probability across all strategies is zero.
:DD oh good catch! I saw least but thought greatest.
 
  • #7
PeroK said:
It's definitely not the least. If all players agree to open boxes 1 and 2 then the probability of them all finding their number is 0.
I feel stupid missing such obivious case. Actually I was thinking of strategies (where players will strategize optimally or atleast don't leave any box unopened) that might backfire instead or more precisely if the system can be modified to make some or all seemingly optimal strategies backfire. It is a vague thought that I struggle to put into words accurately. The idea was that players are strategizing so that they can use the information stored in the room to their advantage without any communication. We see this in case 2, where their individual turns get correlated, banking on the system's information to give them an edge over case 1 where they don't use system's information in anyway and their individual turns are uncorrelated and mutually independent. Another strategy would be if players open consecutive boxes starting from their number (player 1 opens box 1 & 2, player 2 opens box 2 & 3, ... player 4 opens box 4 & 1) where the winning probability is 1/12 (which is still better than 1/16) due to partially utilizing the information present in system. So among a series of questions that rise in my mind, one is that whether or not a negative correlation possible. Also, can any strategy give a result better than 5/12 since the strategy in case 2 seems to completely utilize the system's information i.e. the distribution of chits to its advantage. Another thing to note was that the advantage gained by utilizing system's information campared to case 1 increases when the number of players increase and the factor by which the probability of winning increases is directly proportional to the number of players or in other words, it is directly proportional to the number of turns (actions) that the system can correlate. Whereas, the system's information depends on the factorial of number of boxes(or players). It seems something but I'm not sure if it is of any significance (significance in terms of physical world or a generalized behaviour).
 
  • #8
Why don't you follow the hints in #2 to find out more about this well-studied problem?
 
  • Like
Likes PeroK

1. What is a game of seemingly mutually independent events?

A game of seemingly mutually independent events is a game where the outcome of one event does not affect the outcome of the other events. In other words, each event appears to be independent of the others.

2. Can you give an example of a game of seemingly mutually independent events?

One example of a game of seemingly mutually independent events is flipping a coin multiple times. The outcome of each coin flip does not affect the outcome of the other flips, making it appear that each flip is independent of the others.

3. Are there any real-life applications of a game of seemingly mutually independent events?

Yes, there are many real-life applications of a game of seemingly mutually independent events. For example, in sports betting, the outcome of one game does not affect the outcome of other games, making it seem like each game is independent of the others.

4. How do you determine the probability of winning in a game of seemingly mutually independent events?

The probability of winning in a game of seemingly mutually independent events can be determined by multiplying the probabilities of winning each individual event. For example, if the probability of winning each event is 1/2, then the probability of winning the entire game would be (1/2)^n, where n is the number of events.

5. Is it possible for a game of seemingly mutually independent events to have events that are not actually independent?

Yes, it is possible for a game of seemingly mutually independent events to have events that are not actually independent. This can happen if there are hidden factors that affect the outcome of the events, making them dependent on each other. It is important to carefully analyze the events and their potential dependencies before assuming they are truly independent.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
798
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
920
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
380
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
956
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
909
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
931
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
866
Back
Top