Paano Pumipili ng Patas na Panalo ang Wheel of Names

Araw-araw, ang mga guro sa paaralan, mga streamer sa YouTube at Twitch, mga pinuno ng grupo sa opisina, at mga tagapag-organisa ng giveaway ay humihingi ng tiwala sa isang umiikot na bilog. Isang makulay na gulong ang umiikot sa screen, lumalampas sa mga ticked peg, at dahan-dahang humihinto hanggang sa ituro ng palaso ang iisang pangalan.

Gayunpaman, kapag may premyo, grado, o reputasyon na nakataya, natural na lumilitaw ang parehong pagdududa: Dinaya ba ang wheel of names na ito?

Mabuti ang maging maingat. Kapag hindi masusuri ang code sa likod ng isang palabunutan, ang digital spinner ay nagmumukhang isang misteryosong kahon. Ang isang kalahok na nakitang natalo ang kanyang pangalan nang limang magkakasunod na ikot ay maaaring maghinala na may nakatagong timbang, na minamanipula ng server ang resulta, o naapektuhan ito ng bilis ng pag-click.

Sa malalimang gabay na ito, hahantong tayo nang sunod-sunod sa computer science at probability theory sa likod ng isang tunay na patas na random picker. Susuriin natin kung bakit ang mga karaniwang programming shortcut tulad ng Math.random() ay nagdadala ng mga nakatagong bias, paano ito nilulutas ng cryptographically secure pseudo-random number generators (CSPRNG), paano inaalis ng rejection sampling ang bitag ng modulo bias, at paano mo masusuri ang mga resulta gamit ang Chi-Square test.

Bakit nabibigo ang mga karaniwang pseudo-random na numero sa mahahalagang palabunutan

Ang mga computer ay mga makinang deterministiko. Kapag binigyan ng magkaparehong inputs at magkaparehong utos, ang isang computer processor ay maglalabas ng parehong resulta sa bawat pagkakataon. Upang makabuo ng mukhang “random”, karamihan sa mga programming language at browser ay umaasa sa mga algorithmic formula na tinatawag na Pseudo-Random Number Generators (PRNG).

Sa pangkaraniwang web development, nagbibigay ang JavaScript ng Math.random(). Sa ilalim nito, ang mga modernong browser ay nagpapatakbo ng Math.random() gamit ang algorithm na kilala bilang xorshift128+. Para sa mga simpleng visual effect, tulad ng bumabagsak na snow sa webpage o nagbabagong kulay ng background, ang xorshift128+ ay mabilis, magaan sa memory, at sapat na.

Ngunit para sa mga pagpili na kailangang maging patas, may dalawang malaking kahinaan ang Math.random():

1. Nahuhulaang Estado ng Algoritmo: Dahil puro matematika ang xorshift128+, ang pagsubaybay sa maikling serye ng magkakasunod na resulta ay sapat na upang malaman ang 128-bit internal state nito. Kapag nalaman ang estadong ito, lahat ng susunod na “random” na resulta ay mahuhulaan nang may 100% katiyakan sa matematika.
2. Kakulangan sa Pisikal na Hardware Entropy: Ang mga karaniwang PRNG algorithm ay hindi kumukuha ng ingay mula sa pisikal na kapaligiran (tulad ng init ng processor o bilis ng pagpindot sa keyboard). Umuulit lamang sila sa isang formula batay sa panimulang seed.

Kapag may nag-organisa ng raffle sa kumpanya, namili ng iskolar, o naghati ng mga estudyante gamit ang team generator, ang paggamit ng nahuhulaang algorithm ay nagdudulot ng panganib. Kung mahulaan ng sinuman ang seed, mawawalan ng bisa ang tiwala sa palabunutan.

Ang pamantayan sa cryptography: paano gumagana ang CSPRNG

Upang makamit ang katarungang hindi mapag-aalinlanganan, ang isang modernong wheel of names ay dapat gumamit ng Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). Sa modernong web, ang kakayahang ito ay likas na ibinibigay sa pamamagitan ng method na window.crypto.getRandomValues().

Sa halip na umasa sa isang pormula na nagsisimula sa pag-load ng page, ang CSPRNG ay direktang kumokonekta sa entropy pool ng operating system:

• Sa Linux, Android, at macOS, nakikipag-ugnayan ang browser sa mga mekanismo ng kernel tulad ng /dev/urandom at mga ChaCha20-based CPRNG implementation.
• Sa Windows, humihiling ang browser ng mga random byte mula sa Windows Cryptography API: Next Generation (CNG) sa pamamagitan ng ProcessPrng at mga system entropy collector.

Kinukuha ng mga pool na ito ang mga hindi mahuhulaang pisikal na ingay: maliliit na pagbabago sa temperatura ng CPU, agwat ng pagproseso ng hard drive, paggalaw ng mga packet sa network, at bilis ng pagpindot sa keyboard. Isinasama ng OS ang mga ito sa isang cryptographic pool na imposibleng mahulaan o i-reverse-engineer.

Kapag pinindot mo ang pagpaikot sa Spin Names Now, pinatatakbo ng aming makina ang:

