Proceso estocástico del restaurante chino

En teoría de la probabilidad, un proceso estocástico de restaurante chino es un tipo de proceso estocástico de tiempo discreto, que es reminiscente al proceso de sentar clientes en las mesas de un restaurante chino, de ahí su nombre.

Imagínese un restaurante chino con un número infinito de mesas circulares, cada una con una capacidad infinita. El primer cliente se sienta en una mesa no ocupada con probabilidad 1. En el paso (n+1)-ésimo un nuevo cliente escoge donde sentarse de acuerdo con un proceso aleatorio que consiste en escoger una silla entre n+1 disponibles: o bien directamente a la izquierda de uno de los n clientes ya sentados, o bien en una mesa no ocupada.

Después de n pasos, el valor del proceso estocástico del restaurante chino es una partición del conjunto de n clientes, donde las mesas son los bloques de la partición. Este problema tiene interés matemático, y algunas aplicaciones, y se ha estudiado la distribución de probabilidad de las posibles particiones tras n pasos.

David J. Aldous atribuye la analogía del restaurante chino para este proceso a Jim Pitman y Lester Dubins en su libro de 1983.​

Definición formal

Para cualquier tiempo n (siendo n un entero positivo) el valor del proceso es una partición B_n del conjunto {1, 2, 3, ..., n}, cuya distribución de probabilidad se determina como sigue. En el instante n = 1, se obtiene la partición trivial { {1} } con probabilidad 1. En el instante n + 1 el elemento n + 1 o bien:

1. se añade a uno de los bloques de la partición B_n, donde cada bloque se escoge con probabilidad |b|/(n + 1) donde |b| es el número de elementos del bloque, o bien
2. se añade a la partición B_n como un bloque de un solo elemento (cliente en mesa desocupada, en la analogía del restaurante), con probabilidad 1/(n + 1).

La partición aleatoria así generada tiene algunas propiedades especiales. Esta partición tiene la propiedad de la intercambiabilidad en el sentido de que reetiquetar a los clientes {1, ..., n} no cambia la distribución de la partición, y es consistente en el sentido de que la ley de la partición de n − 1 obtenida eliminando el elemento n-ésimo de la partición aleatoria en el instante n es la misma que la ley de partición en el instante n − 1.

La probabilidad asingada a una partición particular (ignorando el orden en el que los clientes se sientan alrededor de una mesa particular) viene dado por:

$\Pr(B_{n}=B)={\dfrac {\prod _{b\in B}(|b|-1)!}{n!}}$

donde b es un bloque de la partición B y |b| es el tamaño ( i.e. el número de elementos) de b.

Generalización

Esta construcción anterior puede generalizarse a un modelo con dos parámetros adicionales, α y θ,​​ comúnmente llamados parámetros de descuento y de fortaleza (o de concentración). En el instante n + 1, el siguiente cliente en llegar encuentra |B| mesas ocupadas y cedide sentarse en una mesa vacía con probabilidad

${\dfrac {\theta +|B|\alpha }{n+\theta }},$

o en una mesa ocupada b de tamaño |b| con probabilidad

${\dfrac {|b|-\alpha }{n+\theta }}.$

Para que la construcción defina una medida de probabilidad válida es necesario suponer que o bien α < 0 y θ = - Lα para algún L ∈ {1, 2, ...}; o bien que 0 ≤ α < 1 y θ > −α.

Bajo este modelo la probabilidad asignada a una partición particular B de n, en términos del símbolo de Pochhammer, es

