1
$\begingroup$

I am currently trying to use probability theory to help solve a programming problem involving Monte Carlo Tree Search with Information Sets and have hit a roadblock. The problem can be described as follows:

There are N piles, or groups, of cards in which the probability that each card exists in the pile is known in advance. The different piles can be of varying counts, but at all times the count of cards in each pile is known. How should the known probability adjustments be calculated when one particular card is shown to exist with 100% certainty in a particular pile? Conversely, how should the probability adjustments be calculated when a particular card is shown to NOT exist in a particular pile?

An Example for case 1:

In some card games, there exists the possibility to swap your hand with a hidden dummy hand. When such a situation occurs, the player not only knows what cards he/she has, but also what cards were traded away(which are still hidden to other players). Thus the player should be able to more precisely predict what the opponent's cards are than any other player. By ruling out more of the opponent's possible cards, the probability distribution should narrow, and each specific card's probability that still remains uncertain should be more probable than was previously believed.

An Example for case 2:

In most trick taking card games, when a player fails to follow the suit led... that player is effectively revealing that he/she does not have any cards of that suit (Hearts, Clubs, Diamonds, or Spades). The other players are, in turn, more likely to have cards of that particular suit in their hand than previously believed and a little less likely to have cards of the other three suits. Conversely, the probabilities for cards of each of the other three suits in the player's hand that didn't follow suit would go up.

Additional Info:

  1. There are no duplicate cards.
  2. The number of cards in each pile is known at all times.
  3. The problem space does not explicitly revolve around playing cards, but they make for a good representation of the problem.
  4. A given card can have been passed in a hidden manner from one pile to another, but knowledge of each such pass is guaranteed to have been given (this is not part of the problem, but added to avoid possible oversimplifications) edited: ( these passes should be assumed to be randomly generated )

I have been stumbling around with this particular problem for a while now for a programming project and do not know how best to proceed. I should mention that probability theory is not my greatest strength.

edit:

After going over this post a few times, I think a numerical sample would be appropriate.

There are 3 piles of hidden cards marked A, B, and C. A contains 2 cards, B contains 4 cards and C contains 2 cards. Together within each of these piles are cards labeled 1, 2, 3... up to 8 with no duplicates. The probability that a card Exists in each pile is as follows:

card\pile. A ---- B ---- C

card 1 ... 50% .. 25% .. 25%

card 2 ... 50% .. 25% .. 25%

card 3 ... 10% .. 65% .. 25%

card 4 ... 10% .. 65% .. 25%

card 5 ... 10% .. 65% .. 25%

card 6 ... 10% .. 65% .. 25%

card 7 ... 10% .. 65% .. 25%

card 8 ... 50% .. 25% .. 25%

count ..... 2 ....... 4 ....... 2

Then... card 5 is revealed to exist in pile A. Horizontally, the deduction 'for card 5' is easy to process, but vertically, the necessary adjustment eludes me.

  • 0
    Further to my answer, you might want to insert "marginal" before "probability distribution" in the title.2012-10-25

1 Answers 1

0

I'm not sure you understood what André was getting at in his comment, so I'll try to demonstrate it more explicitly, using some simple examples. Let's say you have three cards, $1$, $2$ and $3$, in three separate piles, $A$, $B$ and $C$, one card per pile, and you know that for each card and each pile the probability for that card to be in that pile is $1/3$. Here are two very different distributions that lead to these marginal probabilities:

a) You might have no idea how the cards are distributed, and all $6$ permutations might be equally likely.

b) You might know that the cards lie in one of the cyclical permutations of $123$, that is, $123$, $231$ or $312$.

In one case, you have probability $1/6$ for each of the six possible states, in the other, you have probability $1/3$ for three of the possible states and $0$ for the other three.

Now say we turn over the first card and it's a $1$. Under a), that eliminates $3$ of $6$ possibilities and leaves an equal chance for the remaining cards to be $23$ or $32$. Under b), it eliminates $2$ of $3$ possibilities and leaves only one, namely $23$. So under a), you still have no knowledge at all about the positions of the remaining cards, whereas under b) you now have full knowledge. This despite the fact that the marginal probabilities (which is what you listed in the table in your example) were exactly the same for both.

