# N piles of hidden cards of known marginal probability distribution, then a card is revealed in one of the piles.

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.

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.

-
It can get complicated, because of dependencies. For example, two piles, of $26$ and $26$. We are told probability of Ace of Spades in left pile is $1/2$, same with Ace of Hearts. But maybe the two Aces are stuck together. Or maybe someone is making sure they are not in the same pile. To get clear answers, we would need assumptions about dependencies. –  André Nicolas Oct 25 '12 at 6:12
I'm sure it can, but for all intents and purposes of the problem, player's choice is removed from the problem. Also, the system distinguishes between Ace of Spades and Ace of Hearts as two distinct and separate entities (see the no duplicates section) so the problem really boils down to a separate probability for Ace of Spades and for Ace of Hearts. –  Drac32Drac Oct 25 '12 at 6:23
It's not clear to me from the question whether you're aware of conditional probabilities. If not, you might want to read up on them and then get back to us with more specific questions (or perhaps they'll all be resolved). If you are, you might want to explain in terms of conditional probabilities what's causing you trouble in your $8$-card example (in which, by the way, by "Within each of these piles are cards" you seem to mean "Together, these piles contain the eight cards"; otherwise there would be no linkage to deal with?). –  joriki Oct 25 '12 at 8:49
P.S.: I took a look at the article; the top part contains a lot of formal stuff that you won't need; you can just skip from the introduction to the example with two dice, which is roughly similar to what you're dealing with. –  joriki Oct 25 '12 at 8:53
You are correct, I did mean together the piles contain the eight cards. I am having difficulty correlating the example you directed me with my problem. But I assume what is requested is along the lines of... Assuming a pile with a 20% chance of card #1 and a 15% chance of card #2 out of 8 possible choices with no duplicates, it is revealed that card #2 is held. There are 2 cards in the pile. What is the chance that the remaining card is card #1? –  Drac32Drac Oct 25 '12 at 9:25

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.

-
I applaud you for this informative answer. It is true, I do not know the distribution of the cards at any given point in time. If, under the assumption of "least information" such an explosion of calculations and look-ups is unavoidable, then it is pointless for me to continue developing this portion of the software (in which the probabilities are to be stored in the search tree hierarchy to serve as a representation of the probability that a given action would be available to the agent). Unless a crude approximation can be calculated, the approach is likely doomed to failure. –  Drac32Drac Oct 25 '12 at 20:27
@Drac32Drac: You can find some stuff on the Web about finding the maximum-entropy distribution under linear constraints, e.g. at Wikipedia, in this paper or in this nice article on the lottery. Feel free to ask again if you want to go in that direction. The problem would be determining the Lagrange multipliers without undue effort. –  joriki Oct 26 '12 at 0:52
@Drac32Drac: If you want to go for a crude approximation, I'd just remember which cards can and can't be in which hands, have probabilities $p_{ij}$ for card $i$ being in hand $j$ if it could be, then impose the constraints $\sum_j p_{ij}=1$ and $\sum_ip_{ij}=n_j$, where $n_j$ is the number of cards in hand $j$, and then maximize the "marginal entropy" $-\sum_{ij}p_{ij}\log p_{ij}$. That's still a bit of work, but more feasible than for the full distribution. If you don't want to deal at all with maximizing entropy, you could just ignore or fudge the constraints. –  joriki Oct 26 '12 at 1:20
Well, I can't fault you for going the extra mile to help me out... The more I analyze the problem space, the more I realize that I don't require precise calculations, but rather, ball park estimates should suffice. As long as certain deductions can be made from specific events(such as revealing the location of a particular resource) then the overall system should still function properly. Thanks again for your help in pointing me in the right direction. –  Drac32Drac Oct 26 '12 at 1:35
For the record, I sort of solved my issue by winging some new formulas that are likely not accurate (but close enough in most cases), but fast to calculate. They are asymptotically correct though (with a select few edge cases that I had to deal with), which is more important in my use case. It's just that the computational speed of these crude estimates out-perform the extra accuracy that would be gained by performing a more involved calculation. –  Drac32Drac Nov 13 '12 at 1:27