Jaki jest najskuteczniejszy sposób generowania losowej permutacji na podstawie probabilistycznych zamian par?

48

Pytanie, które mnie interesuje, dotyczy generowania przypadkowych permutacji. Biorąc pod uwagę probabilistyczną bramę wymiany par jako podstawowy element konstrukcyjny, jaki jest najbardziej skuteczny sposób na uzyskanie jednolicie losowej permutacji elementów? Tu stosować „probabilistyczny bramy parami wymiany” się operacja, która realizuje brama Przełączanie do wybranych elementów i z pewnym prawdopodobieństwem , które mogą być dowolnie wybranej dla każdej bramki i tożsamości w inny sposób. $n$ $i$ $j$ $p$

Zdaję sobie sprawę, że zwykle nie jest to sposób generowania losowych permutacji, w którym zwykle można użyć czegoś takiego jak tasowanie Fishera-Yatesa, jednak nie będzie to działać w przypadku aplikacji, o której myślę, ponieważ dozwolone operacje są różne.

Oczywiście można to zrobić, pytanie brzmi, jak skutecznie. Jaka jest najmniej probabilistycznych zamian niezbędnych do osiągnięcia tego celu?

AKTUALIZACJA:

Anthony Leverrier zapewnia metodę poniżej, która rzeczywiście daje prawidłowy rozkład przy użyciu bramek , przy czym Tsuyoshi Ito zapewnia inne podejście z takim samym skalowaniem w komentarzach. Jednak najlepszą dolną granicą, jaką do tej pory widziałem, jest , która skaluje się jako . Tak więc pytanie pozostaje otwarte: czy jest najlepszym, co można zrobić (tj. Czy jest lepsza dolna granica)? Lub alternatywnie, czy istnieje bardziej wydajna rodzina obwodów? $O(n^2)$ $\lceil \log_2(n!) \rceil$ $O(n\log n)$ $O(n^2)$

AKTUALIZACJA:

W kilku odpowiedziach i komentarzach zaproponowano obwody składające się całkowicie z zamian probabilistycznych, w których prawdopodobieństwo jest ustalone na $\frac{1}{2}$ . Taki obwód nie może rozwiązać tego problemu z następującego powodu (usunięty z komentarzy):