Now you may reply that what you had in mind is a), since in a sense it contains only the information from the marginal probabilities and nothing more, whereas in b) you have additional information about correlations between the cards, and you don't want to consider such information. That's a perfectly valid reply. The problem is just that whereas it's intuitively obvious and computationally simple in this example to find the distribution that contains the least information beyond the marginal probabilities, this is not so in the general case.

You would first have to define what least information means. You may think you've fully specified the problem by giving the marginal probabilities, but you haven't – any number of joint probability distributions would lead to these marginal probabilities, and it's far from obvious which one of these should be assumed. As the above example shows, without some assumption about the joint probability distribution the marginal probabilities don't determine how the probabilities should be updated when new information comes in.

One common way to define "least information" is through maximizing the entropy $-\sum_ip_i\log p_i$. Here $i$ runs over all possible combinations of the cards, and the $p_i$ are the probabilities of these combinations, so they give the full joint probability distribution. In the present case the entropy would have to be maximized subject to the constraints given by the marginal probabilities.

In a nice symmetric situation like the one with three cards above, this is a simple exercise and the result is what one would intuitively expect: If all marginal probabilities are the same, the joint probability distribution that maximizes the entropy is also uniform.

However, let's do a different example to see how things get complicated:

   A   B   C 1 1/8 3/8 4/8 2 2/8 4/8 2/8 3 5/8 1/8 2/8 

We have six possible states, and five linearly independent linear constraints on their probabilities:

$ \begin{align} p(123)+p(321)&=4/8\;,\\ p(132)+p(312)&=2/8\;,\\ p(132)+p(231)&=1/8\;,\\ p(123)+p(213)&=2/8\;,\\ \sum_ip_i&=1\;. \end{align} $

The solution space is

$ \frac18\pmatrix{0\\1\\2\\0\\1\\4}+p(123)\pmatrix{1\\-1\\-1\\1\\1\\-1}\;, $

so $p:=p(123)$ must lie in $[0,1/8]$ to make all probabilities non-negative. Now we can maximize the entropy with respect to $p$:

$ \begin{align} \sum_ip_i\log p_i=&p\log p+\left(\frac18-p\right)\log\left(\frac18-p\right)+\left(\frac28-p\right)\log\left(\frac28-p\right)+\\ &p\log p+\left(\frac18+p\right)\log\left(\frac18+p\right)+\left(\frac48-p\right)\log\left(\frac48-p\right)\;,\\ \frac{\mathrm d}{\mathrm dp}\sum_ip_i\log p_i=&\log p-\log\left(\frac18-p\right)-\log\left(\frac28-p\right)+\log p+\log\left(\frac18+p\right)-\log\left(\frac48-p\right)\\ \stackrel{!}{=}&0\;,\\ 1=&\frac{p^2\left(\frac18+p\right)}{\left(\frac18-p\right)\left(\frac28-p\right)\left(\frac48-p\right)}\;. \end{align} $

The real-valued solution of this equation is

$ p=\frac18\left(1-4\sqrt[3]{\frac2{3\left(\sqrt{849}-9\right)}}+\sqrt[3]{\frac{\sqrt{849}-9}{18}}\right)\approx0.0942 $

(computation), which lies in $[0,1/8]$ and thus yields a valid solution. Who would have thought that such a monster would come out of such a harmless table of marginal probabilities?

Thus, the probability distribution with least information that yields the given marginal probabilities is

$ p(123)\approx0.0942\;,\\ p(132)\approx0.0308\;,\\ p(213)\approx0.1558\;,\\ p(231)\approx0.0942\;,\\ p(312)\approx0.2192\;,\\ p(321)\approx0.4058\;. $

This we can use to accommodate new information. For instance, if we flip the first card and it turns out to be the $1$, then the probability that the second card is the $2$ is approximately $0.0942/(0.0942+0.0308)=0.7536$.

The point of this entire exercise is that while you may feel that you've specified a probability distribution by listing marginal probabilities, you actually haven't, and you need to make assumptions about the part that you haven't specified in order to proceed, and though these assumptions may feel simple ("no further information"), they actually aren't.

  • 0
    @Drac32Drac: Thanks for the feedback!2012-11-13