0.5 توزیع انتخابی از اعداد تصادفی

مواقعی وجود دارد که شما نیاز به توزیع یکنواخت از اعداد تصادفی یا توزیع گاوسی ندارید، تصور کنید شما گردشگر تصادفی هستید که می خواهید به دنبال غذاست. حرکت تصادفی در محیط برای پیدا کردن غذا یک استراتژی منطقی است، شما نمیدانید که غذا کجاست. ممکن است به صورت تصادفی حرکت کنید تا غذایی بیابید. مشکلی که شما ممکن است متوجه آن شده باشیداین است که گردشگر تصادفی ممکن است چندین بار به جای قبلی که گشته است برگردد.این مشکل به نام «oversmapling” شناخته می شود.یک استراتژی برای جلوگیری از این مشکل این است که گاهی یک قدم خیلی بزرگ برداریم. این به گردشگر ما اجازه می دهد که به جستجوی تصادفی خود بپردازد و در بازه های زمانی یک جهش بلند انجام دهد تا مشکل oversmapling کمتر شود. این نوع حرکت تصادفی به نام پرش لوی(Lévy شناخته می شود. در این روش نیاز به مجموعه ای احتمالات نیاز است. به هر حال یک پیاده سازی نچندان دقیق از پرش لوی می تواند به شکل زیر باشد : قدم بلند تر با احتمال اتفاق کمتر و گام کوتاه تر با احتمال اتفاق بیشتر.

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

float r = random(1);
if (r < 0.01) {
  xstep = random(-100,100);
  ystep = random(-100,100);
} else {
  xstep = random(-1,1);
  ystep = random(-1,1);
}

این روش احتمالات را به چند حالت محدود می کند. حال اگر بخواهیم یک قانون کلی تر بنویسیم چه. مثلا برای پیاده سازی اینکه عدد بزرگتر احتمال انتخاب بیشتری داشته باشد. ۳.۱۴۵ احتمال انتخاب بیشتری از ۳.۱۴۴ داشته باشد، حتی اگر یک مقدار کم بزرگتر از آن است. به عبارت دیگر، اگر X عددی تصادفی باشد، ما می توانیم نگاشتی از محور y به صورت y=x داشته باشیم.

تصویر ۰.۴

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

یک راه حل این است که دو عدد تصادفی به جای یکی انتخاب کنیم. عدد تصادفی اول که مانند قبل است. عدد دوم چیزی است که به نام صلاحیت سنجی مقدار تصادفی می نامیم. مقدار دوم به ما خواهد گفت که از عدد اول استفاده کنیم یا اینکه آن را بیندازیم و عدد دیگری برداریم. اعدادی که در زمان زودتری صلاحیت سنجی می شوند زودتر انتخاب می شوند، و اعداد که کمتر صلاحیت سنجی می شوند کمتر انتخاب می شوند. مراحلی که زیر لیست شده اند( برای الان، اجازه بدهید تنها اعداد تصادفی بین صفر تا ۱ را در نظر بگیریم):

۱) یک عدد تصادفی بردارد:R1

۲) احتمال انتخاب P که R1 دارد تا انتخاب شود را محاسبه کن : P=R1

۳) یک عدد تصادفی دیگر را بردار: R2

۴) اگر R2 کمتر از P بود آنگاه ما عدد خود را یافته ایم R1

۵) اگر R2 کمتر از P بود به مرحله یک برو و از ابتدا آغاز کن

در اینجا ما می توانیم بگویم که انتخاب عدد تصادفی برابر عددی تصادفی است.

اجازه بدهید بگوییم که مقدار ۰.۱ را برای R1 برداشته ایم. این به معنای آن است که R1 شانسی ۱۰٪ برای انتخاب دارد.اگر ما مقدار ۰.۸۳ برای R1 را برداشته بودیم آنوقت ما با احتمال ۸۳٪ را برای انتخاب داشتیم. مقدار بالاتر، احتمال بالاتری را برای انتخاب دارد.

در اینجا تابعی (به نام تابع Monte Carlo شناخته میشود) الگوریتم بالا را پیاده سازی می کند، یک مقدار تصادفی بین ۰ تا ۱ را برمی گرداند.

float montecarlo() {
//We do this “forever” until we find a qualifying random value.
  while (true) {
//Pick a random value.
    float r1 = random(1);
//Assign a probability.
    float probability = r1;
//Pick a second random value.
    float r2 = random(1);
 
//Does it qualify? If so, we’re done!
    if (r2 < probability) {
      return r1;
    }
  }
}

تمرین ۰.۶

از یک توزیع احتمال انتخابی برای تغییر اندازه قدم های گردشگر تصادفی استفاده کنید. اندازه قدم می تواند با تاثیر از رنج های مقادیر آمده انتخاب شود. آیا می توانید از احتمال نمایی استفاده کنید. -- مثلا احتمال انتخاب مقادر برداشته شده برابر با مربع مقدار باشد؟

   float stepsize = random(0,10);
 
  float stepx = random(-stepsize,stepsize);
  float stepy = random(-stepsize,stepsize);
 
  x += stepx;
  y += stepy; 

در آینده خواهید دید چطور که چگونه با استفاده از وکتور به صورت بهینه تری آنرا پیاده سازی کنید.