מספר אקראי

מספר אקראי בתורת ההסתברות הוא מספר "מוגרל" מתוך טווח נתון ולפי התפלגות נתונה. זוהי תוצאת תצפית יחידה של משתנה מקרי בעל התפלגות כלשהי. כאשר ההתפלגות אינה מצוינת, מדובר בדרך כלל בהתפלגות אחידה בדידה, בה הסיכוי לקבלת כל ערך בטווח - שווה (כפי שמתקיים למשל בהטלת מטבע או בהטלת קובייה). כל התפלגות אחרת יכולה לשמש אף היא להגרלת ערך אקראי, ולמעשה תקבע את סיכויי ההגרלה.
במספרים אקראיים יש עניין בתחומים מדעיים רבים, בהם הדמיית אקראיות לצורך מחקר במדעי המחשב ובמדעים אחרים כמו תורת הכאוס, תורת המשחקים, תורת האינפורמציה, תורת ההסתברות ומכניקה קוונטית. כמו כן יש עניין בהם גם במשחקי מחשב, משחקי הימורים ובקריפטוגרפיה, בהם יש צורך לעיתים בהגרלת אלמנט או רצף אקראי של אלמנטים בהתפלגות אחידה מתוך קבוצה נתונה של האלמנטים או רצפים.

מספר אקראי אמיתי

לא ניתן לקרוא למספר "אקראי" ללא הקשר כלשהו. לדוגמה: אם נתונים במכל 49 כדורים זהים הממוספרים מ-1 עד 49 ואם שולפים מתוך המכל (לאחר ערבוב הגון) כדור אחד ועליו מופיע המספר 23 ניתן לומר כי המספר 23 הוגרל באופן אקראי בהתפלגות אחידה מתוך הקבוצה . ההסתברות שהמספר 23 יוגרל היא . אם נרשום את המספר המופיע על הכדור, נחזירו למכל ונחזור על תהליך זה מספר פעמים, נקבל רצף אקראי המוגדר מעל הקבוצה . לדוגמה: הסיכוי שיוגרל הרצף:  (בהנחה שכל כדור מוצא, נרשם ומוחזר שוב) היא  או  שהיא כפולה של ההסתברויות של כל כדורים ברצף.

מבחנים סטטיסטיים

מחוללים המבוססים על תופעות פיזיקליות כמו אלו המתוארות, אינם יציבים בדרך כלל ולרוב סובלים מהטיה סטטיסטית (Biased), כך שתוצאתם אינה אחידה. מבחינה מתמטית לא ניתן להוכיח שרצף הנוצר ממקור אקראי כלשהו הוא באמת אקראי. אולם ניתן באמצעות מבחנים סטטיסטיים מסוימים לבדוק את רמת האקראיות, על ידי איתור נקודות תורפה במחולל, שיכולות להצביע על אקראיות לקויה. מחולל אקראי יהיה בטוח רק אם ניתן להשתכנע בוודאות כי כל סיבית המופקת ממנו היא בהסתברות של חצי. אם למשל ההסתברות להגרלת סיבית 1 שונה מחצי אזי המחולל לא יהיה בטוח. ידוע על ניסיונות מוצלחים לניצול חולשות אלו על ידי מהמרים במשחקי הימורים. ישנן טכניקות לביטול ההטיה ושיפור האקראיות במקרים בהם תוצאת המחולל האקראי סובלת מהטיה, כמו בטכניקה הנקראת De-skewing.
ישנם מספר מבחנים סטטיסטיים בסיסיים, לבדיקת אקראיות. מבחן תדירות של סיביות בודדות, שבו נבדק האם מספר סיביות 1 זהה בקירוב לסיביות 0. מבחן סריאלי (זוגות סיביות) שבו בודקים האם מספר מופעי הזוגות (00,01,11,10) ברצף, אחיד פחות או יותר. מבחן פוקר, המבוסס על התפלגות כי בריבוע, שבו מחלקים את הרצף לתת-סדרות באורך מסוים ובודקים האם הם חוזרים על עצמם בהתפלגות שווה ברצף האקראי. מבחן רצף שבו בודקים האם ריצות רצופות של אפסים או אחדים באורכים שונים הם כצפוי מרצף אקראי ואוטו-קורלציה שהיא בדיקת מידת הקורלציה (רמת מתאם) בין הרצף הנבדק לבין היסטים שונים שלו.
מעבר לכך קיימות שיטות רבות לבדיקת אקראיות, בהן שיטת מאואר הנקראת "מבחן סטטיסטי אוניברסלי" המבוססת על הרעיון הבא, אם רצף כלשהו ניתן לדחיסה באופן משמעותי בעזרת אלגוריתם דחיסה כלשהו, הוא אינו אקראי. האלגוריתם של מאואר מנסה לבדוק את רמת הדחיסות של הרצף ובדרך זו לבחון את מידת אקראיותו, ככל ששיעור הדחיסות נמוך יותר מידת האקראיות גבוהה יותר. מבחנים נוספים נקראים מבחנים ספקטרליים המבוססים על התמרת פורייה ועל סיבוכיות ליניארית. ומבחן Diehard (שמרן), הוא סוללה של מבדקים סטטיסטיים שונים למדידת איכות של רצפים אקראיים, הידוע כאחד המבחנים היותר קפדניים. פותח על ידי ג'ורג' מרסגליה ב-1995.
גם אם המחולל עומד בהצלחה בכל מבחני האקראיות כמו אלו האמורים, אין בכך הוכחה מוחלטת לאקראיותו.

