W jakich okolicznościach integracja Monte Carlo jest lepsza niż quasi-Monte Carlo?

11

Proste pytanie: wykonać całkę wielowymiarową, biorąc pod uwagę, że zdecydowano, że jakaś metoda Monte Carlo jest odpowiednia, czy istnieje jakakolwiek zaleta, że ​​regularna integracja MC przy użyciu liczb pseudolosowych ma przewagę nad integracją quasi-Monte Carlo przy użyciu sekwencji quasirandom ? Jeśli tak, to jak rozpoznałbym sytuacje, w których ta korzyść miałaby miejsce? (A jeśli nie, to dlaczego ktoś używa zwykłej starej integracji Monte Carlo?)

David Z
źródło

Odpowiedzi:

4

Symulacje Monte Carlo są metodą z wyboru do obliczania rozpraszania elektronów. Czasami używane są sztuczki, takie jak próbkowanie ważności, więc można powiedzieć, że nie jest to zwykła stara Monte Carlo. Ale najważniejsze jest prawdopodobnie to, że symulowany jest tutaj z natury stochastyczny proces, podczas gdy pytasz tylko o użycie Monte Carlo do integracji.

Ponieważ nikt inny nie próbował udzielić odpowiedzi, pozwól mi nieco rozszerzyć moją odpowiedź. Załóżmy, że mamy symulację rozpraszania elektronów, w której obliczana jest tylko jedna liczba, taka jak współczynnik rozproszenia wstecznego. Gdybyśmy przeformułowali to jako całkę wielowymiarową, prawdopodobnie byłaby to całka o nieskończonym wymiarze. Z drugiej strony podczas symulacji pojedynczej trajektorii wymagana jest tylko skończona liczba liczb losowych (liczba ta może stać się dość duża, jeśli weźmie się pod uwagę generację elektronów wtórnych). Gdybyśmy użyli quasirandomowej sekwencji, takiej jak próbkowanie hipersześcianu w łacińskiej formie, musielibyśmy zastosować przybliżenie ze stałą liczbą wymiarów i wygenerować losową liczbę dla każdego wymiaru dla każdego punktu próbki.

Myślę więc, że różnica polega na tym, czy próbkowany jest jakiś wysokowymiarowy hipersześcian jednostki w porównaniu z chmurą prawdopodobieństwa nieskończonego wymiaru wokół źródła.

Thomas Klimpel
źródło
5

Niektóre z moich badań polegają na rozwiązaniu stochastycznych równań różniczkowych cząstkowych na dużą skalę. W takim przypadku tradycyjne przybliżenie Monte Carlo całki zainteresowania zbiega się zbyt wolno, aby było to opłacalne w sensie praktycznym ... tzn. Nie chcę przeprowadzać 100 razy więcej symulacji, aby uzyskać dokładność dziesiętną większą dokładność do całki. Zamiast tego zwykle używam innych metod, takich jak rzadkie siatki smolyakowe, ponieważ oferują one większą dokładność przy mniejszej liczbie ocen funkcji. Jest to możliwe tylko dlatego, że mogę założyć pewien stopień płynności funkcji.

Rozsądne jest przypuszczenie, że jeśli oczekujesz, że funkcja, którą integrujesz, ma określoną strukturę (np. Gładkość), najlepiej byłoby użyć quasi-monte carlo, który ją wykorzystuje. Jeśli naprawdę nie możesz poczynić zbyt wielu założeń dotyczących tej funkcji, to Monte Carlo jest jedynym narzędziem, które mogę wymyślić, aby sobie z tym poradzić.

Paweł
źródło
3
W rzeczywistości musisz uruchomić 100 razy więcej symulacji, aby uzyskać dodatkową znaczącą cyfrę.
Brian Borchers
4

Zalety tradycyjnej integracji Monte-Carlo nad integracją quasi-Monte Carlo zostały omówione w Kočiš i papier wybielania jest tutaj . Podają następujące powody:

  • Granica błędu metod qmc jest „teoretycznie” lepsza niż granica podana przez naiwny Monte-Carlo. Jednak dla wartości które są osiągalne w rozsądnym czasie na obecnym sprzęcie, jest lepszą opcją dla . (Kocis i Whiten pisali w 1997 roku, więc przypuszczalnie od tego czasu nieco wzrosło).O ( N - 1 / 2 ) N O ( N - 1 / 2 ) d 40 dO(log(N)d/N)O(N1/2)NO(N1/2)d40d
  • Błąd integracji QMC jest związany przez nierówność Koksma-Hławka gdzie jest odmianą i jest gwiazdą rozbieżności. Ale cytując z pracy Kocisa, V [ f ] f D N

    errorV[f]DN
    V[f]fDN

    Niestety, teoretyczna granica rozbieżności istniejących sekwencji nie jest użyteczna dla średnich i dużych wartości s. Druga opcja, numeryczna ocena rozbieżności gwiazd w sekwencji dla dużych s, wymaga nadmiernego wysiłku obliczeniowego, a nawet rozsądne szacunki liczbowe takich rozbieżności są bardzo trudne do uzyskania.

    Dzięki tradycyjnej integracji Monte-Carlo możemy określić cel błędu i poczekać, ponieważ granica błędu jest łatwa do obliczenia. Dzięki QMC musimy określić liczbę ocen funkcji i mamy nadzieję, że błąd mieści się w naszym celu. (Należy zauważyć, że istnieją techniki pozwalające temu zaradzić, takie jak randomizowane quasi-Monte Carlo, w których do oszacowania błędu stosuje się wiele oszacowań quasi-Monte Carlo).

  • Ponieważ „stałe warunki” błędu dotyczą wielu sekwencji o niskiej rozbieżności, które faktycznie posiadamy, rosną wykładniczo wraz z wymiarem, Kocis i Whiten używają innej miary do oszacowania błędu: Maksymalna odległość między punktami próbki. Daje to szacunkową wartość błędu i twierdzą, że pasuje do obserwowanego zachowania wielu integrandów.O(1/N1/2+2/d)

  • Aby quasi-Monte Carlo pokonało tradycyjne Monte-Carlo, integrand musi mieć „niski efektywny wymiar”. Zobacz artykuł Art Owena na ten temat tutaj .

użytkownik14717
źródło