$\Pr(B_{n}=B)={\dfrac {(\theta +\alpha )_{|B|-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{b\in B}(1-\alpha )_{|b|-1,1}$

donde, por convención, $(a)_{0,c}=1$y para $b>0$

$(a)_{b,c}=\prod _{i=0}^{b-1}(a+ic)={\begin{cases}a^{b}&{\text{if }}c=0,\\\\{\dfrac {c^{b}\,\Gamma (a/c+b)}{\Gamma (a/c)}}&{\text{otherwise}}\end{cases}}$

Por tanto, para el caso en el que $\theta >0$ la probabilida de la partición puede expresarse en términos de la función gamma como

$\Pr(B_{n}=B)={\dfrac {\Gamma (\theta )}{\Gamma (\theta +n)}}{\dfrac {\alpha ^{|B|}\,\Gamma (\theta /\alpha +|B|)}{\Gamma (\theta /\alpha )}}\prod _{b\in B}{\dfrac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}$

En el caso uniparamétrico, donde $\alpha$ es cero, esta expresión se simplifica a:

$\Pr(B_{n}=B)={\dfrac {\Gamma (\theta )\,\theta ^{|B|}}{\Gamma (\theta +n)}}\prod _{b\in B}\Gamma (|b|)$

O cuando $\theta$ es cero,

$\Pr(B_{n}=B)={\dfrac {\alpha ^{|B|-1}\,\Gamma (|B|)}{\Gamma (n)}}\prod _{b\in B}{\dfrac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}$

Como antes, la probabilidad asignada a una partición particular depende solamente de los tamaños de los bloques, así que como antes la partición aleatoria es intercambiable en el sentido explicado anteriormente. La propiedad de consistencia también sigue siendo cierta, como antes, por construcción.

Si α = 0, la distribución de probabilidad de la partición aleatoria de n, así generada es la distribución de Ewens con parámetro θ, que se usa en genética de poblaciones y en teoría de la biodiversidad.

Derivación

Esta sección presenta una derivación de la probabilidad de una partición dada. Sea C_i el bloque aleatorio en el que se añade al cliente i-ésimo, para i = 1, 2, 3, ... . Entonces

$\Pr(C_{i}=c|C_{1},\ldots ,C_{i-1})={\begin{cases}{\dfrac {\theta +|B|\alpha }{\theta +i-1}}&{\text{if }}c\in {\text{new block}},\\\\{\dfrac {|b|-\alpha }{\theta +i-1}}&{\text{if }}c\in b;\end{cases}}$

donde δ es la función indicatriz, es decir, δ(A) = 1 or 0 según el evento A ocurra o no ocurra.

La probabilida de que B_n sea una partición particular del conjunto { 1, ..., n } es el producot de estas probabilidades según i varía entre 1 y n. Ahora considérese el tamaño del bloque b: este se incrementa en 1 cada vez que se añade un elemento a él. Cuando se añade el último elemento al bloque b, el tamaño del bloque es (|b| − 1). Por ejemplo, considérese esta secuencia de elecciones: (generar un nuevo bloque  b)(añadir a  b)(añadir a  b)(añadir a  b). Al final, el bloque b tiene 4 elements y el producto de los numeradores en la ecuación anterior da θ · 1 · 2 · 3. Siguiendo esta lógica, se obtiene Pr(B_n = B) como antes.

Número esperado de mesas

Para el caso uniparamétrico, con α = 0 y 0 < θ < ∞, el número esperado de mesas, dad que existen $n$ clientes sentados, resulta ser​

${\begin{aligned}\sum _{k=1}^{n}{\frac {\theta }{\theta +k-1}}=\theta \cdot (\Psi (\theta +n)-\Psi (\theta ))\end{aligned}}$

donde $\Psi (\theta )$ es la función digamma. En el caso general, (α > 0) el número esperado de mesas ocupadas viene dado por​

${\begin{aligned}{\frac {\Gamma (\theta +n+\alpha )\Gamma (\theta +1)}{\alpha \Gamma (\theta +n)\Gamma (\theta +\alpha )}}-{\frac {\theta }{\alpha }}\end{aligned}}$

El proceso del bufé indio

Es posible adaptar el modelo de manera que cada paso no esté unívocamente asociado con una clase ( i.e. ya no se está construyendo una partición), pero que pueda ser asociado con una combinación de clases. En la analogía de los restaurantes, este proceso puede ser entendido como una sucesión aleatoria de comidas servidas a partir de una carta con infinitos platos ofrecidos por un bufé. La probabilidad de que una comida particular esté asociada a un plato es proporcional a la popularidad del plato entre los clientes, y además cada nueva comida pueda ser tomada de comidas que todavía nadie se ha servido. Este proceso más complejo se ha denominado proceso estocástico del buffet indio y puede ser usado para inferir ciertas características latentes en los datos.​

Aplicaciones

El proceso estocástico del restaurante chino está estrechamente relacionado con el proceso de Dirichlet y el esquema de la urna de Pólya y, por tanto, es útil en las aplicaciones de los métodos bayesianos no paramétricos. Los procesos generalizados del restauranete chino por otra parte están estrechamente relacionados con el proceso de Pitman–Yor. Este tipo de procesos han sido usados en muchas aplicaciones, que incluyen la predicción de texto, la clasificación de datos biológicos,​ y la modelización de la biodeversidad, así como la detección de objetos en imágenes.

Referencias

Enlaces externos

• Introduction to the Dirichlet Distribution and Related Processes by Frigyik, Kapila and Gupta

• A talk by Michael I. Jordan on the CRP:
  • http://videolectures.net/icml05_jordan_dpcrp/

• Datos: Q4407236