Випадкова перестановка

Випадкова перестановка — це випадкове впорядкування множини об'єктів, тобто випадкова величина, елементарними подіями якої є перестановки. Випадкові перестановки часто застосовують у галузях, які використовують увипадковлені алгоритми: теорії кодування, криптографії, моделюванні тощо. Прикладом випадкової перестановки є тасування колоди карт.

Генерування випадкових перестановок

Прямий метод (елемент за елементом)

Одним з методів генерування випадкової перестановки множини з ${\displaystyle n}$ елементів є використання рівномірного розподілу, для чого вибирають послідовно випадкові числа між 1 і ${\displaystyle n}$, забезпечуючи при цьому відсутність повторень. Отримана послідовність ${\displaystyle (x_{1},\cdots ,x_{n})}$ інтерпретується як перестановка

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},}$

Прямий метод генерування вимагає повторення вибору випадкового числа, якщо число, що випало, вже є в послідовності. Цього можна уникнути, якщо на ${\displaystyle i}$-му кроці (коли ${\displaystyle x_{1},\cdots ,x_{i-1}}$ вже вибрано), вибирати випадкове число ${\displaystyle j}$ між 1 і ${\displaystyle n-i+1}$ і, потім, вибирати ${\displaystyle x_{i}}$ рівним ${\displaystyle j}$-му невибраному числу.

Тасування Кнута

Простий алгоритм генерування випадкових перестановок з ${\displaystyle n}$ елементів (із рівномірним розподілом) без повторів, відомий як тасування Кнута, починається з довільної перестановки (наприклад, з тотожної — без переставляння елементів), і проходить з позиції 1 до позиції ${\displaystyle n-1}$, переставляючи елемент на позиції ${\displaystyle i}$ з випадково вибраним елементом на позиціях від ${\displaystyle i}$ до ${\displaystyle n}$ включно. Легко показати, що в такий спосіб ми отримаємо всі перестановки ${\displaystyle n}$ елементів зі ймовірністю рівно ${\displaystyle 1/n!}$.

Статистика на випадкових перестановках

Нерухомі точки

Розподіл імовірностей числа нерухомих точок у рівномірно розподілених випадкових перестановках на ${\displaystyle n}$ елементах, у разі зростання ${\displaystyle n}$ , наближається до закону Пуассона. Підрахунок числа нерухомих точок є класичним прикладом використання формули включень-виключень, яка показує, що ймовірність відсутності нерухомих точок наближається до ${\displaystyle 1/e}$. При цьому математичне сподівання числа нерухомих точок дорівнює 1 за будь-якого розміру перестановки.

Перевірка випадковості

Як і у всіх інших випадкових процесах, якість алгоритму генерування перестановок, зокрема алгоритму тасування Кнута, залежить від покладеного в основу генератора випадкових чисел, такого як генератор псевдовипадкових чисел. Є багато можливих тестів випадковості, наприклад, тести diehard. Типовий приклад такого тесту полягає у виборі деякої статистики, для якої розподіл відомий, і перевірці, чи дійсно розподіл цієї статистики на множині отриманих перестановок достатньо близький до цього розподілу.

Див. також

• Константа Голомба — Дікмана
• Перестановка
• Псевдовипадкова перестановка