Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

18.05.2023

Реальна ймовірність збігу UUID

Вчора я трохи завтикав зі ймовірністю. А саме: вирішив, що ймовірність збігу за годину у 3600 разів більша за ймовірність збігу за секунду. Зрозуміти, що це неправильно можна, якщо спростити приклад до підкидання монети. Ймовірність “орла” - 1/2. Якщо підкинути монету двічі, то ймовірність аж ніяк не зросте удвічі та не становитимете 1!

Тож з’ясуймо, яка все ж таки ймовірність того збігу UUID.

• Знаємо, що відбиток часу має 10 мільйонів значень на секунду. Але насправді нас цікавить не секунда, а проміжок часу між генераціями; припускаючи, що UUID може отримати будь-який таймстемп з проміжку. Наприклад, якщо ми генеруємо 1000 UUID на секунду, то число можливих значень таймстемпу - 10000. (До речі, ще одне припущення — що годинники всіх машин засинхронізовані.)

• Припускаємо, що кожна машина генерує тільки унікальні таймстемпи. Тоді ймовірність збігу залежить від кількості машин. Це варіант парадокса днів народження, тільки замість дітей в нас “народжуються” таймстемпи, а замість року — множина можливих значень.

• Тоді за узагальненою формулою можна підрахувати ймовірність збігу на одну генерацію: (1 - Math.exp(-machineCount*(machineCount-1)/(2*valueCount)).

• Тепер щодо ймовірності на більшому проміжку часу. Не знайшов гарного джерела, тому розбирався сам. Легко обчислити ймовірність того, що подія відбудеться щоразу: для цього ймовірність береться в ступінь за кількістю повторень: 1/2, 1/4, 1/8 і так далі: p^n. Так само можна обчислити ймовірність того, що подія ніколи не відбудеться: (1-p)^n. А нас цікавить ймовірність зворотного: 1-(1-p)^n. Або, в нашому прикладі зі збігами: 1 - Math.pow(1-singleCollisionProbability, repeatCount).

• Всю цю математику опублікував в gist. Якщо я не помиляюсь знову, то 2 машини, що генерують 1 UUID на секунду, досягнуть 50% ймовірності збігу за 3 місяці. А якщо вони генерують 1000 UUID на секунду — то вже за хвилину ймовірність досягне 99.7%. Отакої.

…Теорія ймовірності — найпарадоксальніша з галузей математики. Вона, безумовно, має найбільший вплив на наше життя — оцінки ймовірності визначають наші найважливіші життєві рішення. Тільки при цьому немає науки, де легше зробити помилку та бути 100% впевненим у своїй правоті. Дозвольте познайомити вас з парадоксом Монті Голла.