What distribution do you get from this broken random shuffle?

by

An Empirical Approach.

Let’s implement the erroneous algorithm in 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];
]

Now get the number of times each integer is in each position: 

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

Let’s take three positions in the resulting arrays and plot the frequency distribution for each integer in that position:

For position 1 the freq distribution is:

enter image description here

For position 5 (middle)

enter image description here

And for position 10 (last):

enter image description here

and here you have the distribution for all positions plotted together:

enter image description here

Here you have a better statistics over 8 positions:

enter image description here

Some observations:

  • For all positions the probability of
    “1” is the same (1/n).
  • The probability matrix is symmetrical
    with respect to the big anti-diagonal
  • So, the probability for any number in the last
    position is also uniform (1/n)

You may visualize those properties looking at the starting of all lines from the same point (first property) and the last horizontal line (third property).

The second property can be seen from the following matrix representation example, where the rows are the positions, the columns are the occupant number, and the color represents the experimental probability:

enter image description here

For a 100×100 matrix:

enter image description here

Edit

Just for fun, I calculated the exact formula for the second diagonal element (the first is 1/n). The rest can be done, but it’s a lot of work. 

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

Values verified from n=3 to 6 ( {8/27, 57/256, 564/3125, 7105/46656} )

Edit

Working out a little the general explicit calculation in @wnoise answer, we can get a little more info.

Replacing 1/n by p[n], so the calculations are hold unevaluated, we get for example for the first part of the matrix with n=7 (click to see a bigger image):

enter image description here

Which, after comparing with results for other values of n, let us identify some known integer sequences in the matrix: 

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

You may find those sequences (in some cases with different signs) in the wonderful http://oeis.org/

Solving the general problem is more difficult, but I hope this is a start

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Generating shuffled range using a PRNG rather than shuffling
  3. Custom Weighted Scale [closed]
  4. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  5. Select k random elements from a list whose elements have weights
  6. Data structures for loaded dice?
  7. Pseudorandom Number Generator – Exponential Distribution
  8. Choosing n numbers with fixed sum
  9. Need help in mod 1000000007 questions
  10. Shuffle list, ensuring that no item remains in same position
  11. What is the fastest integer factorization algorithm?
  12. Why does this simple shuffle algorithm produce biased results?
  13. True random number generator [closed]
  14. Modulus power of big numbers
  15. Puzzle: Find largest rectangle (maximal rectangle problem)
  16. Calculate largest inscribed rectangle in a rotated rectangle
  17. The Sieve of Atkin
  18. How do I find a factorial? [closed]
  19. How do I determine whether my calculation of pi is accurate?
  20. “Rounding” colour values to the nearest of a small set of colours
  21. Randomly choosing from a list with weighted probabilities
  22. How do I calculate a point on a circle’s circumference?
  23. Fast permutation -> number -> permutation mapping algorithms
  24. Algorithm to detect intersection of two rectangles?
  25. What algorithm gives suggestions in a spell checker?
  26. Precise subpixel line drawing algorithm (rasterization algorithm)
  27. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  28. nᵗʰ ugly number
  29. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  30. Optimized low-accuracy approximation to `rootn(x, n)`

Leave a Comment