Wyobraź sobie obwód, który wykorzystuje $m$ takich bram. Następnie istnieją $2^m$ obliczenia ścieżki obliczeniowe, więc każda permutacja musi wystąpić z prawdopodobieństwem $k 2^{−m}$ dla pewnej liczby całkowitej k. Jednak dla równomiernego rozkładu wymagamy $k 2^{−m}=\frac{1}{n!}$ , Który można przepisać jako $k n! = 2^m$ . Oczywiście nie można tego spełnić dla liczby całkowitej $k$ dla $n\geq3$ , ponieważ $3|n!$ (dla $n\geq 3$ , ale $3\nmid 2^m$ .

AKTUALIZACJA (od mjqxxxx, który oferuje nagrodę):

Oferowana nagroda za (1) dowód, że wymagane są bramki , lub (2) działający obwód dla dowolnego , który wykorzystuje mniej niż bramek. $\omega(n \log n)$ $n$ $n(n-1)/2$

co.combinatorics randomness probabilistic-circuits

— Joe Fitzsimons
źródło

8

@Anthony: Być może nie jest to oczywiste, ale możesz: Wyobraź sobie, że obwód tworzy jednolity rozkład permutacji pierwszych elementów . Następnie po którym następuje zamiana probabilistyczna (z prawdopodobieństwem 0,5) między pozycją a pozycją da jednolicie losowy wybór dla pozycji . Jeśli zastosujesz się do tego, stosując ponownie do pierwszych elementów , powinieneś uzyskać jednolicie losowy rozkład.

C

$C$

n - 1

$n-1$

C

$C$

n - 1

$n-1$

n

$n$

n

$n$

C

$C$

n - 1

$n-1$

— Joe Fitzsimons,

4

ok, dzięki za wyjaśnienie! Zauważ, że zamiana probabilistyczna powinna mieć proba między pozycją a pozycją .

(n - 1) / n

$(n-1)/n$

n - 1

$n-1$

n

$n$

— Anthony Leverrier,

5

Pod względem wymaganej entropii algorytm potrzebuje losowe bity, gdzie jest funkcją binarnej entropii. Nie mogę dokładnie obliczyć tej sumy, ale jest to zgodnie z matematyką ... podczas gdy optimum jest co najmniej .

(n - 1) h (1 / 2) + (n - 2) h (1 / 3) + \dots + (n - k) h (1 / (k + 1)) + \dots + h (1 / n)

$(n-1) h(1/2) + (n-2) h(1/3) + \cdots + (n-k) h(1/(k+1)) + \cdots + h(1/n)$

h (.)

$h(.)$

O (n \log_{2} (n)^{2})

$O(n \log_2(n)^2)$

O (n \log_{2} (n))

$O(n \log_2(n))$

— Anthony Leverrier

8

Różni się to od tego, co chcesz, ale istnieje rodzina obwodów o rozmiarze O (n log n), które generują każdą permutację z prawdopodobieństwem co najmniej 1 / p (n!) Dla pewnego wielomianu p: rozważ sieć sortującą o rozmiarze O (n log n) i zamień każdy komparator na bramkę zamiany prawdopodobieństwa-1/2. Ze względu na poprawność sieci sortującej, każda permutacja musi powstać z niezerowym prawdopodobieństwem, czyli koniecznie co najmniej 1/2 ^ {O (n log n)} = 1 / poli (n!).

— Tsuyoshi Ito,

3

Powrót do pierwotnego problemu. Należy zauważyć, że rozwiązanie O (n ^ 2), które opisał Anthony, może być postrzegane jako zastępowanie każdego komparatora w sieci sortującej reprezentującej sortowanie selekcyjne probabilistyczną bramką wymiany z odpowiednim prawdopodobieństwem. (więcej)

— Tsuyoshi Ito

17

Działający algorytm, który opisałem w komentarzu powyżej, jest następujący:

Najpierw uruchomić poprzez wprowadzanie losowej elementu z prawdopodobieństwem w pozycji : zamiany pozycji 1 i 2, z Proby , a następnie 2 i 3 z Proby, , ..., a następnie i o Proby . $1/n$ $n$ $1/2$ $2/3$ $n-1$ $n$ $(n-1)/n$
Zastosuj tę samą procedurę, aby ustawić losowy element w pozycji : zamień pozycje 1 i 2 za pomocą prob ... następnie pozycje i pomocą proba . $n-1$ $1/2$ $n-2$ $n-1$ $(n-2)/(n-1)$
Itp

Liczba bramek wymaganych przez ten algorytm wynosi . $(n-1)+(n-2)+ \cdots + 2+1 = n(n-1)/2 = O(n^2)$

— Anthony Leverrier
źródło

3

Ten algorytm ma połączenie z sortowaniem bąbelkowym. W szczególności rozważ przestrzeń stanów wszystkich permutacji o rozmiarze n. Prawdopodobieństwo, że 1. element większy niż 2. wynosi 1/2, zamień z tym prawdopodobieństwem. Załóżmy, że pierwsze dwa elementy są posortowane, co to jest proba 2. element> 3. element 2/3 itd. Dlatego wydaje się możliwe przekształcenie algorytmu sortowania w obwód bramki wymiany, w którym każdy kolejny krok powinien uwzględniać prawdopodobieństwa warunkowe wynikające z poprzednich kroki. Które w pewnym sensie sugerują wyraźną nieefektywną metodę budowy takich obwodów.

— mkatkov,

16

To nie jest ani odpowiedź, ani nowa informacja. Tutaj postaram się podsumować dyskusje, które miały miejsce w komentarzach na temat relacji między tym problemem a sieciami sortującymi . W tym poście wszystkie godziny są w UTC, a „komentarz” oznacza komentarz do pytania, chyba że zaznaczono inaczej.

Obwód składający się z probabilistycznych bramek wymiany (które zamieniają losowo dwie wartości) naturalnie przypomina nam sieć sortującą, która jest niczym innym jak obwodem składającym się z komparatorów (które zamieniają dwie wartości w zależności od kolejności między nimi). Rzeczywiście, obwody dla obecnego problemu i sieci sortujące są powiązane ze sobą w następujący sposób:

Roztwór Anthony Leverriera z n ( n -1) / 2 probabilistyczne bramy wymiany może być rozumiana jako sieć sortujące do sortowania bańki z komparatorów zastąpiona probabilistycznych bramy wymienne z odpowiednich prawdopodobieństw. Zobacz komentarz mkatkov z 10 marca 4:53 na tę odpowiedź, aby poznać szczegóły. Sieć sortowania dla sortowania wyboru można również wykorzystać w ten sam sposób. (W komentarzu z 7 marca 23:04 opisałem obwód Anthony'ego jako rodzaj selekcji, ale to nie było poprawne.)
Jeśli chcemy tylko każdej permutacji z niezerowym prawdopodobieństwem i nie dbamy o równomierny rozkład, wówczas każda sieć sortująca wykonuje zadanie, gdy wszystkie komparatory są zastępowane bramkami zamiany prawdopodobieństwa-1/2. Jeśli użyjemy sieci sortującej z komparatorami O ( n log n ), powstały obwód generuje każdą permutację z prawdopodobieństwem co najmniej 1/2 ^{O ( n log n )} = 1 / poli ( n !), Jak zaobserwowałem w moim komentarzu z marca 7 22:59.
W tym problemie wymagane jest, aby bramki zamiany probabilistycznej działały niezależnie. Jeśli usuniemy to ograniczenie, każdą sieć sortującą można przekształcić w obwód, który generuje równomierny rozkład, jak wspomniałem w komentarzu z 7 marca 23:08, a użytkownik 1749 opisany bardziej szczegółowo z 8 marca 14:07.

Fakty te najwyraźniej sugerują, że problem ten jest ściśle związany z sieciami sortującymi. Jednak Peter Taylor znalazł dowód, że relacja może nie być bardzo bliska. Mianowicie, nie każdą sieć sortującą można przekształcić w pożądany obwód, zastępując komparatory probabilistycznymi bramkami wymiany o odpowiednich prawdopodobieństwach. Pięcio-komparacyjna sieć sortująca dla n = 4 jest kontrprzykładem. Zobacz jego komentarze z 10 marca 11:08 i 10 marca 14:01.

— Tsuyoshi Ito
źródło

3

@mkatkov: Widziałem trzy lub cztery usunięte odpowiedzi i nie pamiętam, który był, przepraszam. Jeśli znalazłeś rozwiązanie z bramkami mniejszymi niż n (n − 1) / 2, chciałbym poznać całą konstrukcję (i nie chodzi o to, by ukraść ci nagrodę mjqxxxx :)).

— Tsuyoshi Ito,

2

@mkatkov: Nadal jestem sceptyczny. Jak napisałem w ostatnim akapicie tego postu, Peter Taylor stwierdził, że sieci sortującej z pięcioma komparatorami dla n = 4 nie można przekształcić w rozwiązanie obecnego problemu, zastępując komparatory bramkami zamiany probabilistycznej. To implikuje, że twoja logika nie może działać dla każdej sieci sortującej, chociaż nie wyklucza to, że w jakiś sposób działa ona, powiedzmy, w przypadku parzystego parzystego nieparzystego.

— Tsuyoshi Ito,

1

@mkatkov: Powodem, dla którego tego rodzaju rozwiązanie nie działa (lub przynajmniej nie pokazano żadnego działającego przykładu), jest to, że bramki wymiany w sieci sortowania parami strzelają w wysoce skorelowany sposób. W tym problemie wszystkie bramy strzelają niezależnie, co prowadzi do zupełnie innej przestrzeni możliwych obwodów.

— mjqxxxx,

1

@ mkatbov, każdy krok w sieci Anthony'ego wybiera jedno z m wejść (gdzie m wynosi od n do 2). Nie możesz wybrać jednego z m wejść z mniej niż bramkami m-1, więc w szczególności nie możesz tego zrobić z bramkami logarytmicznymi. Pokonanie prawdopodobnie będzie wymagało pewnego rodzaju podejścia dziel i zwyciężaj.

O (n^{2})

$O(n^2)$

— Peter Taylor

3

@Tsuyoshi, Yuval i ja przeanalizowaliśmy wszystkie możliwe rozwiązania 5-bramkowe dla i wyeliminowaliśmy je wszystkie, co wzmacnia wynik, że nie wszystkie sieci sortujące można przekształcić w jednolite sieci permutacyjne, w wyniku czego istnieją rozmiary problemów, dla których optymalna jednolita sieć permutacyjna wymaga więcej bramek niż optymalna sieć sortująca.

n = 4

$n=4$

— Peter Taylor,

15

W żadnym wypadku nie jest to pełna odpowiedź, ale zawiera wynik, który może być użyteczny i stosuje ją, aby uzyskać pewne ograniczenia w sprawie które ograniczają możliwe rozwiązania 5-bramkowe do 2500 łatwych do wyliczenia przypadków. $n=4$

Najpierw ogólny wynik: w każdym rozwiązaniu, które dopuszcza obiektów, muszą istnieć co najmniej zamiany, które mają prawdopodobieństwo . $n$ $n-1$ $\frac{1}{2}$

Dowód: rozważ reprezentację permutacji permutacji rzędu . Są to macierzy spełniających . Rozważmy zamianę pomiędzy i z prawdopodobieństwem : jest reprezentowana (notacji cyklu reprezentować permutację). Można pomyśleć o pomnożeniu przez tę macierz w kategoriach teorii reprezentacji lub w kategoriach Markowa jako o zastosowaniu permutacji z prawdopodobieństwem i pozostawieniu rzeczy niezmienionych z prawdopodobieństwem . $n$ $n\times n$ $A_\pi$ $(A_\pi)_{i,j} = [i = \pi(j)]$ $i$ $j$ $p$ $(1-p)I + pA_{(i j)}$ $(i j)$ $p$ $1-p$

Sieć permutacji jest zatem łańcuchem takich multiplikacji macierzy. Rozpoczynamy z macierzą jednostkową, a wynik końcowy będzie macierz gdzie , tak, że będą się z matrycy z szeregu do matrycy stopnia przez mnożenie - tzn. ranga maleje o . $U$ $U_{i,j} = \frac{1}{n}$ $n$ $1$ $n-1$

Biorąc pod uwagę rangę macierzy , widzimy, że są one zasadniczo matrycami tożsamości oprócz niewielkiego , więc mają pełną rangę, chyba że , w którym to przypadku mają rangę . $(1-p)I + pA_{(i j)}$ $\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}$ $p=\frac{1}{2}$ $n-1$

