The Chinese Restaurant Process

The Chinese Restaurant Process is very simple and best explained by example. Suppose there is a Chinese restaurant that has 4 tables. There are currently 7 customers: 4 customers at table #1, 2 customers at table #2, 1 customer at table #3, and no customers at table #4. When new customer #8 enters, he will be seated at one of the 4 tables with probabilities:

p(table #1) = 4 / (7 + 1) = 4/8
p(table #2) = 2 / (7 + 1) = 2/8
p(table #3) = 1 / (7 + 1) = 1/8
p(table #4) = 1 / (7 + 1) = 1/8

The probability of being seated at an occupied table is ni / (m + a) where ni is the number of people currently at the table, m is the total number of customers currently at all tables, and a is variable parameter that controls the process.

There will always be one empty table. The probability of being seated at the empty table is a / (m + a).

The Chinese Restaurant Process is an example of “the rich get richer”. Tables with the most customers seated are the most likely to get the next new customer. The larger the value of a is, the less extreme the tendency is.

Tables are assumed to have infinite size, and when a new customer is seated at the one empty table, a new empty table is wheeled out.

The Chinese Restaurant Process is very closely related to the mathematical Dirichlet process. Both processes pop up in problems such as statistical text models, data clustering, biological models, and image reconstruction.

Left: I’ll take a large size, thin crust, topped with olives and penicillin. Center: No thanks. Right: I’ll have some loaves and fishes, and a glass of Holy water.

This entry was posted in Miscellaneous. Bookmark the permalink.

1 Response to The Chinese Restaurant Process

  1. Thorsten Kleppe says:

    James, you always have so interesting topics.

    This is one of those topics that bind me.
    The technique for the Chinese Restaurant Process seems easy to understand.
    But after a second look,
    the empty table equation reminds me on Laplace Smoothing also called Additive Smoothing with one.
    That’s cool, but unintuitive, because a seat with one customer gets the same probability,
    which feels a bit wrong on my first sight.

    One more question for me is, where should we use that idea.

    Anyway, you show every day what a pro is.
    In the E-Sport scene it calls: play hard, go pro
    You live that mentality!

    For ML there is no better teacher or a better place than here,
    for me you are the best of us and what you say counts.
    And you keep on pushing, Hooray!!!

    I’m so happy every day that I can be here to get in touch of your wonderful minds and learn new things.

    Your ability to associate that complicated topics with pictures that also make sense, remarkable.
    It helps to understand things better too.
    The pictures of the articles of Visual Studio Magazine show that quite impressive.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s