Random generation of subsets using conditional probabilities - MathOverflow

Random generation of subsets using conditional probabilities

2010-04-06T17:51:36Z

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:

Compute the sum of all ratings for all decks (call it S)
Compute the sum of all ratings for decks that contain a given card (call it S(A))
Compute the sum of all ratings for decks that contain any pair of cards (call it S(A∩B))
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:

Initialize a probability distribution P₀(x) such that P₀(x) = S(x) / S.
Select the first card, c, using the probability distribution P₀
Compute the updated probability distribution P₁(x), such that P₁(x) = n P₀(x) P(x|c), where n is a normalizing factor such that the integral of the distribution is 1.
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.

Answer by Gerhard Paseman for Random generation of subsets using conditional probabilities

2010-04-07T00:24:22Z

You may do better with an approach that mimics the likely characteristics, and then selects cards that meet the characteristics, and then resolves conflicts. Here is a possible approach:

Consider the gross characteristics of such a deck: number and distribution of costs, number of +n Buys +n Cards +n Actions, number of duration cards, number of attack cards. Now start the build by choosing a cost distribution, say 2 2's, 3 3's, 2 4's, and 3 5's. Choose 20 cards at random with cost distribution mirroring the target distribution. Now try a subset of 10 appropriate cards. Check their stats against the others, e.g. number of +1 Buys. If all the stats match up, then check to see how many pairs of cards are disallowed. By whatever means, determine which cards out of the ten chosen do not represent a good fit to a random desired deck, and replace those cards with appropriate choices from the remainder of the 20 cards. If possible, let the stats dictate the replacement subset. Now evaluate the modified deck, and see how many of the stats are out of whack. Chances are good that you will converge to an acceptable deck within a few trials.

If you implement this and find contrarily that chances are bad on converging to a good deck, then try resolving conflicts using a subset of 30 cards instead of a subset of 20 cards. I believe that finding a good set of characteristics will give you a way of generating many good random decks, rather than just considering how often individual cards and card pairs occur or do not occur in favored decks.

Gerhard "Ask Me About System Design" Paseman, 2010.04.06