이 깨진 무작위 셔플에서 어떤 분포를 얻습니까?

이 깨진 무작위 셔플에서 어떤 분포를 얻습니까?

---

유명한 Fisher-Yates 셔플 알고리즘을 사용하여 길이가 N 인 배열 A를 무작위로 순회 할 수 있습니다.

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

내가하지 말라고 반복해서 들었던 일반적인 실수는 다음과 같습니다.

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

즉, k에서 N까지의 임의의 정수를 선택하는 대신 1에서 N까지의 임의의 정수를 선택합니다.

이 실수를하면 어떻게 되나요? 나는 결과 순열이 균일하게 분포되지 않는다는 것을 알고 있지만 결과 분포가 무엇인지에 대한 보장이 무엇인지 모르겠습니다. 특히, 요소의 최종 위치에 대한 확률 분포에 대한 표현이있는 사람이 있습니까?

---

경험적 접근.

Mathematica에서 잘못된 알고리즘을 구현해 보겠습니다.

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

이제 각 정수가 각 위치에있는 횟수를 구하십시오.

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

결과 배열에서 세 위치를 취하고 해당 위치의 각 정수에 대한 빈도 분포를 플로팅합니다.

위치 1의 경우 주파수 분포는 다음과 같습니다.

위치 5 (중간)

그리고 위치 10 (마지막)의 경우 :

여기에 모든 위치에 대한 분포가 함께 표시됩니다.

여기에 8 개 위치에 대한 더 나은 통계가 있습니다.

일부 관찰 :

• 모든 위치에서 "1"의 확률은 동일합니다 (1 / n).
• 확률 행렬은 큰 대각선에 대해 대칭입니다.
• 따라서 마지막 위치의 숫자에 대한 확률도 균일합니다 (1 / n).

동일한 지점 (첫 번째 속성)과 마지막 수평선 (세 번째 속성)에서 모든 선의 시작을보고 이러한 속성을 시각화 할 수 있습니다.

두 번째 속성은 행이 위치, 열이 점유자 번호, 색상이 실험 확률을 나타내는 다음 행렬 표현 예제에서 볼 수 있습니다.

100x100 매트릭스의 경우 :

편집하다

재미를 위해 두 번째 대각선 요소에 대한 정확한 공식을 계산했습니다 (첫 번째는 1 / n). 나머지는 할 수 있지만 많은 작업이 필요합니다.

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

n = 3에서 6까지 확인 된 값 ({8/27, 57/256, 564/3125, 7105/46656})

편집하다

@wnoise 대답에서 일반적인 명시 적 계산을 조금 수행하면 조금 더 많은 정보를 얻을 수 있습니다.

1 / n을 p [n]으로 바꾸면 계산이 평가되지 않은 상태로 유지됩니다. 예를 들어 n = 7 인 행렬의 첫 번째 부분이 표시됩니다 (더 큰 이미지를 보려면 클릭).

n의 다른 값에 대한 결과와 비교 한 후 행렬에서 알려진 정수 시퀀스를 식별 해 보겠습니다.

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

멋진 http://oeis.org/ 에서 이러한 시퀀스 (경우에 따라 다른 기호가있는 경우)를 찾을 수 있습니다.

일반적인 문제를 해결하는 것이 더 어렵지만 이것이 시작이기를 바랍니다

---

당신이 언급 한 "일반적인 실수"는 무작위 조옮김으로 뒤섞이는 것입니다. 이 문제는 Diaconis와 Shahshahani가 Genrating a random permutation with random transpositions (1981) 에서 자세히 연구했습니다 . 그들은 정지 시간과 균일성에 대한 수렴에 대한 완전한 분석을 수행합니다. 논문에 대한 링크를받을 수없는 경우 저에게 이메일을 보내 주시면 사본을 전달할 수 있습니다. 이것은 실제로 재미있는 읽기입니다 (대부분의 Persi Diaconis의 논문과 마찬가지로).

배열에 반복되는 항목이 있으면 문제가 약간 다릅니다. 뻔뻔한 플러그로서,이보다 일반적인 문제는 A Rule of Thumb for Riffle Shuffling (2011)의 부록 B에서 나 자신, Diaconis 및 Soundararajan에 의해 해결되었습니다 .

---

의 말을하자

