Procés del restaurant xinès

Plantilla:Infotaula distribució de probabilitatEn la teoria de la probabilitat, el procés del restaurant xinès és un procés estocàstic de temps discret, anàleg a asseure els clients a les taules d'un restaurant. Imagineu un restaurant amb un nombre infinit de taules circulars, cadascuna amb una capacitat infinita. El client 1 s'asseu a la primera taula. El següent client s'asseu a la mateixa taula que el client 1 o a la taula següent. Això continua, amb cada client que tria seure a una taula ocupada amb una probabilitat proporcional al nombre de clients que ja hi ha (és a dir, és més probable que s'asseu a una taula amb molts clients que pocs) o una taula desocupada. En el moment n, els n clients s'han repartit entre m ≤ n taules (o blocs de la partició). Els resultats d'aquest procés són intercanviables, és a dir, l'ordre en què s'asseuen els clients no afecta la probabilitat de la distribució final. Aquesta propietat simplifica enormement una sèrie de problemes en la genètica de poblacions, l'anàlisi lingüística i el reconeixement d'imatges. Fitxer:Chinese Restaurant Process for DP(0.5,H).webm L'analogia del restaurant va aparèixer per primera vegada en un escrit de 1985 de David Aldous, on s'atribuïa a Jim Pitman (qui a més acredita a Lester Dubins).

Fred Hoppe va publicar un any abans un procés de partició equivalent, utilitzant un "esquema d'urna" semblant a l'urna de Pólya. En comparació amb el model d'urna d'Hoppe, el procés del restaurant xinès té l'avantatge que es presta naturalment a descriure permutacions aleatòries mitjançant la seva estructura de cicle, a més de descriure particions aleatòries.

Definició formal

Per a qualsevol nombre enter positiu $n$, deixa ${𝒫}_n$ denoten el conjunt de totes les particions del conjunt $\{1,2,3,...,n\}\triangleq [n]$. El procés del restaurant xinès pren valors en l'infinit producte cartesià $\prod _{n\ge 1}{𝒫}_n$.

El valor del procés en el moment $n$ és una partició $B_n$ del conjunt $[n]$, la distribució de probabilitat de la qual es determina de la següent manera. A l'hora $n=1$, la partició trivial $B_1=\{\{1\}\}$ s'obté (amb una probabilitat). A l'hora $n+1$ l'element " $n+1$ "és o bé:

1. afegit a un dels blocs de la partició $B_n$, on cada bloc s'escull amb probabilitat $|b|/(n+1)$ on $|b|$ és la mida del bloc (és a dir, el nombre d'elements), o
2. afegit a la partició $B_n$ com un nou bloc singleton, amb probabilitat $1/(n+1)$.

La partició aleatòria així generada té algunes propietats especials. És intercanviable en el sentit que el reetiquetatge $\{1,...,n\}$ no canvia la distribució de la partició, i és coherent en el sentit que la llei de la partició de $[n-1]$ obtingut eliminant l'element $n$ de la partició aleatòria $B_n$ és la mateixa que la llei de la partició aleatòria $B_{n-1}$.

La probabilitat assignada a qualsevol partició en particular (ignorant l'ordre en què els clients s'asseuen al voltant d'una taula en particular) és

$\mathrm{Pr}(B_n=B)=\frac{\prod _{b\in B}(|b|-1)!}{n!},B\in {𝒫}_n$

on $b$ és un bloc a la partició $B$ i $|b|$ és la mida de $b$.

La definició es pot generalitzar introduint un paràmetre $\theta >0$ que modifica la probabilitat que el nou client se senti a una taula nova $\frac{\theta }{n+\theta }$ i en conseqüència modifica la probabilitat que se sentin a una taula de mida $|b|$ a $\frac{|b|}{n+\theta }$. El procés de vainilla introduït anteriorment es pot recuperar mitjançant la configuració $\theta =1$. Intuïtivament, $\theta$ es pot interpretar com el nombre efectiu de clients asseguts a la primera taula buida.

Distribució del nombre de taules

La distribució de taules de restaurant xinès (CRT) és la distribució de probabilitat sobre el nombre de taules en el procés de restaurant xinès. Es pot entendre com la suma de $n$ variables aleatòries de Bernoulli independents, cadascuna amb un paràmetre diferent:

$\begin{array}{cc}K& =\sum _{i=1}^n{b}_i\\ b_i& \sim \mathrm{Bernoulli}\left(\frac{\theta }{i-1+\theta }\right)\end{array}$

La funció de massa de probabilitat de $K$ ve donada per

$f(k)=\frac{\mathrm{\Gamma }(\theta )}{\mathrm{\Gamma }(n+\theta )}|s(n,k)|{\theta }^k,k=1,\dots ,n,$

on $s$ denota nombres de Stirling del primer tipus.

Aplicacions

El procés del restaurant xinès està estretament relacionat amb els processos de Dirichlet i l'esquema d'urnes de Pólya, i per tant és útil en aplicacions de l'estadística bayesiana, inclosos els mètodes bayesians no paramètrics. El procés de restaurant xinès generalitzat està estretament relacionat amb el procés Pitman–Yor. Aquests processos s'han utilitzat en moltes aplicacions, com ara el modelatge de text, l'agrupació de dades de microarrays biològics, el modelatge de la biodiversitat i la reconstrucció d'imatges