Сподівання

Ерік розробив просту схему генерації випадкових цілих чисел. Ця схема приймає на вхід ціле число $n$ та з рівною ймовірністю генерує цілі числа від $0$ до n - 1 включно. Наприклад, якщо n = 3, то схема з однаковою ймовірністю $1/3$ може згенерувати числа $0,1$ або $2$.

Тепер Ерік хоче створити більш складні схеми. Перша з них складається з двох незалежних ймовірнісних генераторів, виходи яких об'єднуються за допомогою побітової операції $XOR$ — виключного "АБО".

Друг Еріка, Нік, що вивчає математику, зауважив, що ця схема доволі цікава, а ще цікавішим є її математичне сподівання. Допоможіть їм обчислити це значення.

Нагадаємо, що математичне сподівання випадкової величини визначається як її середнє значення. Для випадкової величини $\xi$, що приймає невід'ємні цілі значення, воно обчислюється за формулою:

де p_i — ймовірність того, що \xi = i.