Algebraiczny algorytm próbkowania z rozkładów warunkowych - czesc I

Zaprezentuję artykuł Persi Diaconisa i Bernda Sturmfelsa z 1998 roku pt. "Algebraic algorithms for sampling from conditional distributions". Prezentuje on ciekawe zastosowanie algebry przemiennej w analizie dla danych dyskretnych. Okazuje się, że konstruując nieprzywiedlny, nieokresowy łańcuch Markowa na skończonych przestrzeniach spełniających jakiś warunek (np. tablic kontyngencji o tych samych rozkładach brzegowych, kwadratów magicznych itd.) możemy rozważać generatory pewnego ideału w pierścieniu wielomianów. Obliczenia w tym pierścieniu są efektywne dzięki zastosowaniu baz Gröbnera. W ten sposób dostajemy na przykład sposób na generowanie losowych wielowymiarowych tablic kontyngencji o ustalonych rozkładach brzegowych względem rozkładu jednostajnego na tej przestrzeni.