PiBytes

Modulo Bias Error

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

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

int rng_int(int main, 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 بار تکرار شدن درحالیکه اعداد {4,5} 2 بار تکرار شدن!

اینجا خطا رو با rejection sampling برطرف میکنیم:

int rng_int(int main, 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، مثل وقتی که یک طرف سکه سنگین تر از اونیکی‌ طرفه:)

📍Read more in Telegraph

#script@pibytes

🖤 - PiBytes

❤10👍2

431 viewsedited 17:45