• a = 1/N
• b = 1-a
• B _i (k)는 th 요소를 i교체 한 후의 확률 행렬 k입니다. 즉, " 스왑 k후 어디에 i있습니까?"라는 질문에 대한 대답 입니다. 예를 들어 B ₀ (3) = (0 0 1 0 ... 0)및 B ₁ (3) = (a 0 b 0 ... 0). 당신이 원하는 것은 모든 k에 대한 B _N (k)입니다.
• K _i 는 i 번째 열과 i 번째 행에 1이있는 NxN 행렬이고 다른 모든 곳은 0입니다. 예 :

• I _i 는 단위 행렬이지만 x = y = i 요소가 0입니다. 예 : i = 2의 경우 :

• _난 입니다

그때,

그러나 B _N (k = 1..N)이 단위 행렬을 형성 하기 때문에 주어진 요소 i가 끝에 j 위치에있을 확률은 행렬의 행렬 요소 (i, j)에 의해 제공됩니다.

예를 들어 N = 4의 경우 :

N = 500에 대한 다이어그램 (색상 레벨은 100 * 확률 임) :

패턴은 모든 N> 2에 대해 동일합니다.

• k 번째 요소 의 가장 가능성있는 끝 위치 는 k-1 입니다.
• 적어도 가능성 종료 위치 를 k 에 대한 K <N * LN (2) , 위치 1 , 그렇지

---

이 질문을 전에 본 적이 있다는 것을 알고있었습니다

" 이 간단한 셔플 알고리즘이 편향된 결과를 생성하는 이유는 무엇입니까? 간단한 이유는 무엇입니까? "에는 답변, 특히 Jeff Atwood의 Coding Horror 블로그 링크가 포함되어 있습니다.

이미 짐작했듯이 @belisarius의 답변에 따르면 정확한 분포는 셔플 할 요소의 수에 따라 크게 달라집니다. 다음은 6 개 요소 덱에 대한 Atwood의 플롯입니다.

---

정말 멋진 질문입니다! 나는 완전한 대답을 얻었 으면한다.

Fisher-Yates는 첫 번째 요소를 결정한 후에는 그대로두기 때문에 분석하기에 좋습니다. 편향된 사람은 어떤 장소에서든 요소를 ​​반복적으로 교체 할 수 있습니다.

우리는 행동을 확률 분포에 선형 적으로 작용하는 확률 적 전이 행렬로 설명함으로써 Markov 체인과 동일한 방식으로이를 분석 할 수 있습니다. 대부분의 요소는 그대로두고 대각선은 일반적으로 (n-1) / n입니다. 패스 k에서 홀로 남겨지지 않으면 요소 k (또는 요소 k 인 경우 임의의 요소)로 교체됩니다. 이것은 행 또는 열 k에서 1 / (n-1)입니다. k 행과 열의 요소도 1 / (n-1)입니다. k가 1에서 n이되도록이 행렬을 곱하는 것은 쉽습니다.

마지막 패스가 마지막 장소를 다른 장소와 똑같이 교체하기 때문에 마지막 장소의 요소가 원래 어디에 있었을 가능성이 똑같다는 것을 알고 있습니다. 마찬가지로 첫 번째 요소는 어디에나 배치 될 가능성이 동일합니다. 이 대칭은 전치가 행렬 곱셈의 순서를 반대로하기 때문입니다. 실제로 행렬은 i 행이 열 (n + 1-i)과 동일하다는 점에서 대칭입니다. 그 외에도 숫자는 뚜렷한 패턴을 보이지 않습니다. 이러한 정확한 솔루션은 belisarius가 실행 한 시뮬레이션과 일치 함을 보여줍니다. 슬롯 i에서 j가 i로 상승하면 j를 얻을 확률이 감소하고 i-1에서 가장 낮은 값에 도달 한 다음 i에서 가장 높은 값으로 점프합니다. j가 n에 도달 할 때까지 감소합니다.

Mathematica에서는 각 단계를 다음과 같이 생성했습니다.

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(어디서도 문서화되지 않았지만 첫 번째 일치 규칙이 사용됩니다.) 최종 전환 행렬은 다음과 같이 계산할 수 있습니다.

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot 유용한 시각화 도구입니다.

편집 (by belisarius)

그냥 확인입니다. 다음 코드는 @Eelvex의 답변과 동일한 행렬을 제공합니다.

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

---

Fisher-Yates 셔플의 Wikipedia 페이지 에는이 경우에 일어날 일에 대한 설명과 예가 있습니다.

---

