4817
правок
Нижняя граница для динамической связности: различия между версиями
Перейти к навигации
Перейти к поиску
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 09:28, 18 августа 2025
, 18 август→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
1. Ни одна ячейка, записанная в эпохи i + 1 | 1. Ни одна ячейка, записанная в эпохи <math>i + 1, i + 2,...</math>, не может содержать информацию об эпохе <math>i</math>, так как все они были записаны в прошлом. | ||
2. В эпохи 1... | 2. В эпохи <math>1, ..., i - 1</math> было записано <math>b t_u^{\Sigma} \cdot \sum_{j = 1}^{i - 1} r^j \le b t_u^{\Sigma} \cdot 2 r^{i - 1}</math> бит. Это меньше, чем <math>r_i \delta/100</math> бит информации для <math>r > 200 t_u^{\Sigma}</math> (вспомним предположение <math>\delta = b</math>). Из вышесказанного следует, что ответ на запрос все еще имеет <math>\Omega(\delta)</math> бит энтропии. | ||
3. Поскольку значение i равномерно случайно среди | 3. Поскольку значение <math>i</math> равномерно случайно среди <math>\Theta(log_r \; n)</math> эпох, запрос делает ожидаемое число <math>\Theta(t_q^{\Sigma}/log_r \; n)</math> зондирований ячеек из эпохи <math>i</math>. Все запросы, которые не делают ни одного зондирования ячеек в эпоху <math>i</math>, получают фиксированный ответ (энтропия 0), а все остальные запросы получают ответы с энтропией менее <math>\delta</math>. Поскольку средний запрос имеет энтропию <math>\Omega(\delta)</math>, запрос должен зондировать ячейку из эпохи <math>i</math> с константной вероятностью. Это означает, что <math>t_q^{\Sigma} / log_r \; n = \Omega(1)</math>, а <math>\sum = \Omega(log_r \; n) = \Omega(lg \; n/lg \; t_u^{\Sigma})</math>. | ||