Stosując nierówność macierzową Sylwestra, stwierdzamy, że każda zamiana zmniejsza rangę tylko wtedy, gdy , a gdy ten warunek jest spełniony, zmniejsza ją o nie więcej niż 1. Dlatego wymagamy co najmniej zamiany prawdopodobieństwa . $p=\frac{1}{2}$ $n-1$ $\frac{1}{2}$

Pamiętaj, że tej granicy nie można zacieśnić, ponieważ sieć Anthony'ego Leverriera to osiągnęła.

Zastosowanie w sprawie . Mamy już rozwiązania z 6 bramkami, więc pytanie brzmi, czy możliwe są rozwiązania z 5 bramkami. Wiemy teraz, że co najmniej 3 bramki muszą być 50/50 zamianami, więc mamy dwa „wolne” prawdopodobieństwa, i . Istnieje 32 możliwe zdarzenia (5 niezależnych wydarzeń, każde z dwoma wynikami) i segmenty, z których każdy musi zawierać co najmniej jedno zdarzenie. Zdarzenia dzielą się na 8 z prawdopodobieństwem , 8 z prawdopodobieństwem , 8 z prawdopodobieństwem i 8 z prawdopodobieństwem . $n=4$ $p$ $q$ $4! = 24$ $\frac{pq}{8}$ $\frac{\overline{p}q}{8}$ $\frac{p\overline{q}}{8}$ $\frac{\overline{p}\overline{q}}{8}$

