Chinese restaurant process

The Chinese Restaurant Process (CRP) is a predictive rule that descripes a probability distribution on an unbounded partition (clustering). The CRP is as follows: imagine a chinese restaurant with a countably infinite number of tables, the first customer (datum) walks into a restaurant and sits at a table (cluster), the second customer walks into the restaurant and sits at the first customers table with probability 1/2 and chooses a new table with probability 1/2, the nth customer chooses a previous table with probability proportional to the number of customers at that table and chooses his own table with the remaining probability. Defining the probability from this predictive rule yields a probability distribution on an unbounded clustering.