이 셔플 링 알고리즘에 어떤 문제가 있으며 어떻게 알 수 있습니까?

이 셔플 링 알고리즘에 어떤 문제가 있으며 어떻게 알 수 있습니까?

---

배경으로 나는 Fisher-Yates 완벽한 셔플을 알고 있습니다. 그것은 O (n) 복잡성과 보장 된 균일 성을 가진 큰 셔플이며, 나는 그것을 사용하지 않는 것은 바보가 될 것입니다 ... 배열의 내부 업데이트를 허용하는 환경에서 (그래서 전부는 아니지만, 명령형 프로그래밍 환경).

슬프게도 함수형 프로그래밍 세계는 변경 가능한 상태에 대한 액세스 권한을 제공하지 않습니다.

그러나 Fisher-Yates 때문에 셔플 링 알고리즘을 설계하는 방법에 대해 찾을 수있는 문헌이 많지 않습니다. 이 문제를 해결하는 몇 안되는 곳에서는 실제로 "피셔-예이츠가 여러분이 알아야 할 모든 셔플 링입니다"라고 말하기 전에 간단히 그렇게합니다. 결국 나는 내 자신의 해결책을 찾아야했다.

내가 생각해 낸 솔루션은 데이터 목록을 섞기 위해 다음과 같이 작동합니다.

• 목록이 비어 있으면 빈 집합을 반환합니다.
• 목록에 단일 항목이있는 경우 해당 단일 항목을 반환합니다.
• 목록이 비어 있지 않으면 난수 생성기로 목록을 분할하고 알고리즘을 각 분할에 반복적으로 적용하여 결과를 조합합니다.

Erlang 코드에서는 다음과 같습니다.

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(이것이 어리석은 빠른 정렬처럼 보이면 기본적으로 그게 다입니다.)

그래서 여기에 내 문제가 있습니다. Fisher-Yates가 아닌 셔플 링 알고리즘을 찾는 것을 어렵게 만드는 동일한 상황은 셔플 링 알고리즘을 분석 하는 도구를 찾는 것을 똑같이 어렵게 만듭니다. 균일 성, 주기성 등을 위해 PRNG를 분석하는 데 대한 문헌은 많이 있지만 셔플을 분석하는 방법에 대한 정보는 많지 않습니다. (실제로 내가 셔플을 분석하면서 찾은 정보 중 일부는 단순한 기술을 통해 쉽게 속이는 잘못된 정보였습니다.)

그래서 내 질문은 이것입니다 : 내 셔플 링 알고리즘을 어떻게 분석합니까 ( random:uniform()좋은 특성을 가진 적절한 난수를 생성하는 작업에 달려 있다고 가정 )? 1..100 범위의 정수 목록에서 10 만 번의 셔플 실행이 나에게 그럴듯하게 좋은 셔플 링 결과를 제공했는지 여부를 판단 할 수있는 수학적 도구는 무엇입니까? 몇 가지 테스트를 수행했지만 (예를 들어 셔플의 증가와 감소 비교) 몇 가지 더 알고 싶습니다.

그리고 그 셔플 알고리즘 자체에 대한 통찰력이 있다면 감사 할 것입니다.

---

일반 비고

확률 사용 알고리즘의 정확성에 대한 나의 개인적인 접근 방식 : 그것이 옳다는 것을 증명 하는 방법을 안다면 아마 정확할 것입니다. 그렇지 않으면 확실히 잘못된 것입니다.

다르게 말하면, 일반적으로 당신이 생각 해낼 수있는 모든 알고리즘을 분석하는 것은 희망이 없습니다. 당신이 옳다고 증명할 수 있는 알고리즘을 찾을 때까지 알고리즘을 계속 찾아야 합니다.

분포를 계산하여 무작위 알고리즘 분석

나는 단순한 "많은 테스트를 던져 균일 성을 확인"하는 것보다 더 강력한 셔플 (또는보다 일반적으로 무작위 사용 알고리즘)을 "자동으로"분석하는 한 가지 방법을 알고 있습니다. 알고리즘의 각 입력과 관련된 분포를 기계적으로 계산할 수 있습니다.