32 zdarzenia na 24 segmenty bez pustych segmentów sugerują, że co najmniej 16 segmentów zawiera dokładnie jedno zdarzenie, więc co najmniej dwa z czterech podanych powyżej prawdopodobieństw są równe . Biorąc pod uwagę symetrie, mamy dwa przypadki: lub . $\frac{1}{24}$ $pq = \overline{p}q = \frac{1}{3}$ $pq = \overline{p}\overline{q} = \frac{1}{3}$

Pierwszy przypadek daje , ( poprawka lub , odwijając symetrię). Drugi przypadek daje , więc , co nie ma rzeczywistych rozwiązań. $p=\overline{p}=\frac{1}{2}$ $q=\frac{2}{3}$ $q=\frac{1}{3}$ $pq=1-p-q+pq$ $pq = p(1-p) = \frac{1}{3}$

Dlatego jeśli istnieje rozwiązanie 5-bramkowe, mamy cztery bramki z prawdopodobieństwem i jedną bramę z prawdopodobieństwem lub . Wlog pierwsza zamiana to , a druga to lub ; pozostałe trzy mają (nie więcej niż) pięć możliwości, ponieważ nie ma sensu wykonywać tej samej wymiany dwa razy z rzędu. Mamy więc do rozważenia sekwencji wymiany i 10 sposobów przypisywania prawdopodobieństw, co prowadzi do 2500 przypadków, które można wyliczyć i przetestować mechanicznie. $\frac{1}{2}$ $\frac{1}{3}$ $\frac{2}{3}$ $0\leftrightarrow 1$ $0\leftrightarrow 2$ $2\leftrightarrow 3$ $2\times 5^3$

Aktualizacja: Yuval Filmus i ja wyliczyliśmy i przetestowaliśmy przypadki i nie znaleźliśmy żadnych rozwiązań, więc optymalne rozwiązanie dla obejmuje 6 bramek, a przykłady rozwiązań 6-bramkowych można znaleźć w innych odpowiedziach. $n=4$

— Peter Taylor
źródło

2

Moje wyliczenie przypadku nie dało krótszego przykładu.

— Yuval Filmus

... nawet po korekcie.

— Yuval Filmus

1

Doskonale, to bardzo miła obserwacja.

— Joe Fitzsimons,

1

@ mjqxxxx, obliczam, że szukając rozwiązania 9-bramkowego na , musiałbyś wziąć pod uwagę około 104 miliony przypadków (chociaż można by to nieco zmniejszyć dzięki sprytowi), ale dla każdego przypadku obliczałbyś 120 równań w 5 zmiennych ze skrzyżowaniami, a następnie sprawdzanie rozwiązania. Prawdopodobnie jest to wykonalne na standardowym komputerze stacjonarnym, ale wymaga nieco więcej wysiłku, ponieważ nie można tak łatwo ograniczyć możliwych wartości prawdopodobieństwa.

n = 5

$n=5$

— Peter Taylor

4

Przyznam nagrodę tutaj, chociaż odpowiedź nie zapewnia ani asymptotycznej poprawy w stosunku do dolnej granicy ani żadnej poprawy w górnej granicy , ponieważ przynajmniej dowodzi, że jest optymalny w pojedynczym, nietrywialnym przypadku.

Ω (n \log n)

$\Omega(n \log n)$

n (n - 1) / 2

$n(n-1)/2$

n (n - 1) / 2

$n(n-1)/2$

— mjqxxxx,

14

Wydaje się, że następujące i nowe istotne informacje:

W pracy [CKKL99] pokazano, jak uzyskać 1 / n blisko jednolitej permutacji n elementów za pomocą sieci przełączającej o głębokości O (log n), a zatem w sumie O (n log n) komparatorów.

Ta konstrukcja nie jest wyraźna, ale można ją wyrazić, jeśli zwiększysz głębokość do polylog (n). Zobacz wskazówki w artykule [CKKL01], który zawiera także więcej informacji.

Poprzedni komentarz już wskazywał na wynik, mówiąc, że wystarczą przełączniki O (n log n), ale różnica polega na tym, że w przełączanych sieciach porównywane elementy są stałe.