const buffer = new Uint32Array(1);
window.crypto.getRandomValues(buffer);
const rawRandomValue = buffer[0];

Ang tawag na ito ay gumagawa ng isang unsigned 32-bit integer (u32) na pantay-pantay na nakakalat sa 2³² = 4,294,967,296 posibleng halaga (mula 0 hanggang 4,294,967,295). Bawat integer sa saklaw na mahigit 4.29 bilyon ay may eksaktong parehong probabilidad na mapili:

P(X = k) = 1 / 4,294,967,296 ≈ 2.3283 × 10⁻¹⁰

Ang nakatagong bitag: ano ang modulo bias at paano nito binabago ang tsansa?

Ang pagbuo ng patas na 32-bit integer ay kalahati lamang ng laban. Bihirang maglaman ang gulong ng 4.29 bilyong piraso; kadalasan, mayroon lamang itong 7 pangalan, 15 mag-aaral, o 40 kalahok.

Paano itinutugma ng computer ang 32-bit na numero sa maliit na listahan na may habang $N$?

Karamihan sa mga simpleng tutorial sa pag-code ay nagmumungkahi na gamitin ang modulo operator (%):

// WARNING: Naive implementation that suffers from modulo bias!
const winnerIndex = rawRandomValue % numberOfNames;

Dito sa iisang linyang ito ng code nagsisimula ang hindi sinasadyang daya ng maraming online wheel spinner at raffle bot. Ang kapintasang ito sa matematika ay tinatawag na Modulo Bias.

Simpleng halimbawa ng modulo bias

Upang maunawaan ang modulo bias nang malinaw nang hindi naliligaw sa bilyun-bilyong numero, isipin ang pinasimpleng halimbawa:

• Ipagpalagay nating ang generator ay gumagawa ng mga numero sa pagitan ng 0 at 9 nang may pantay na pagkakataon (10 posibleng resulta).
• Mayroon kang 3 pangalan sa gulong: Ana (index 0), Ben (index 1), at Carlo (index 2).
• Itinutugma mo ang numerong 0–9 sa 3 pangalan gamit ang halaga % 3:

Napansin mo ba ang nangyari?

• Si Ana ay mananalo kung ang generator ay maglabas ng 0, 3, 6, o 9 (4 sa 10 resulta = 40.0% pagkakataon).
• Si Ben ay mananalo sa 1, 4, o 7 (3 sa 10 resulta = 30.0% pagkakataon).
• Si Carlo ay mananalo sa 2, 5, o 8 (3 sa 10 resulta = 30.0% pagkakataon).

Dahil hindi nahahati nang pantay ang 10 sa 3, ang natirang labis ay pumapabor sa mga unang entry sa listahan. Si Ana ay may 33% mas mataas na tsansang manalo kaysa kay Ben o Carlo dahil lamang sa paraan ng paghahati ng numero!

Kahit mas maliit ang agwat kapag hinahati ang 2³² (4,294,967,296), sa mga pormal na pamamahagi at opisyal na palabunutan, anumang bias sa matematika ay lumalabag sa prinsipyo ng pantay na tsansa.

Paano inaalis ng rejection sampling ang modulo bias

Paano inaalis ng mga eksperto sa cryptography at mga mapagkakatiwalaang system ang modulo bias? Ang solusyon ay isang eleganteng paraan na tinatawag na Uniform Rejection Sampling.

Sa halip na tanggapin ang buong saklaw ng numero, kinakalkula ng algorithm ang pinakamalaking buong multiple ng dami ng listahan $N$ na kasya sa loob ng 32-bit limit. Anumang random na halaga na lalampas sa limitasyong iyon ay itinatapon (“tinatanggihan”), at agad na kumukuha ng panibagong numero.

Narito ang eksaktong pagpapatupad sa aming system (src/lib/random.ts):

const MAX_U32 = 0x100000000; // 2^32 = 4,294,967,296

export function secureRandomInt(maxExclusive: number): number {
  if (maxExclusive <= 1) return 0;

  const cryptoObj = window.crypto;
  const max = Math.floor(maxExclusive);

  // Calculate the largest multiple of `max` that fits inside 2^32
  const limit = MAX_U32 - (MAX_U32 % max);
  const buf = new Uint32Array(1);
  let val: number;

  // Discard any number in the uneven trailing tail
  do {
    cryptoObj.getRandomValues(buf);
    val = buf[0];
  } while (val >= limit);

  return val % max;
}

Sa pamamagitan ng lohikang ito:

1. Bawat numerong ginagamit ay garantisadong nagmumula sa saklaw na pantay na nahahati sa laki ng listahan max.
2. Dahil napakaliit ng itinatapong bahagi (hindi lalagpas sa max - 1 na numero sa mahigit 4.29 bilyon), ang posibilidad ng rejection ay mas mababa sa $0.00001%$, na tumatagal lamang ng microseconds.
3. Bawat bahagi sa gulong ay may eksaktong parehong probabilidad na mapili.

Binabago ba ng bilis o tagal ng pagpaikot ang mananalo?

Ang madalas na itinatanong ng mga kalahok ay ang kaugnayan ng nakikitang animation at ng algorithm. Madalas itanong:

