Вопросы в теории вероятностей
Несмотря на то, что я прошел несколько курсов по теории вероятностей, как в старшей школе, так и в университете, мне трудно читать документы TCS, когда речь идет о вероятности. Кажется, что авторы работ TCS очень знакомы с вероятностью. Они волшебным образом работают с формулами вероятности и очень...
Существует ли обратная граница Черноффа, определяющая, что вероятность хвоста хотя бы так велика? т.е. если являются независимыми биномиальными случайными переменными и . Тогда мы можем доказать для некоторой функции...
Хорошо известно, что случайное блуждание в двумерной сетке вернется в начало координат с вероятностью 1. Также известно, что такое же случайное блуждание в ТРЕХ измерениях имеет вероятность, строго меньшую 1, возврата в начало координат . Мой вопрос: Есть что-то среднее? Например, предположим, что...
Цитируя Википедию , «[Игра Жизни Конвея] обладает мощью универсальной машины Тьюринга: то есть все, что может быть вычислено алгоритмически, может быть вычислено в Игре Жизни Конвея». Распространяются ли такие результаты на шумные версии игры жизни Конвея? Простейшая версия состоит в том, что после...
Следующая проблема возникла во время исследования, и она удивительно чиста: У вас есть источник монет. Каждая монета имеет уклон, а именно вероятность того, что она упадет на «голову». Для каждой монеты независимо существует вероятность 2/3, что она имеет смещение не менее 0,9, а с остальной...
Я слышал, что в статистической физике есть эвристические аргументы, которые дают результаты в теории вероятностей, для которых строгие доказательства либо неизвестны, либо очень трудно получить. Что является простым игрушечным примером такого явления? Было бы хорошо, если бы ответ предполагал...
Меня интересует критическая плотность 3-удовлетворяемости (3-SAT) . Предполагается, что такой α существует: если количество случайно сгенерированных 3-SAT-предложений равно ( α + ϵ ) n или более, они почти наверняка неудовлетворительны. (Здесь ϵ - любая малая постоянная, а n - число переменных.)...
Хорошо известно, что многие важные параметры графа показывают (сильную) концентрацию на случайных графах, по крайней мере, в некотором диапазоне вероятности границы. Некоторые типичные примеры: хроматическое число, максимальная клика, максимальный независимый набор, максимальное совпадение, номер...
Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...
Когда я преподаю границы хвоста, я использую обычную прогрессию: Если ваш тренд положительный, вы можете применить неравенство Маркова Если у вас есть независимость, а также ограниченная дисперсия, вы можете применить неравенство Чебышева Если каждый независимый rv также имеет все ограниченные...
(Фон Нейман дал алгоритм, который имитирует честную монету при доступе к одинаковым смещенным монетам. Алгоритм потенциально требует бесконечного числа монет (хотя в ожидании достаточно конечного числа). Этот вопрос касается случая, когда допустимое количество бросков монет ограниченная.)...
Я столкнулся со следующим результатом во время моего исследования. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 где m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) и a1,⋯,ama1,⋯,ama_1,\cdots,a_m...
Если - выпуклая функция, то неравенство Дженсена утверждает, что , и mutatis mutandis, когда вогнута. Очевидно, что в худшем случае вы не можете получить верхнюю границу в терминах для выпуклого , но есть ли граница, которая идет в этом направлении, если выпуклый, но не слишком выпуклый? Существует...
Классическая проблема в теории вероятностей состоит в том, чтобы выразить вероятность события в терминах более конкретных событий. В простейшем случае можно сказать, что . Напишем для события .п[ A ∪ B ] = P[ A ] + P[ B ] - P[ A ∩ B ]п[A∪В]знак равноп[A]+п[В]-п[A∩В]P[A \cup B] = P[A] + P[B] - P[A...
Я думал об этой проблеме очень давно, но понятия не имею об этом. Алгоритм генерации заключается в следующем. Мы предполагаем, что существует nnn дискретных узлов, пронумерованных от 000 до n−1n−1n - 1 . Затем для каждого iii в { 1 , … , n - 1 }{1,…,n−1}\{1, \dotsc, n - 1\} мы делаем родительский...
Хорошо известно, что если вы бросите n шаров в n корзин, то в самой загруженной корзине, скорее всего, будет шариков. В общем, можно спросить о шарах в корзинах. В статье из RANDOM 1998, опубликованной Раабом и Стегером, это подробно рассматривается, показывая, что с ростом вероятность того, что...
Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.± 1±1\pm 1 Здесь и ниже, когда я говорю о выборке преобразования Фурье, я...
Рассмотрим следующий процесс: Есть корзин, расположенных сверху вниз. Первоначально, каждая корзина содержит один шар. На каждом шагу мыNNn выбрать мяч равномерно наугад иббb переместите все шары из корзины, содержащей в корзину под ней. Если это уже была самая низкая корзина, мы удаляем шары из...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...