[CKKL99] Artur Czumaj, Przemysława Kanarek, Mirosław Kutylowski i Krzysztof Łarys. Opóźnione sprzęganie ścieżek i generowanie losowych permutacji za pomocą rozproszonych procesów stochastycznych. W Sympozjum na temat algorytmów dyskretnych (SODA), strony 271 {280, 1999.

[CKKL01] Artur Czumaj, Przemysława Kanarek, Mirosław Kutylowski i Krzysztof Łarys. Przełączanie sieci w celu generowania losowych permutacji, 2001.

— Manu
źródło

Dzięki, to z pewnością warto wiedzieć. Nadal jednak jestem zainteresowany informacjami o numerze bramki do wygenerowania dokładnego rozkładu.

— Joe Fitzsimons,

12

Oto dość interesujące rozwiązanie dla . Ten sam pomysł działa również dla . $n=4$ $n=6$

Zacznij od przełączników z prawdopodobieństwem . Zmniejszając do i do , jesteśmy w sytuacji . Zastosuj przełączniki z prawdopodobieństwem . Wynikiem jest Nasz następny ruch to z prawdopodobieństwem . Dlatego naprawdę zależy nam tylko na tym, aby wynik poprzedniego etapu miał postać (przypadek A) lub formularz $(0,1),(2,3)$ $1/2$ $0,1$ $X$ $2,3$ $Y$ $XXYY$ $(0,3),(1,2)$ $p$

\begin{aligned} X X Y Y & w.p. (1 - p)^{2}, \\ Y Y X X & w.p. p^{2}, \\ X Y X Y & w.p. p (1 - p), \\ Y X Y X & w.p. p (1 - p) \end{aligned}

$\begin{align*} XXYY &\text{ w.p. } (1-p)^2, \\ YYXX &\text{ w.p. } p^2, \\ XYXY &\text{ w.p. } p(1-p), \\ YXYX &\text{ w.p. } p(1-p) \end{align*}$

(0, 2), (1, 3)

$(0,2),(1,3)$

1 / 2

$1/2$

X X Y Y / Y Y X X

$XXYY/YYXX$

X Y X Y / Y X Y X

$XYXY/YXYX$ (przypadek B). W przypadku A te przełączniki spowodują jednolite prawdopodobieństwo w stosunku do . W przypadku B będą one nieskuteczne. Dlatego musi spełniać Biorąc to pod uwagę, wynik jest jednolity.

X X Y Y / X Y Y X / Y X X Y / Y Y X X

$XXYY/XYYX/YXXY/YYXX$

p

$p$

p (1 - p) = 1 / 6 ⟹ p = \frac{3 \pm \sqrt{3}}{6} .

$p(1-p) = 1/6 \Longrightarrow p = \frac{3 \pm \sqrt{3}}{6}.$

Podobny pomysł działa dla - najpierw losowo sortujesz każdą połówkę, a następnie „scalasz” je. Jednak nawet dla nie widzę, jak poprawnie połączyć połówki. $n=6$ $n=8$

Ciekawym punktem tego rozwiązania jest dziwne prawdopodobieństwo . $p$

Na marginesie, zestaw prawdopodobieństw które mogą nam pomóc, podaje , gdzie przekracza wszystkie wartości własne wszystkich reprezentacji przy wszystkich transpozycjach. $p$ $1/(1-\lambda)$ $\lambda \leq 0$ $S_n$

— Yuval Filmus
źródło

1

Dziwne wartości są rzeczywiście zachęcające, ponieważ uważam, że istnieje dość prosty dowód, że jeśli ograniczymy prawdopodobieństwa do dla liczby całkowitej najlepszym, co możesz zrobić, jest .

p

$p$

1 / k

$1/k$

k

$k$

O (n^{2})

$O(n^2)$

— Joe Fitzsimons,

5

Trochę innym sposobem dla elementów 2n, który jest nadal dziwny w podobnym sensie, jest tasowanie pierwszych n elementów, tasowanie ostatnich n elementów, zamiana (i, i + n) z prawdopodobieństwem p_i dla i = 1,…, n , potasuj pierwsze n elementów i potasuj ostatnie n elementów. Prawdopodobieństwa p_i należy wybrać tak, aby prawdopodobieństwo, że dokładnie k z n strzelających bramek wymiany było równe i takie prawdopodobieństwa p_i są podane przez ( 1 + x_i) / 2 gdzie x_1,…, x_n są pierwiastkami wielomianu P_n Legendre . (więcej)

{(\binom{n}{k})}^{2} / (\binom{2 n}{n})

$\binom{n}{k}^2/\binom{2n}{n}$

— Tsuyoshi Ito

6

(kont.) Rozczarowującą rzeczą w opisywanej przeze mnie wariacji jest to, że wymaga ona zamiany probabilistycznej n (n − 1) / 2, gdy n jest potęgą dwóch, czyli dokładnie taką samą liczbą bramek rozwiązanie Anthony'ego Leverriera.

— Tsuyoshi Ito,

@Tsuyoshi, twoja konstrukcja jest wyraźnie poprawna, ale zastanawiam się, czy robi więcej niż to konieczne. W tej chwili nie mam czasu na analizę, ale jeśli tak, to warto rozważyć, czy istnieją takie, że ; ; ; ; następnie zastosuj odpowiednią permutację korzeni Legendre (i wypełnij pozostałe ćwiartki) może działać.

p_{0}, p_{1}

$p_0, p_1$

0 \leftrightarrow 1, p = \frac{1}{2}

$0\leftrightarrow 1, p=\frac{1}{2}$

2 \leftrightarrow 3, p = \frac{1}{2}

$2\leftrightarrow 3, p=\frac{1}{2}$

0 \leftrightarrow 2, p = p_{0}

$0\leftrightarrow 2, p=p_0$

1 \leftrightarrow 3, p = p_{1}

$1\leftrightarrow 3, p=p_1$

— Peter Taylor

7

Rozważ problem losowego tasowania łańcucha , gdzie każdy blok ma długość , z obwodem składającym się z probabilistycznych zamian par. Oznacza to, że wszystkie ciągi o si s muszą być jednakowo prawdopodobnymi wyjściami obwodu, biorąc pod uwagę określone wejście. Niech będzie optymalnym obwodem dla tego problemu, a będzie optymalnym obwodem dla pierwotnego problemu (losowe tasowanie elementów ). Zastosowanie losowej permutacji jest wystarczające do losowego przeplatania i , więc $XX..XY..YY$ $n$ $(2n)!/(n!)^2$ $n$ $X$ $n$ $Y$ $B_{2n}$ $C_{2n}$ $2n$ $X$ $Y$ $\lvert{B_{2n}}\rvert \le \lvert{C_{2n}}\rvert$ . Z drugiej strony możemy tasować elementów, tasując pierwsze elementów, tasując ostatnie elementów i na koniec stosując obwód . Oznacza to, że . Łącząc te dwie granice, możemy uzyskać następujący wynik: $2n$ $n$ $n$ $B_{2n}$ $\lvert{C_{2n}}\rvert \le 2\lvert{C_{n}}\rvert + \lvert{B_{2n}}\rvert$

$\lvert{B_{2n}}\rvert$ i to oba , albo nie ma. $\lvert{C_{2n}}\rvert$ $o(n^2)$

Widzimy, że oba problemy są równie trudne, przynajmniej w tym sensie. Ten wynik jest nieco zaskakujący, ponieważ można oczekiwać, że problem losowania będzie łatwiejszy. W szczególności argument pokazuje, że to , ale daje mocniejszy wynik, że to . $XY$ $\lvert{B_{2n}}\rvert$ $\Omega(n)$ $\lvert{C_{2n}}\rvert$ $\Omega(n \log n)$

— mjqxxxx
źródło

7

Diaconis i Shahshahani 1981, „Generowanie losowej permutacji za pomocą losowych transpozycji” pokazuje, że 1/2 n log n losowych transpozycji (uwaga: tutaj nie ma „O”) skutkuje permutacją bliską (w całkowitej odległości zmiany) do jednolitej. Nie jestem pewien, czy dokładnie to, co jest dozwolone w twojej aplikacji, pozwala ci użyć tego wyniku, ale jest dość szybki i ciasny, ponieważ jest to przykład zjawiska odcięcia. Zobacz Losowe spacery po skończonych grupach autorstwa Saloffa-Coste'a, aby zobaczyć podobne wyniki.

— Jason Morton
źródło

1

I prawdopodobnie można stworzyć dwie niemal losowe kombinacje, aby uzyskać permutację, która jest jeszcze bardziej losowa.

— mjqxxxx,

7

... Należy jednak zauważyć, że tak naprawdę nie jest to ten sam problem (nawet pozwalający na rozwiązanie przybliżone, a nie dokładne), ponieważ autorzy rozważają transpozycje losowo wybranych par elementów, a nie probabilistyczne transpozycje określonych par elementów.

— mjqxxxx,

5

To jest naprawdę komentarz, ale jest zbyt długi, aby opublikować go jako komentarz. Podejrzewam, że teoria reprezentacji grupy symetrycznej może być użyteczna do udowodnienia lepszej dolnej granicy. Chociaż prawie nic nie wiem na temat teorii reprezentacji i mogę nie mieć pojęcia, pozwól mi wyjaśnić, dlaczego może to być związane z obecnym problemem.

Zauważ, że zachowanie obwodu składającego się z probabilistycznych bramek swapowych można w pełni określić jako rozkład prawdopodobieństwa p na S _n , grupie permutacji na n elementach. Permutację g ∈S _n można traktować jako zdarzenie, że i- ty wynik jest g ( i ) wejściem dla wszystkich i ∈ {1,…, n }. Teraz przedstawiamy rozkład prawdopodobieństwa p jako sumę formalną ∑ _{g ∈S _n} p ( g ) g . Na przykład zamiana probabilistyczna między drutami i ij z prawdopodobieństwem p jest reprezentowane jako (1- p ) e + p τ _ij , gdzie e ∈S _n jest elementem tożsamości, a τ _ij ∈S _n jest transpozycją między i i j .

Ciekawym faktem na temat tej sumy formalnej jest to, że zachowanie konkatenacji dwóch niezależnych obwodów można formalnie opisać jako iloczyn tych sum formalnych. Mianowicie, w przypadku zachowań obwodów C ₁ i C ₂ są przedstawione jako posiadanie sumy ₁ = Σ _g_∈S_{_n} p ₁ ( g ), g i ₂ = Σ _g_∈S_{_n} s ₂ ( g ) g , odpowiednio, po czym zachowanie obwodu C _1, a następnie C ₂jest reprezentowany jako ∑ _{g ₁ , g ₂ ∈S _n} p ₁ ( g ₁ ) p ₂ ( g ₂ ) g ₁g ₂ = a ₁a ₂ .

Dlatego pożądany obwód z m zamian probabilistycznych dokładnie odpowiada sposobowi zapisu sumy (1 / n !) ∑ _{g ∈S _n} g jako iloczynu m sum, z których każdy ma postać (1- p ) e + p τ _ij . Chcielibyśmy poznać minimalną liczbę m czynników.

Sumy formalne ∑ _{g ∈S _n} f ( g ) g , gdzie f jest funkcją od S _n do ℂ, wyposażoną w naturalnie zdefiniowane dodawanie i mnożenie, tworzą pierścień zwany algebrą grupy ℂ [S _n ]. Algebra grupowa jest ściśle związana z teorią reprezentacji grup, która jest głęboką teorią, którą wszyscy znamy i boimy się :). To mnie podejrzewa, że coś w teorii reprezentacji może odnosić się do obecnego problemu.