일반적인 아이디어는 무작위 사용 알고리즘이 가능성 세계의 일부를 탐색한다는 것입니다. 알고리즘이 세트에서 임의의 요소를 요청할 때마다 ( 코인을 뒤집을 때 { true, false}) 알고리즘에 대해 두 가지 가능한 결과가 있으며 그중 하나가 선택됩니다. 가능한 결과 중 하나를 반환하는 대신 모든 솔루션을 병렬로 탐색 하고 관련된 분포와 함께 가능한 모든 결과를 반환하도록 알고리즘을 변경할 수 있습니다 .

일반적으로 알고리즘을 심층적으로 다시 작성해야합니다. 사용하는 언어가 구분 된 연속을 지원하는 경우에는 그럴 필요가 없습니다. 함수 내에서 임의의 요소를 요청하는 "가능한 모든 결과 탐색"을 구현할 수 있습니다 (이 아이디어는 결과를 반환하는 대신 임의 생성기가 프로그램과 관련된 연속을 캡처하고 모든 다른 결과로 실행하는 것입니다). 이 접근 방식의 예는 oleg의 HANSEI를 참조하십시오 .

중개적이고 덜 신비한 해결책은이 "가능한 결과의 세계"를 모나드로 표현하고 모나드 프로그래밍을위한 기능과 함께 Haskell과 같은 언어를 사용하는 것입니다. 다음은 확률 패키지 의 확률 모나드를 사용하여 Haskell에서 알고리즘 변형 ¹을 구현 한 예입니다 .

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

주어진 입력에 대해 실행하고 출력 분포를 얻을 수 있습니다.

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

이 알고리즘은 크기 2의 입력에 대해 균일하지만 크기 3의 입력에 대해서는 균일하지 않음을 알 수 있습니다.

테스트 기반 접근 방식과의 차이점은 제한된 수의 단계에서 절대적인 확실성을 얻을 수 있다는 것입니다. 가능한 세계에 대한 철저한 탐색에 해당하므로 상당히 클 수 있습니다 (그러나 일반적으로 2 ^ N보다 작습니다. 유사한 결과의 인수 분해가 있습니다.)하지만 균일하지 않은 분포를 반환하면 알고리즘이 잘못되었음을 확실히 알 수 있습니다. 물론 [1..N]및에 대해 균일 한 분포를 반환하는 경우 1 <= N <= 100알고리즘이 크기가 100 인 목록까지 균일하다는 것을 알 수 있습니다. 여전히 잘못되었을 수 있습니다.

¹ :이 알고리즘은 특정 피벗 처리로 인해 Erlang 구현의 변형입니다. 귀하의 경우와 같이 피벗을 사용하지 않으면 입력 크기가 더 이상 각 단계에서 감소하지 않습니다. 알고리즘은 모든 입력이 왼쪽 목록 (또는 오른쪽 목록)에 있고 무한 루프에서 손실되는 경우도 고려합니다. . 이것은 확률 모나드 구현의 약점입니다 (알고리즘이 종료되지 않을 확률이 0 인 경우 분포 계산이 여전히 발산 할 수 있음). 아직 해결 방법을 모릅니다.

정렬 기반 셔플

다음은 내가 옳다는 것을 증명할 수 있다고 확신하는 간단한 알고리즘입니다.

1. 컬렉션의 각 요소에 대해 임의의 키를 선택하십시오.
2. 키가 모두 구별되지 않으면 1 단계부터 다시 시작하십시오.
3. 이 임의의 키로 컬렉션을 정렬합니다.

충돌 확률 (선택된 두 개의 난수가 동일 함)이 충분히 낮다는 것을 알고 있으면 2 단계를 생략 할 수 있지만, 충돌이 없으면 셔플이 완벽하게 균일하지 않습니다.

N이 컬렉션의 길이 인 [1..N]에서 키를 선택하면 충돌이 많이 발생합니다 ( Birthday problem ). 키를 32 비트 정수로 선택하면 실제로 충돌 가능성이 낮지 만 여전히 생일 문제가 발생할 수 있습니다.

