Modular Bias Error

Modulo Bias Error

وقتی که ی تابع رندوم توی C نوشتم براساس تکرار زیاد برنامه متوجه میشدم که یکسری حالات بیشتر رخ میدن، حتی با اینکه تابع ()rand رو برحسب زمان seed میدادم. بعدش متوجه شدم مشکل از محاسبات خودم بوده، و طوری که من کد رو نوشته بودم دچار خطای Modulo Bias میشدم که باعث میشد بعضی حالات احتمال بیشتری داشته باشند!

تابع ()rand یک عدد مثبت در بازه [RAND_MAX, 0] رو تولید میکنه پس طول بازه RAND_MAX + 1. کد اول که دارای خطای Modular Bias هست به این شکله:

int rng_int(int min, int max){
int range = max - min + 1;
int random = rand() % range;
return random + min;
}

فرض کنید RAND_MAX یک عدد خیلی کوچیک مثل 15 باشه، در این حالت اگه من اعداد رندوم از بازه [0, 5] بخوام، چون طول بازه‌ام 6 هست، اون رنج بزرگتر صفر تا 15 باید مپ بشه روی اعداد 0 تا 5 تا من نتیجه دلخواهم رو بگیرم، (مثلا اگه تابع بهم ۱۳ داد من اون رو نمیخوام چون توی بازه صفر تا پنجم نیست، پس مپش میکنم روی عدد یک) حالا به ازای تمام خروجی های یک تا پانزده ()rand این اتفاق میوفته:

0 % 6 = 0     1 % 6 = 1
2 % 6 = 2     3 % 6 = 3
4 % 6 = 4     5 % 6 = 5
6 % 6 = 0     7 % 6 = 1
8 % 6 = 2     9 % 6 = 3
10 % 6 = 4     11 % 6 = 5
12 % 6 = 0     13 % 6 = 1
14 % 6 = 2     15 % 6 = 3

دقت کردید؟ اعداد {0,1,2,3} 3 بار تکرار | map شدن درحالیکه اعداد {4,5} 2 بار تکرار | map شدن!

اینجا خطا رو با متد rejection sampling با استفاده از یک حلقه `do while` برطرف میکنیم:

int rng_int(int min, int max){
unsigned range = (unsigned)max - min + 1;
unsigned limit = RAND_MAX - (RAND_MAX % range);
int random;
do {
   random = rand();
} while((unsigned)random >= limit);
return min + (random % (int)range);

چه اتفاقی افتاد؟ با متغییر limit شانس همه رو برابر کردیم، مقدار limit بزرگترین عددی در بازه [0, RAND_MAX] هست که به طول بازه دلخواه ما بخش پذیره، توی مثال خودمون limit برابر با 12 میشه و توی حلقه‌ی do while باعث میشیم که اگه خروجی دربازه [0,limit - 1] نبود، دوباره انتخاب بشه تا شانس همه برابر باشه.

درنهایت، خطای Mudolo Bias دقیقاّ چیه؟ خب ماجولو (با همین تلفظ گوگولی) همون اپراتور % هستش و در دنیای احتمالات به سنگینی احتمال به یک سمت درحالیکه انتظار میره همه شانس برابری داشته باشن میگن Bias، مثل وقتی که یک طرف سکه سنگین تر از اونیکی‌ طرفه:)

کنجکاوی بیشتر:

مقدار RAND_MAX در پیاده سازی فعلی 2,147,483,647 هست.

 که با اجرای دستورات زیر در ترمینال bash بهش میرسید:

echo '#include <stdio.h>
#include <stdlib.h>
int main(){ printf("%d\n", RAND_MAX); }' | gcc -x c - && ./a.out

ممکنه با خودتون فکرکنید که این *نابرابری احتمالی* (به این خاطر میگیم احتمالی چون اگه بازه بزرگتر که قراره مپ بشه بطور تصادفی مضربی از بازه‌ای که ما میخوایم باشه، تمام احتمال‌ها یکسان توضیع میشه)، بعلت کوچک درنظر گرفتن عدد RAND_MAX در فرض ما صورت گرفته باشه، خب فرض کنیم مقدارش همون 2,147,483,647 باشه و میخوایم روی رنج [0, 5] مپ‌اش کنیم:

اول بیاییم طول بازه هارو بدست بیاریم:

Mapped Range = 2,147,483,647 + 1 = 2,147,483,648 (which is 2^31)
Mapping Range = 6

حاصل تقسیم صحیح بهمون میگه که اعداد داخل بازه حداقل چندبار مپ شدن.

Mapped Range / Mapping Range = 357,913,941

حاصل عملگر ماجولو بهمون میگه که دو تا عدد اول بازه دلخواه ما یکبار بیشتر مپ میشن پس یک شانس بیشتر گیرشون میاد! (درواقع همیشه این اعداد ابتدایی رنج هستن که ممکنه شانس بیشتری گیرشون بیاد)

Mapped Range % Mapping Range = 2

پس نتیجه گیری میکنیم:

{2,3,4,5} mapped 357913941 times
{0,1} mapped 357913942 times 
TRUTH CHECK:
4 * 357,913,941 + 2 * 357,913,942 = 2,147,483,648 (Mapped Range!)

شاید بگید دیدی که چون توی این رنج بزرگ احتمال ها خیلی نزدیکه و یک شانس بیشتر اصلا به چشم نمیاد حرف ما درست بود؟ حتی اگر به چشم نیاد هنوزم شانس ها برابر نیست، اما حق با تو، واقعا به زحمت نوشتن چند خط کد بیشتر نمی‌ارزه، اما حالا بیا بازه‌ای مدنظرمون برای تولید اعداد رندوم رو بزرگتر کنیم ببینیم بازم نمیارزه؟ ایندفعه بازه مدنظر ما [0, 999999] باشه، تمام مراحل بالا رو صرفا تکرار و نتجیه گیری میکنیم:

Mapped Range = 2,147,483,647 + 1 = 2,147,483,648 (which is 2^31)
Mapping Range = 1,000,000
Mapped Range / Mapping Range = 2,147
Mapped Range % Mapping Range = 483648

به زبان ساده این چه عدالتی است که چهارصدوهشتادوسه‌هزاروششصدوچهل‌وهشت عدد ابتدایی بازه، یک شانس بیشتر دارند در بازه‌ای که درکل ‌یک میلیون عدد دارد؟

[🖤 - PiBytes](https://t.me/PiBytes)