A może jest to zbyt daleko idące.

— Tsuyoshi Ito
źródło

2

Oto, co to ogranicza. Istnieje grupa reprezentacji grupy symetrycznej, które można obliczyć jawnie dla transpozycji, przy pewnym nakładzie pracy (zwykle są one obliczane tylko jawnie dla transpozycji ). Wartość początkowa każdej reprezentacji jest odpowiednią matrycą tożsamości. Zastosowanie zamiany probabilistycznej powoduje pomnożenie każdej reprezentacji przez , gdzie jest wartością reprezentacji w przeprowadzonej zamianie . (kont.)

(k, k + 1)

$(k,k+1)$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

(i j)

$(ij)$

— Yuval Filmus

2

Aby dane wyjściowe były jednolite, potrzebujemy wszystkich reprezentacji innych niż reprezentacja tożsamości, aby były zerowe. Prawdopodobieństwa powinny być tak dobrane, aby przynajmniej niektóre macierze były osobliwe. Macierze dla każdej reprezentacji mają różne wektory własne, więc nie jest jasne, który warunek wymusiłby określoną reprezentację na zero. (kont.)

p

$p$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

— Yuval Filmus

3

Gdybyśmy jednak mogli udowodnić, że każda transpozycja zmniejsza średnią rangę reprezentacji o najwyżej , powiedzmy, wówczas otrzymalibyśmy dolną granicę . Takie powiązanie można udowodnić, jeśli znamy wektory własne odpowiadające każdej reprezentacji i każdej transpozycji. Informacje te można zasadniczo opracować, ale nie ma pewności, że takie podejście przyniosłoby wszystko, co nie jest trywialne.