확률 행렬을 사용하여 분포를 계산할 수 있습니다 . 행렬 A (i, j)가 원래 위치 i에서 j 위치로 끝나는 카드의 확률을 설명하도록합니다. 그런 다음 k 번째 스왑은 Ak(i,j) = 1/Nif i == k또는 j == k, (위치 k의 카드는 어디에서나 끝날 수 있고 모든 카드는 같은 확률로 위치 k에 끝날 수 있음)에 의해 주어진 행렬 Ak Ak(i,i) = (N - 1)/N를 갖습니다. i != k(다른 모든 카드는 확률 (N-1) / N) 및 기타 모든 요소는 0입니다.

완전한 셔플의 결과는 행렬의 곱으로 제공됩니다 AN ... A1.

나는 당신이 확률에 대한 대수적 설명을 찾고 있다고 기대합니다. 위의 매트릭스 제품을 확장하여 하나를 얻을 수 있지만 상당히 복잡 할 것이라고 생각합니다!

업데이트 : 방금 위의 wnoise의 동등한 대답을 발견했습니다! 죄송합니다 ...

---

나는 이것을 더 자세히 조사했고,이 분포가 오랫동안 연구 된 것으로 밝혀졌습니다. 이것이 흥미로운 이유는이 "깨진"알고리즘이 RSA 칩 시스템에서 사용 되었기 때문입니다.

에서 셔플 반 임의 트랜스 토지 , Elchanan 모젤, 유발 페레스, 그리고 알리스 테어 싱클레어이와 셔플의보다 일반적인 클래스를 공부합니다. 그 논문의 결론은 log(n)거의 무작위 배포를 달성하기 위해 깨진 셔플 이 필요하다는 것 입니다.

에서는 세 개의 의사 랜덤 셔플의 바이어스 ( Aequationes Mathematicae , 22, 1981, 268-292), 이단 Bolker 데이비드 로빈스 매우 불가능하다는 것을 나타냄이 셔플을 분석하여 단일 패스 후 균일로 전체 변동 거리가 1 인 것으로 판단 전혀 무작위입니다. 무증상 분석도 제공합니다.

마지막으로 Laurent Saloff-Coste와 Jessica Zuniga는 이질적인 마르코프 사슬에 대한 연구에서 좋은 상한선을 발견했습니다.

---

이 질문은 언급 된 깨진 셔플 의 대화 형 시각적 매트릭스 다이어그램 분석을 구걸합니다 . 이러한 도구는 Will It Shuffle? 페이지에 있습니다 . -Mike Bostock 이 랜덤 비교기가 나쁜 이유 .

Bostock은 무작위 비교기를 분석하는 훌륭한 도구를 모았습니다. 해당 페이지의 드롭 다운에서 순진한 스왑 (랜덤 ↦ random) 을 선택하여 깨진 알고리즘과 생성되는 패턴을 확인합니다.

그의 페이지는 논리 변경이 셔플 된 데이터에 미치는 즉각적인 영향을 볼 수 있기 때문에 유익합니다. 예를 들면 :

비 균일하고 매우 편향된 셔플을 사용하는이 매트릭스 다이어그램은 다음과 같은 코드로 순진한 스왑 ( "1에서 N"까지 선택)을 사용하여 생성됩니다.

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

그러나 "k에서 N"으로 선택하는 편향되지 않은 셔플을 구현하면 다음과 같은 다이어그램이 표시됩니다.

분포가 균일하고 다음과 같은 코드에서 생성됩니다.

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

---

The excellent answers given so far are concentrating on the distribution, but you have asked also "What happens if you make this mistake?" - which is what I haven't seen answered yet, so I'll give an explanation on this:

The Knuth-Fisher-Yates shuffle algorithm picks 1 out of n elements, then 1 out of n-1 remaining elements and so forth.

You can implement it with two arrays a1 and a2 where you remove one element from a1 and insert it into a2, but the algorithm does it in place (which means, that it needs only one array), as is explained here (Google: "Shuffling Algorithms Fisher-Yates DataGenetics") very well.

요소를 제거하지 않으면 다시 무작위로 선택되어 편향된 임의성을 생성 할 수 있습니다. 이것이 당신이 설명하는 두 번째 예가하는 일입니다. 첫 번째 예인 Knuth-Fisher-Yates 알고리즘은 k에서 N까지 실행되는 커서 변수를 사용합니다.이 변수는 이미 가져온 요소를 기억하므로 요소를 두 번 이상 선택하지 않습니다.

참고 URL : https://stackoverflow.com/questions/5131341/what-distribution-do-you-get-from-this-broken-random-shuffle