Chinese Restaurant Process - Definition

Definition

Although whimsical, one fancifully imagines a Chinese restaurant with an infinite number of circular tables, each with infinite capacity. Customer 1 is seated at an unoccupied table with probability 1. At time n + 1, a new customer chooses uniformly at random to sit at one of the following n + 1 places: directly to the left of one of the n customers already sitting at an occupied table, or at a new, unoccupied circular table. Each table thus corresponds to a block of a random partition. (For an account of the custom in actual Chinese restaurants, see table sharing). The probability assigned to any particular partition (ignoring the order in which customers sit around any particular table) is


\Pr(B_n = B) = \dfrac{\prod_{b\in B} (|b| -1)!}{n!}

where b is a block in the partition B and |b| is the size (i.e. number of elements) of b. David J. Aldous attributes the analogy to Pitman and Dubins in his 1983 book.

Read more about this topic:  Chinese Restaurant Process

Famous quotes containing the word definition:

    ... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.
    George Eliot [Mary Ann (or Marian)

    ... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.
    Adrienne Rich (b. 1929)

    Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.
    Nadine Gordimer (b. 1923)