1 / n^{2}

$1/n^2$

n^{2}

$n^2$

— Yuval Filmus

1

(cd.) i ta transformacja liniowa jest dokładnie macierzą powstającą w reprezentacji S_n przez n × n macierzy permutacyjnych. Chociaż n-1 jest trywialne jako dolna granica liczby bramek (argument entropii już daje lepszą dolną granicę), mam nadzieję, że możliwe będzie uogólnienie twojego argumentu na inne reprezentacje, aby uzyskać lepszą dolną granicę całkowita liczba bramek.

— Tsuyoshi Ito,

4

@Yuval, @Peter: Zauważyłem, że dla każdej reprezentacji (1 − p) I + pA_ {ij} nie jest jednostkowa, chyba że p = 1/2 (ponieważ A_ {ij} ^ 2 = sugeruje, że wartości własne A_ {ij } to ± 1). Dlatego liczenie rang jest przydatne tylko w przypadku ograniczania liczby bramek prawdopodobieństwa 1/2, co zostało już optymalnie wykonane przez Piotra. Innymi słowy, jeśli teoria reprezentacji jest przydatna w sposób, który zasugerowałem w tym poście, potrzebujemy czegoś innego niż zliczanie rang macierzy! Nie jestem pewien, czy to jest realistyczne.

— Tsuyoshi Ito,

1

Algorytm Anthony'ego można uruchomić równolegle, rozpoczynając następną iterację procedury po pierwszych dwóch probabilistycznych zamianach, co daje czas działania . $O(n^2)$ $O(n)$

— Dave
źródło

4

Myślę, że miarą złożoności tego pytania jest liczba bramek, a nie czas działania.

— Anthony Leverrier,

3

@Anthony ma rację, że interesuje mnie po prostu minimalna liczba niezbędnych bramek.

— Joe Fitzsimons,

0

Jeśli dobrze rozumiem, jeśli chcesz, aby Twój obwód mógł generować wszystkie permutacje, potrzebujesz co najmniej probabilistycznych bramek, chociaż nie jestem pewien, jak można zbudować obwód minimalny. $\lceil \log_2(n!) \rceil$

AKTUALIZACJA:

Myślę, że jeśli weźmiesz algorytm Mergesort i zastąpisz wszystkie porównania przypadkowymi wyborami o odpowiednich prawdopodobieństwach, otrzymasz obwód, którego szukasz.

— Antonio Valerio Miceli-Barone
źródło

2

Nie jestem do końca pewien, jak przełożyłbyś to na model probabilitycznej bramki wymiany, którą podałem powyżej. Nie widzę, jak zamiana probabilistyczna zastępuje porównanie i nadal osiąga rozkład losowy. Dlatego też nie jestem pewien, dlaczego byłoby to optymalne.

— Joe Fitzsimons,

1

I tak, jest minimum, ale jest to tylko .

⌈ \log_{2} (n!) ⌉

$\lceil \log_2(n!) \rceil$

O (n \log (n))

$O(n\log(n))$

— Joe Fitzsimons,

1

Załóżmy, że i kontynuuj indukcję na . Masz dwie losowe kombinacje długości . Jeśli scalisz je losowo (tzn. Weź następny element z losowo wybranej subpermutacji), połączone wyniki z pewnością powinny być losowe. Prawdopodobieństwo, że pozycja mieć element z „lewego” podprądu, jest wyraźnie równe 1/2 symetrii. I pod warunkiem, że ma element z lewej subpermutacji, musi mieć z niego jednakowo losowy element. W ten sposób możesz zobaczyć, że wynikowa permutacja jest rzeczywiście losowa.

n = 2^{k}

$n=2^k$

k

$k$

2^{k - 1}

$2^{k-1}$

i

$i$

— Andrew D. King,

1

Tak też myślałem, gdy zaproponowałem połączenie, jednak po zastanowieniu wydaje mi się, że operacja scalania może nie być możliwa przy użyciu tylko wymaganego typu bramek, ponieważ nie dają one wyniku aby powiedzieć, czy wykonali permutację i nie mają żadnych danych sterujących, aby je uwarunkować.

— Antonio Valerio Miceli-Barone

3

@Andrew: Nie widzę, jak „scalić je losowo” za pomocą bram opisanych w pytaniu.

— Joe Fitzsimons,

0

Następująca odpowiedź jest błędna (patrz komentarz @joe fitzsimon), ale może być przydatna jako punkt wyjścia

Mam propozycję szkicu w . Sprawdziłem ręcznie, czy działa dla (!), Ale nie mam jeszcze dowodu, że wynik jest jednolity powyżej . $O(n\log n)$ $n=4$ $n=4$

Załóżmy, że masz obwód który generuje jednolitą losową permutację na bitach. Les probabilistyczny bramy wymiany który zamienia bity i z prawdopodobieństwem 1/2 i robi nic z prawdopodobieństwem . Skonstruuj następujący obwód działający na bitach: $C_n$ $n$ $S_{i,j}^{\frac 12}$ $i$ $j$ $1/2$ $C_{2n}$ $2n$

$\forall 1\le k\le n$ , zastosuj bramkę ; $S_{k,k+n}^{1/2}$
Zastosuj na pierwszych bitach; $C_n$ $n$
Zastosuj na ostatnich bitach; $C_n$ $n$
$\forall 1\le k\le n$ , zastosuj bramkę . $S_{k,k+n}^{1/2}$

Krok 1 jest potrzebny, aby bity i mogły wylądować w tej samej połowie permutacji, a krok 4 jest potrzebny symetrii: jeśli jest rozwiązaniem, to też uzyskane przez zastosowanie bramek w odwrotnej kolejności jest również rozwiązaniem. $1$ $n+1$ $C_{2n}$ $C_{2n}^-1$

Rozmiar tej rodziny obwodów jest zgodny z następującą relacją rekurencyjną: z, oczywiście, . Łatwo zauważyć, że .

| C_{2 n} | = 2 | C_{n} | + 2 n

$|C_{2n}| = 2|C_n|+2n$

| C_{1} | = 0

$|C_1|=0$

| C_{n} | = n \log n

$|C_n|=n\log n$

Pozostaje zatem oczywiste pytanie: czy te obwody wykonują jednolite permutacje? Nie, patrz pierwszy komentarz poniżej

— Frédéric Grosshans
źródło

6

Nie wierzę, że wykonują one jednolite permutacje. W rzeczywistości uważam, że nie da się zrobić dokładnie z takimi bramkami, jeśli ustalimy prawdopodobieństwo na 1/2. Powód tego jest prosty: wyobraź sobie obwód, który wykorzystuje takich bram. Następnie istnieją obliczenia ścieżki obliczeniowe, więc każda permutacja musi wystąpić z prawdopodobieństwem dla pewnej liczby całkowitej . Jednak dla równomiernego rozkładu wymagamy, aby . Oczywiście nie można tego spełnić dla wartości całkowitej dla .

m

$m$

2^{m}

$2^{m}$

k 2^{- m}

$k 2^{-m}$

k

$k$

k 2^{- m} = \frac{1}{n!}

$k 2^{-m} = \frac{1}{n!}$

k

$k$

n \geq 3

$n\geq 3$

— Joe Fitzsimons,

W rzeczy samej. Zapomniałem też sprawdzić jednolitość dla ...

n = 4

$n=4$

— Frédéric Grosshans