Looking for better algorithm to solve this kind of a probability/combinatorics game

Question

Lets say we have the 10 integers from 1 to 10.

We also have some players who are each given a different random number from this set.

Now players start to say information about his or her number by saying: my number is in a subset of initial 1 to 10 set. For example my number is 8,9 or 10.

We want to make assumptions about number of players who didn't say anything yet (of-course its same assumption about each silent player given initial information)

Lets say we have 5 players and the first 3 players said one by one:

1. mine is 8, 9 or 10
2. mine is 7 or 6
3. mine is 7, 6, 9 or 10

Now we need to calculate what are the odds (probability) that next player has a specific number, like what are the odds that next player has a number in 7.

Its just an example of course and information can be given in any form by each player (like 1 or 10, 1 through 10 etc)

Is this some kind of well known problem or maybe someone sees a good approach? I really want this to be performant, so bruteforcing isn't good. I am thinking it could be directly connected to Bayes theorem but not 100% sure it can be applied here.

EXAMPLE:

Simple case 2 players and 12345 numbers. First player has 4 or 5. Then for second player he has 25% to have 1, but only 12.5% to have 4 because there are 2 possible outcomes after first players says information about his hand.

1234 or 1235, we can see that 1 is (1/4 * 2) /2 =1/4 and 4 is (1/4 * 1) / 2= 1/8 This is what I call a brute force solution, compute all possible combinations and derive number probability by analyzing each of them.

UPDATE

Solution suggested by Mr.Wizard works.

Here is the code if your curious how it looks:

class Program
    {
        static void Main()
        {
            int length = 5;
            double[][] matrix = new double[length][];
            for (int i = 0; i < length; i++) {
                matrix[i] = new double[length];
            }

            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    matrix[i][j] = 1;
                }
            }

            matrix[0] = new double[] { 0, 0, 0, 1, 1 };
            matrix[1] = new double[] { 0, 0, 1, 1, 0 };
            matrix[2] = new double[] { 0, 0, 0, 0, 1 };

            DumpMatrix(matrix);
            while(true)
            {
                NormalizeColumns(matrix);
                DumpMatrix(matrix);
                NormalizeRows(matrix);
                DumpMatrix(matrix);
                Console.ReadLine();
            }
        }

        private static void NormalizeRows(double[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++)
            {
                double sum = matrix[i].Sum();
                for (int j = 0; j < matrix.Length; j++) {
                    matrix[i][j] = matrix[i][j] / sum;
                }
            }
        }

        private static void NormalizeColumns(double[][] matrix)
        {
            for (int j = 0; j < matrix.Length; j++)
            {
                double columnSum = 0;
                for (int i = 0; i < matrix.Length; i++)
                {
                    columnSum += matrix[i][j];
                }
                for (int i = 0; i < matrix.Length; i++) {
                    matrix[i][j] = matrix[i][j] / columnSum;
                }
            }
        }

        private static void DumpMatrix(double[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++) {
                for (int j = 0; j < matrix.Length; j++) {
                    Console.Write(matrix[i][j].ToString("0.#####").PadRight(8));
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

    }

Although from this example its pretty clear that its approaching final results not very fast.

Here player 3 has exactly 5, players one and two can have 4 or 5 and 3 or 4 respectively, which means that player one has 4 cause player 3 got 5 and player 2 has 3 cause player 2 got 4. But we approach 1 value for players 1 and 2 in matching column after many many iterations.

Answer 1

I may be well off the mark here, but I think that a process of repetitive normalization of each row and column will converge on the correct values.

If you start with a n*n matrix with zeros representing what cannot be, and ones representing what can, for your example:

0   0   0   1   1
1   1   1   1   1
1   1   1   1   1
1   1   1   1   1
1   1   1   1   1

Meaning, that row #1, representing player #1, can be only either 4 or 5, and nothing else is known. Then, if we normalize each row such that it sums to 1, we get:

0.  0.  0.  0.5 0.5
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2

And then, for each column:

0.      0.      0.      0.384615    0.384615
0.25    0.25    0.25    0.153846    0.153846
0.25    0.25    0.25    0.153846    0.153846
0.25    0.25    0.25    0.153846    0.153846
0.25    0.25    0.25    0.153846    0.153846

Repeat this process 15 times, and we get:

0.      0.      0.      0.5     0.5
0.25    0.25    0.25    0.125   0.125
0.25    0.25    0.25    0.125   0.125
0.25    0.25    0.25    0.125   0.125
0.25    0.25    0.25    0.125   0.125

If the original parameters are not impossible, then each row and column in the final matrix should sum to ~= 1.

I offer no proof that this is correct, but if you already have a working brute force implementation it should be easy to check for correlation of results.

Answer 2

Try constructing a graph with players on one side and numbers on the other. There is an edge between a player and a number if and only if the player could have that number based on what they've said. You want, for each edge, the probability that a uniform random perfect matching contains that edge.

Unfortunately, if this problem has an exact polynomial-time algorithm, then #P, a class which contains NP (and in fact the entire polynomial hierarchy, by Toda's theorem), is equal to P.

It is possible, in theory at least, to estimate the probability, via a complicated algorithm due to Jerrum, Sinclair, and Vigoda. I'm not sure anyone has ever implemented that algorithm.

Answer 3

Not sure about the exact calculation right now, but i think you can do it easier than with a complete tree.

In the easy example: There are 5 Numbers and you want to know the probability for B to have a 3:

• There are always 4 possible numbers because one is already taken
• In no case the 3 can be taken, so whatever A does, the 3 is always one of the 4 numbers.

From that statements we can directly say that the probability is 1/4 = 25%

For a 1 and 2 it is the same, and for 4 and 5 you have only a 50% chance of the number beeing in the pool, so it reduces to 0.25*0.5 = 0.125

---

For the bigger Example: 1 to 10, 5 players as you stated above.

Now say you want to know the possibility of a 6.

Both Players that did not say anything have the same probabilities. One said he has a 6 with 25% and One said he has a 6 with 50% Im not sure right now how exactly that is done, but you can now calculate the probability of "one of them has a 6". As one has 50% and the other 25% add to it, it should be like 60% or something. (not just add them... two times 50% is a good chance, but no sure hit).

Lets just assume it is 60% for this example. Now we have 10 Numbers, of which 3 are taken which leaves us 7 to choose from = 1/7 ~ 14%. So for any number which is available we have 14%. But now the 6 is in the pool only 40% of the time, so I think we have 0.14 * 0.4 = 0.056 which means 5.6% that we have a 6.

Whatever information you have, you can calculate the probability of the number you want to know about to be taken, and the probability of hitting exactly the one of X left and multiply them.

Answer 4

You should build a probability tree diagram.

For your example:

__
  |___ 0.5 A=4 __
  |              |___ 0.25 B=1
  |              |___ 0.25 B=2
  |              |___ 0.25 B=3
  |              |___ 0.25 B=5
  |___ 0.5 A=5 __
                 |___ 0.25 B=1
                 |___ 0.25 B=2
                 |___ 0.25 B=3
                 |___ 0.25 B=4

The tree represents statements such as p(B=1|A=4)=0.25

So

p(B=1|A=4 or A=5)= p(B=1|A=4)+p(B=1|A=5)= 0.5*0.25 + 0.5*0.25= 0.25

and

p(B=4|A=4 or A=5)= p(B=4|A=4)+p(B=4|A=5)= 0 + 0.5*0.25= 0.125

You can dynamically expend the tree at any stage of the game and calculate the probability for each assumption accordingly.

I believe that for the general case there are no shortcuts.