유한 길이 키가 아닌 무한 (지연 적으로 평가 된) 비트 문자열을 키로 사용하는 경우 충돌 확률은 0이되고 더 이상 구별 여부를 확인할 필요가 없습니다.

다음은 지연 실수를 무한 비트 문자열로 사용하는 OCaml의 셔플 구현입니다.

type 'a stream = Cons of 'a * 'a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
    compare_real a' b'

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

There are other approaches to "pure shuffling". A nice one is apfelmus's mergesort-based solution.

Algorithmic considerations: the complexity of the previous algorithm depends on the probability that all keys are distinct. If you pick them as 32-bit integers, you have a one in ~4 billion probability that a particular key collides with another key. Sorting by these keys is O(n log n), assuming picking a random number is O(1).

If you infinite bitstrings, you never have to restart picking, but the complexity is then related to "how many elements of the streams are evaluated on average". I conjecture it is O(log n) in average (hence still O(n log n) in total), but have no proof.

... and I think your algorithm works

After more reflexion, I think (like douplep), that your implementation is correct. Here is an informal explanation.

Each element in your list is tested by several random:uniform() < 0.5 tests. To an element, you can associate the list of outcomes of those tests, as a list of booleans or {0, 1}. At the beginning of the algorithm, you don't know the list associated to any of those number. After the first partition call, you know the first element of each list, etc. When your algorithm returns, the list of tests are completely known and the elements are sorted according to those lists (sorted in lexicographic order, or considered as binary representations of real numbers).

So, your algorithm is equivalent to sorting by infinite bitstring keys. The action of partitioning the list, reminiscent of quicksort's partition over a pivot element, is actually a way of separating, for a given position in the bitstring, the elements with valuation 0 from the elements with valuation 1.

The sort is uniform because the bitstrings are all different. Indeed, two elements with real numbers equal up to the n-th bit are on the same side of a partition occurring during a recursive shuffle call of depth n. The algorithm only terminates when all the lists resulting from partitions are empty or singletons : all elements have been separated by at least one test, and therefore have one distinct binary decimal.

Probabilistic termination

A subtle point about your algorithm (or my equivalent sort-based method) is that the termination condition is probabilistic. Fisher-Yates always terminates after a known number of steps (the number of elements in the array). With your algorithm, the termination depends on the output of the random number generator.

There are possible outputs that would make your algorithm diverge, not terminate. For example, if the random number generator always output 0, each partition call will return the input list unchanged, on which you recursively call the shuffle : you will loop indefinitely.

However, this is not an issue if you're confident that your random number generator is fair : it does not cheat and always return independent uniformly distributed results. In that case, the probability that the test random:uniform() < 0.5 always returns true (or false) is exactly 0 :

• the probability that the first N calls return true is 2^{-N}
• the probability that all calls return true is the probability of the infinite intersection, for all N, of the event that the first N calls return 0; it is the infimum limit¹ of the 2^{-N}, which is 0

¹: for the mathematical details, see http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

More generally, the algorithm does not terminate if and only if some of the elements get associated to the same boolean stream. This means that at least two elements have the same boolean stream. But the probability that two random boolean streams are equal is again 0 : the probability that the digits at position K are equal is 1/2, so the probability that the N first digits are equal is 2^{-N}, and the same analysis applies.

Therefore, you know that your algorithm terminates with probability 1. This is a slightly weaker guarantee that the Fisher-Yates algorithm, which always terminate. In particular, you're vulnerable to an attack of an evil adversary that would control your random number generator.

With more probability theory, you could also compute the distribution of running times of your algorithm for a given input length. This is beyond my technical abilities, but I assume it's good : I suppose that you only need to look at O(log N) first digits on average to check that all N lazy streams are different, and that the probability of much higher running times decrease exponentially.

---

Your algorithm is a sort-based shuffle, as discussed in the Wikipedia article.

Generally speaking, the computational complexity of sort-based shuffles is the same as the underlying sort algorithm (e.g. O(n log n) average, O(n²) worst case for a quicksort-based shuffle), and while the distribution is not perfectly uniform, it should approach uniform close enough for most practical purposes.

