# Random generation of subsets using conditional probabilities

Edit: Rewritten with motivation, and hopefully more clarity.

I'm building a site for a card game called dominion. In it, people build 'decks' of 10 distinct cards from a set of (currently) approximately 80. People (will) upload their decks to the site I'm working on, where other users will rate them for quality.

What I would like to do is create a random deck generator that generates decks that are 'similar' to use-created decks. For example, if cards A and B occur frequently in isolation, but infrequently together, the decks generated should share this same property. The state required has to be relatively limited in order for me to be able to do this online.

My tentative idea is to do the following:

1. Compute the sum of all ratings for all decks (call it S)
2. Compute the sum of all ratings for decks that contain a given card (call it S(A))
3. Compute the sum of all ratings for decks that contain any pair of cards (call it S(A∩B))
4. Compute the 'weighted' conditional probability P(A|B) = S(A∩B) / S(B)

Then, to generate a random deck, follow a procedure like the following:

1. Initialize a probability distribution P0(x) such that P0(x) = S(x) / S.
2. Select the first card, c, using the probability distribution P0
3. Compute the updated probability distribution P1(x), such that P1(x) = n P0(x) P(x|c), where n is a normalizing factor such that the integral of the distribution is 1.
4. Repeat from step 2 for the next card.

The problem is, I have no idea if this is valid, or if not, what should be modified to make it so. Based on what I've read, this seems like an application of bayes' theorem, but again I have no idea if I'm getting it wrong.

-
You did not tell what are the desired features of the generator. What is "valid" and what is "not valid" in this game? – Sergei Ivanov Apr 6 '10 at 21:40
The desired outcome is to generate 'random' decks that resemble those generated by users. For example, if cards 'A' and 'B' both occur frequently in decks, but rarely occur together, then this generator should do the same. – Nick Johnson Apr 6 '10 at 22:35
I read your comment as follows: you want every card and every pair of cards to occur with the same probability in your generator and in users' input. No it does do this. For example, you may have 3 special cards such that each of them is in 2/3 of users' decks and each pair of them is there in 1/3 of decks. (This occurs e.g. if each user wants to have exactly 2 of these 3 cards.) Your algorithm will include all 3 in the deck with probability close to 1. Another bad sign: if there is a "must have" card for users, your generator can omit it with a small but nonzero probability. – Sergei Ivanov Apr 6 '10 at 23:14
@Sergei: I realize an algorithm such as I describe has limitations - it can only consider first-order frequencies (those involving two cards, that is). I'm looking for a way to get the best fit with the least state required. In the latter case, omitting a card that's 'must have' in rare cases is actually desired - otherwise it'd never generate a novel deck, just rehashes of existing ones. – Nick Johnson Apr 7 '10 at 7:21