מספר פסאודו אקראי

מרבית ההתקנים הפיזיקליים ליצירת מספרים אקראיים כמו אלו המתוארים לעיל, נוטים להיות יקרים מאוד ואיטיים ובמקרים מסוימים אף לא מעשיים. על כן הומצאו שיטות ליצירת מספרים פסאודו-אקראיים (מדומים) באופן דטרמיניסטי (במחשב), מתוך רצף אקראי קצר הנקרא גרעין (seed). רצף פסאודו-אקראי אינו אקראי אמיתי, אלא רק נראה לעין כאקראי, כאשר הגרעין ההתחלתי אינו ידוע. אולם בשל אופיים הדטרמיניסטי רצפים אקראיים שנוצרו בעזרת מחולל פסאודו-אקראי ניתנים לשחזור מדויק בהינתן הגרעין ההתחלתי. לעובדה זו שימושים מסוימים, שכן ניתן להעביר את הגרעין ההתחלתי ממקום למקום וליצור אותו הרצף במקום אחר.
תוצאת מחולל סיביות פסאודו-אקראי (PRBG) אינה אקראית לגמרי. למעשה עבור גרעין התחלתי באורך , מספר הרצפים שהמחולל מסוגל לייצר באורך  מהווה רק חלק קטן מהטווח המקסימלי ליתר דיוק  של כל הרצפים הבינאריים האפשריים באורך . השאיפה היא למצוא שיטה להרחבת גרעין התחלתי קצר לרצף באורך מרבי, באופן שלא ניתן יהיה להבחין בינו לבין רצף באורך זהה המיוצר בעזרת מחולל אמיתי. קיים מגוון עצום של אלגוריתמים ליצירת מספרים פסאודו-אקראיים מסוגים שונים. אולם רבים מהם אינם בטוחים ויש להיזהר בטענת הממציאים באשר לטיב אקראיותם.

אלגוריתמים אקראיים

אלגוריתמים אקראיים עושים שימוש במספרים אקראיים. בזמן ריצה מבצע האלגוריתם החלטות בהתאם לערך אקראי כלשהו. בשל כך ייתכן מצב שבו האלגוריתם יחזיר תשובה שונה עבור קלט זהה. מסיבה זו נקראים אלגוריתמים אלו "אקראיים", בניגוד לאלגוריתמים דטרמיניסטיים, שעבור קלט זהה יבצעו תמיד אותן החלטות ותוצאתם תהיה תמיד זהה. דוגמה לשימוש במספרים אקראיים היא אלגוריתם מילר-רבין לבדיקת ראשוניות, שבמימושו הבסיסי נעשה שימוש במספרים אקראיים. אלגוריתם זה הוא אלגוריתם הסתברותי, כיוון שאינו מחזיר תשובה שנכונותה ודאית. השימוש באקראיות כשיטה לבדיקת ראשוניות יעיל יותר מאלגוריתמים דטרמיניסטיים מקבילים.
דוגמה נוספת לשימוש במספרים פסאודו-אקראיים היא שיטת מונטה קרלו, המשתמשת במספרים אקראיים לפתרון בעיות חישוביות.

לקריאה נוספת

דונלד קנות', The art of computer programming, Vol 2: Seminumerical Algorithms.