• «Kapag mas mabilis kong pinindot, mas lalayo ba ang ikot?»
• «Kung i-swipe ko ang gulong sa cellphone, makokontrol ko ba kung saan hihinto?»
• «Mababago ba ng mas mabilis na computer kung saan hihinto ang arrow?»

Ang malinaw na sagot ay hindi kailanman.

Sa isang mapagkakatiwalaang wheel of names, ang nanalo ay napagdesisyunan na ng secureRandomInt() sa mismong milisegundo ng pag-click. Ang index ng nanalo ay naka-save na sa memorya bago pa man umikot ang gulong nang kahit isang degree.

Ang visual animation na kasunod nito ay pinatatakbo ng physics easing algorithms (tulad ng cubic bezier curves). Kinakalkula ng engine ang kabuuang anggulo ng pag-ikot:

Total Rotation Angle = (360° × N_spins) + Winner_Slice_Offset

Mabilis na iikot ang gulong at unti-unting babagal sa loob ng ilang segundo upang magbigay ng pananabik sa mga manonood, habang sinisiguro na ang palaso ay hihinto nang eksakto sa gitna ng paunang napiling panalo.

Dahil kinakalkula ang resulta gamit ang cryptography at hindi sa pisikal na alitan, walang “dead spots”, walang pagkasira ng piyesa, at hindi apektado ng bilis ng screen refresh o lakas ng processor.

Paano suriin at patunayan ang pagiging patas gamit ang Chi-Square Test

Sa agham, ang katarungan ay hindi dapat tanggapin sa salita lamang: dapat itong mapatunayan sa pamamagitan ng estadistika.

Ang pamantayang pagsusuri na ginagamit para suriin ang mga discrete uniform random distribution ay ang Pearson’s Chi-Square Goodness-of-Fit Test (χ²).

1. Pagbuo ng Hypothesis

Kapag sumusuri ng gulong na may k na magkakaparehong bahagi:

• Null Hypothesis (H₀): Ang wheel of names ay perpektong patas. Bawat bahagi ay may pantay na probabilidad na mapili P_i = 1 / k.
• Alternative Hypothesis (H₁): May kinikilingan ang gulong. May kahit isang bahagi na may probabilidad na iba sa 1 / k.

2. Pormula ng Chi-Square

Kung paiikutin natin ang gulong nang N beses, ang inaasahang dami ng panalo para sa bawat kalahok i ay:

Expected Wins (E_i) = Total Spins (N) / Slices (k)

Sinusukat ng chi-square statistic ang kabuuang paglihis sa pagitan ng aktwal na panalo (O_i) at inaasahang panalo (E_i):

χ² = Σ [ (Observed_i - Expected_i)² / Expected_i ]

3. Degrees of Freedom at ang p-value

Ang degrees of freedom para sa pagsubok ay:

Degrees of Freedom (df) = k - 1

Gamit ang cumulative distribution function ng chi-square, kinakalkula natin ang p-value:

• Ipinapakita ng p-value ang posibilidad na makakita ng paglihis na kasinglaki o mas malaki pa kung ang gulong ay tunay na patas.
• Sa karaniwang estadistika, kung ang p-value ay mas mataas sa 0.05 ($p > 0.05$), hindi natin tatanggihan ang null hypothesis. Ang resulta ay nasa loob ng normal na pagkakaiba-iba.
• Kung dinaya ang spinner (halimbawa, kung ang slice 1 ay may dobleng tsansa), ang 1,000 ikot ay maglalabas ng napakalaking $\chi^2$ na halaga na may p-value sa ilalim ng $0.0001$, na nagpapatunay sa pandaraya.

Sa aming Fairness Lab, maaaring pumili ang mga gumagamit ng dami ng listahan, magpatakbo ng simulation ng hanggang 500,000 ikot sa background (Web Worker), at makita ang live histogram, standard deviation, at p-value nang real-time.

Praktikal na gabay para sa isang transparent na raffle

Kung nag-oorganisa ka ng giveaway, pagsusulit sa klase, o raffle sa komunidad, ang teknolohiya ay kalahati lamang ng tiwala. Ang kalinawan sa pagsasagawa ay nagsisiguro na ang mga kalahok ay magtitiwala sa resulta.

Konklusyon: Kalinawan sa halip na mga itim na kahon

Sa panahon ng mga nakatagong algorithm, may karapatan ang mga gumagamit na malaman kung paano gumagana ang kanilang mga digital tool. Ang isang wheel of names ay hindi dapat maging isang misteryo. Gamit ang Web Crypto API ng browser, pinatatag ng rejection sampling upang maalis ang modulo bias, at napatunayan ng bukas na estadistika, ang digital wheel ay bumabalik sa tunay nitong layunin: isang masaya, patas, at tapat na tagahatol ng kapalaran.

Pumipili ka man kung sino ang unang magsasalita sa meeting, nagbibigay ng regalo sa tagasubaybay sa live stream, o naghahati ng klase gamit ang aming team generator, makapagpapaikot ka nang may buong kapanatagan na bawat pangalan ay may patas at pantay na pagkakataong manalo.