التبديل العشوائي

تتمثل إحدى الخوارزميات لتوليد تبديل عشوائي لمجموعة بحجم n بشكل عشوائي منتظم ، أي بحيث يكون لكل تبديل من التبديلات n ! احتمال ظهور متساوٍ، في توليد متتالية عن طريق اختيار عدد صحيح عشوائيًا بشكل منتظم بين 1 و n (شاملًا)، بالتتابع ودون إرجاع n مرة، ثم تفسير هذه المتتالية ( x1 , ..., xn ₎ على أنها التبديل _.

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

موضح هنا بصيغة السطرين .

قد تقوم طريقة عشوائية غير فعالة لأخذ العينات دون إرجاع باختيار الأرقام بين 1 و n في كل خطوة، مع إعادة المحاولة كلما كان الرقم العشوائي المختار تكرارًا لرقم تم اختياره مسبقًا، حتى يتم اختيار رقم لم يتم اختياره بعد. يتناسب عدد المحاولات المتوقعة لكل خطوة في مثل هذه الحالات عكسيًا مع نسبة الأرقام التي تم اختيارها مسبقًا، ويتناسب العدد الإجمالي للمحاولات مع مجموع هذه المعكوسات، مما يجعل هذه الطريقة غير فعالة.

يمكن تجنب عمليات إعادة المحاولة هذه باستخدام خوارزمية تقوم، في كل خطوة (i) بعد _{اختيار x1، ...، xi-} 1 ، باختيار عدد عشوائي منتظم j _من بين 1 _{و n} - i + 1 ( شاملًا)، وتعيين xi _{مساويًا} لأكبر عدد j من بين الأعداد المتبقية التي لم يتم اختيارها بعد. يؤدي هذا إلى اختيار عشوائي منتظم من بين الأعداد المتبقية في كل خطوة دون الحاجة إلى إعادة المحاولة.

تُعرف خوارزمية بسيطة لتوليد تبديل عشوائي منتظم لـ n عنصرًا دون إعادة المحاولة، باسم خلط فيشر-ياتس . تبدأ الخوارزمية بأي تبديل (على سبيل المثال، التبديل المحايد )، ثم تمر على المواضع من 0 إلى n - 2 (نستخدم اصطلاحًا حيث يكون فهرس العنصر الأول 0، وفهرس العنصر الأخير n - 1)، وفي كل موضع i، يتم تبديل العنصر الموجود فيه بعنصر مختار عشوائيًا من المواضع من i إلى n - 1 (النهاية). ستنتج هذه الخوارزمية أي تبديل لـ n عنصرًا باحتمالية 1/ n ! بالضبط، مما ينتج عنه توزيع منتظم للتبديلات.

unsigned uniform ( unsigned m ); /* تُرجع عددًا صحيحًا عشوائيًا 0 <= uniform(m) <= m-1 بتوزيع منتظم */void initialize_and_permute ( unsigned permutation [], unsigned n ) { unsigned i ; for ( i = 0 ; i <= n -2 ; i ++ ) { unsigned j = i + uniform ( n - i ); /* عدد صحيح عشوائي بحيث يكون i ≤ j < n */ swap ( permutation [ i ], permutation [ j ]); /* تبديل العنصر المختار عشوائيًا مع permutation[i] */ } }

إذا uniform()تم تنفيذ الدالة ببساطة على النحو التالي، فسيكون هناك تحيز في توزيع التباديل إذا لم يكن عدد القيم المُعادة من مضاعفات m. ومع ذلك، يكون هذا التأثير ضئيلاً إذا كان عدد القيم المُعادة أكبر بكثير من m.random() % (m)random()random()

كما هو الحال مع جميع التطبيقات الحاسوبية للعمليات العشوائية، فإن جودة التوزيع الناتج عن تطبيق خوارزمية عشوائية مثل خلطة فيشر-ياتس، أي مدى قرب التوزيع الناتج فعليًا من التوزيع المطلوب، تعتمد على جودة مصادر العشوائية الأساسية في التطبيق، مثل مولدات الأرقام شبه العشوائية أو مولدات الأرقام العشوائية المادية . توجد العديد من اختبارات العشوائية للتباديل العشوائية، مثل اختبار "التباديل المتداخلة" ضمن اختبارات داي هارد . يتمثل أحد الأشكال الشائعة لهذه الاختبارات في أخذ إحصائية تبديلية معروفة التوزيع نظريًا، ثم اختبار ما إذا كان توزيع تلك الإحصائية على مجموعة من التباديل المولدة عشوائيًا من تطبيق ما يُقارب توزيع تلك الإحصائية من التوزيع الحقيقي.

يقترب التوزيع الاحتمالي لعدد النقاط الثابتة لتبديل عشوائي منتظم التوزيع مكون من n عنصرًا من توزيع بواسون بقيمة متوقعة تساوي 1 مع ازدياد n . ^{[ 1 ]} وتتطابق العزوم n الأولى لهذا التوزيع تمامًا مع عزوم توزيع بواسون. وبالتحديد، يقترب احتمال عدم وجود نقاط ثابتة في التبديل العشوائي (أي أن التبديل عبارة عن تبديل غير منتظم ) من 1/ e مع ازدياد n .