CS
Problems Base course RU

Problem

The unfair shuffle

random numbers probabilistic dynamic programming

The first version of shuffling on an old game server went like this: for each place i = 1, 2, …, n, choose a place j with equal probability from all n and swap the cards in places i and j. It looks like a fair shuffle but is not one: the nn equally likely chains of choices do not split evenly among the n! arrangements.

How large is the skew? At first card k lies in place k. For each question “a b”, find the probability that the card that lay in place a ends up in place b after shuffling, and print it multiplied by n: for a fair shuffle this would be exactly 1.

Input

The first line holds n and the number of questions q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5). Then q lines of two numbers a and b (1 ≤ a, b ≤ n).

Output

For each question, n·P(a → b) with an absolute or relative error of at most 10−6.

Examples

Example 1

Input
3 4
1 1
2 1
3 1
2 2
Output
1.000000000
1.111111111
0.888888889
0.888888889

Example 2

Input
52 4
2 1
52 1
1 52
52 52
Output
1.352226153
0.742913844
1.000000000
1.000000000

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

There is no need to go through all nn chains. It is enough to follow one card: in which place it may be after each step and with what probability.

2Hint 2

Write out one step k: what happens to the probability “the card is in place k” and to the probability “the card is in place p ≠ k”? The first is always the same after the step.

3The idea

Let d[p] be the probability that our card is in place p, and q = 1 − 1/n. Step k swaps place k with a random place. The card from place k goes to any place, and any card comes to place k, so after the step d[k] = 1/n. A card from place p ≠ k goes to k with probability 1/n, and comes from k to p also with probability 1/n: d[p] ← q·d[p] + d[k]/n. Over n steps of n places this gives O(n2), too much for 105. But a question needs only d[b] at the end, and that needs only the values of d[k] at the moments of steps k.

4Walkthrough

Denote by sk the probability that the card is in place k just before step k (places from zero). Before step k, place k was changed only by steps j < k, each by the rule for p ≠ j, so

$$s_k = [k = a]\,q^k + \sum_{j<k} \frac{s_j}{n}\, q^{\,k-1-j}.$$

The sum need not be recomputed from scratch: it is a running total T, which at each step is multiplied by q and gains the term sk. The same goes for place b: at step b its probability becomes 1/n, and at each later step k, q·d[b] + sk/n. One pass over the steps, and the answer is ready.

Check on three cards. There are 33 = 27 chains, and card 2 ends up in first place in 10 of them, when it should in 9: n·P = 10/9 ≈ 1.111. Card 3 in 8 chains: 8/9. Card 1 in exactly 9: at the first step it goes to a random place, and after that everything is symmetric. In a 52-card deck the second card reaches the top 35% more often than fair, and the last one 26% less often. The whole matrix of such probabilities is in the second scene of the article on shuffling.

Two cards are a special case: “swap with any” on two places is fair, the 22 = 4 chains split evenly into 2! = 2 arrangements. The skew starts with three cards: n − 1 divides n! but has no common divisors with nn.

4+Solution
5Complexity

O(n) time per question and O(1) memory: one pass over the steps with two running numbers.

6Common mistakes
  • Assuming the shuffle is fair. Answering 1 to everything is wrong already on the first example.
  • Simulating. A million random shuffles give an answer with an error of about 10−3, while 10−6 is needed: that would take a trillion shuffles.
  • The whole matrix. The probabilities of all cards in all places are O(n2) per card and O(n3) for all. One question needs one card and one place.
  • Getting the order wrong. Place b gets 1/n at its own step and changes only at later ones; the steps before b affect the answer only through sk.

Algorithms behind it

SRT Algorithm The Fisher–Yates shuffle A fair random permutation in O(n): each of the n! with probability 1/n!, and why “swap with any” is unfair. O(n) 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems
The algorithms catalogue