Oleg Kiselyov provides the following article / discussion:

• Provably perfect random shuffling and its pure functional implementations

which covers the limitations of sort-based shuffles in more detail, and also offers two adaptations of the Fischer–Yates strategy: a naive O(n²) one, and a binary-tree-based O(n log n) one.

Sadly the functional programming world doesn't give you access to mutable state.

This is not true: while purely functional programming avoids side effects, it supports access to mutable state with first-class effects, without requiring side effects.

In this case, you can use Haskell's mutable arrays to implement the mutating Fischer–Yates algorithm as described in this tutorial:

• Haskell Shuffling (Brett Hall)

Addendum

The specific foundation of your shuffle sort is actually an infinite-key radix sort: as gasche points out, each partition corresponds to a digit grouping.

The main disadvantage of this is the same as any other infinite-key sorting shuffle: there is no termination guarantee. Although the likelihood of termination increases as the comparison proceeds, there is never an upper bound: the worst-case complexity is O(∞).

---

I was doing some stuff similar to this a while ago, and in particular you might be interested in Clojure's vectors, which are functional and immutable but still with O(1) random access/update characteristics. These two gists have several implementations of a "take N elements at random from this M-sized list"; at least one of them turns into a functional implementation of Fisher-Yates if you let N=M.

https://gist.github.com/805546

https://gist.github.com/805747

---

Based on How to test randomness (case in point - Shuffling) , I propose:

Shuffle (medium sized) arrays composed of equal numbers of zeroes and ones. Repeat and concatenate until bored. Use these as input to the diehard tests. If you have a good shuffle, then you should be generating random sequences of zeroes and ones (with the caveat that the cumulative excess of zeroes (or ones) is zero at the boundaries of the medium sized arrays, which you would hope the tests detect, but the larger "medium" is the less likely they are to do so).

Note that a test can reject your shuffle for three reasons:

• the shuffle algorithm is bad,
• the random number generator used by the shuffler or during initialization is bad, or
• the test implementation is bad.

You'll have to resolve which is the case if any test rejects.

Various adaptations of the diehard tests (to resolve certain numbers, I used the source from the diehard page). The principle mechanism of adaptation is to make the shuffle algorithm act as a source of uniformly distributed random bits.

• Birthday spacings: In an array of n zeroes, insert log n ones. Shuffle. Repeat until bored. Construct the distribution of inter-one distances, compare with the exponential distribution. You should perform this experiment with different initialization strategies -- the ones at the front, the ones at the end, the ones together in the middle, the ones scattered at random. (The latter has the greatest hazard of a bad initialization randomization (with respect to the shuffling randomization) yielding rejection of the shuffling.) This can actually be done with blocks of identical values, but has the problem that it introduces correlation in the distributions (a one and a two can't be at the same location in a single shuffle).
• Overlapping permutations: shuffle five values a bunch of times. Verify that the 120 outcomes are about equally likely. (Chi-squared test, 119 degrees of freedom -- the diehard test (cdoperm5.c) uses 99 degrees of freedom, but this is (mostly) an artifact of sequential correlation caused by using overlapping subsequences of the input sequence.)
• Ranks of matrices: from 2*(6*8)^2 = 4608 bits from shuffling equal numbers of zeroes and ones, select 6 non-overlapping 8-bit substrings. Treat these as a 6-by-8 binary matrix and compute its rank. Repeat for 100,000 matrices. (Pool together ranks of 0-4. Ranks are then either 6, 5, or 0-4.) The expected fraction of ranks is 0.773118, 0.217439, 0.009443. Chi-squared compare with observed fractions with two degrees of freedom. The 31-by-31 and 32-by-32 tests are similar. Ranks of 0-28 and 0-29 are pooled, respectively. Expected fractions are 0.2887880952, 0.5775761902, 0.1283502644, 0.0052854502. Chi-squared test has three degrees of freedom.

and so on...

You may also wish to leverage dieharder and/or ent to make similar adapted tests.

참고 URL : https://stackoverflow.com/questions/3944556/what-if-anything-is-wrong-with-this-shuffling-algorithm-and-how-can-i-know