Вероятностная структура данных, основанная на переворачивании битов с вероятностью `1/2^x` для подсчета. ⇐ Python
-
Anonymous
Вероятностная структура данных, основанная на переворачивании битов с вероятностью `1/2^x` для подсчета.
Как работает эта структура данных и каково ее применение?
класс X: защита __init__(сам): self.x = 0 защита plus_one (я): self.x = self.x + переворот(self.x) защита get(self): return 2**self.x #2 возведено в степень x Функция flip() — это случайная функция, которая возвращает 1 с вероятностью 1/2^x и 0 в противном случае.
Я подозреваю, что эта структура данных каким-то образом связана с алгоритмом вероятностного подсчета Р. Морриса.
В вопросе также упоминается, что это неравенство может быть полезным:
log(E[X]) >= E[log(X)]
где E обозначает ожидаемое значение.
Буду очень признателен за любую помощь или рекомендации.
Как работает эта структура данных и каково ее применение?
класс X: защита __init__(сам): self.x = 0 защита plus_one (я): self.x = self.x + переворот(self.x) защита get(self): return 2**self.x #2 возведено в степень x Функция flip() — это случайная функция, которая возвращает 1 с вероятностью 1/2^x и 0 в противном случае.
Я подозреваю, что эта структура данных каким-то образом связана с алгоритмом вероятностного подсчета Р. Морриса.
В вопросе также упоминается, что это неравенство может быть полезным:
log(E[X]) >= E[log(X)]
где E обозначает ожидаемое значение.
Буду очень признателен за любую помощь или рекомендации.
