The goal of this assignment is to give you a first-hand appreciation of the Chinese Restaurant Process, which is a scheme for sampling partitions over a set of examples. Each example (customer) is assigned to one of an unbounded number of partitions (tables). assignments of a set of examples.

Make a graph showing the probability that a new customer will be assigned to an empty table, as a function of the number of customers already in the restaurant.  For example, when there are 0 customers in the restaurant, the next customer -- customer 1 -- will be assigned to a new table with probability 1.  Use alpha=5, and plot your graph for up to 200 customers.

Hint: If you're thinking about running a sampler, you should think again. You can compute this probability analytically.

Using the CRP, pick a value of alpha and draw 10000 samples of table assignments for 100 customers. For each sample, determine the total number of tables that are occupied. Make a histogram showing number of tables on the x-axis (which will vary from 1 to 100) and relative frequency on the y-axis.  Repeat this process for a different value of alpha, such that the two histograms look dissimilar.