выполнено на сервисе Автор24

Студенческая работа на тему:

Начало решения Расстоянием Хэмминга между двумя двоичными последовательностями одинаковой длины называется число разрядов

Решение задач Теория вероятностей

Создан заказ №1338205

15 сентября 2016

Начало решения Расстоянием Хэмминга между двумя двоичными последовательностями одинаковой длины называется число разрядов

Как заказчик описал требования к работе:

Срочно нужно написать решение задач по теории вероятности ко вторнику. Список требований в файле.

Фрагмент выполненной работы:

Начало решения. Расстоянием Хэмминга между двумя двоичными последовательностями одинаковой длины называется число разрядов, в которых последовательности не совпадают. Например, d{(1,0,1,0),(1,1,1,1)}=2, d{(0,1,1,0),(1,1,1,1)}=2, d{(1,0,1,0),(0,1,1,0)}=2. Пусть Pk(a,b)-вероятность, что после k шагов из вершины a попадем точно в вершину b Лемма. Эта вероятность зависит только от d(a,b). Доказательство. (работа была выполнена специалистами author24.ru) Поместим начало координат куба в точку a , а 4 оси координат направим так, чтобы первые d(a,b) координат b стали единицами, а остальные нулями. Например, a=(1,0,1,0),b=(1,1,1,1)} имеют новые координаты a’=(0,0,0,0) b’=(1,1,0,0) (вторая координата стала 1-й, 4-я второй). Pk(a,b) =Pk(a’,b’), так как определение переходных вероятностей давалось вне зависимости от системы координат. Теперь можно дать ответ на первый вопрос. Вершины (0,1,1,0),(1,1,1,1), (1,0,1,0) образуют равносторонний треугольник в метрике Хэмминга и в кубе равноправны. Поэтому на всякий путь из (1,0,1,0) , который раньше посетит (1,1,1,1), чем (0,1,1,0), найдется столь же вероятный путь, который наоборот. Значит, вероятности указанных событий равны ½ Для второго вопроса можно укрупнить пространство состояний: данную стартовую вершину считать состоянием 0, противоположную (на расстоянии 4 от стартовой) состоянием 4, а все вершины на расстоянии 2 от них (6 штук) считать состоянием 2. Каждая пара шагов переводит состояние в соседнее в этой тройке, так как за четное число шагов попалаем в состояние с четными номерами. Выписываем матрицу перехода за пару шагов 0,25 0,75 0 0,375 0,25 0,375 0 0,75 0,25 И анализируем. Только надо учесть, что когда мы из состояния 0 (строка (1 0 0) слева умножается на k-ю степень матрицы перехода, если это сделано за 2k шагов) попадаем в состояние 2 (берется 2-я компонента полученной строки), то равновероятно в любую из 6-ти его вершин, вероятность попасть именно в данную – в 6 раз меньше… Решение. Cтартовое состояние задается 6-мерным вектором-строкой (1,0,0,0,0,0), обозначим его e0. Вероятности состояний на следующем шаге – это строка e0P, где Р –матрица с определенными в условии компонентами, сумма вероятностей в каждой ее строке равна 1. 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 3/4 0 1/4 0 0 0 0 7/8 0 1/8 0 0 0 0 15/16 0 1/16 0 0 0 0 0 1 У данного процесса имеется поглощающее состояние 5 (нумерация с нуля). Для процессов с одним поглощающим состоянием правило (вот например здесь, http://www.nsu.ru/phorum/read.php?f=6&t=11649&a=1) –берем матрицу Q , вычеркивая строку и столбец с номером поглощающего состояния; составляем I-Q, где I единичная матрица (размера у нас 5); 1 -1 0 0 0 - 1/2 1 - 1/2 0 0 0 - 3/4 1 - 1/4 0 0 0 - 7/8 1 - 1/8 0 0 0 - 15/16 1 находим (I-Q)-1, находим сумму элементов i-й строки, это и будет среднее время достижения поглощающего состояния из i-го. (I-Q)-1: 341 680 452 128 16 340 680 452 128 16 339 678 452 128 16 336 672 448 128 16 315 630 420 120 16 Находим сумму элементов нулевой строки (это ответ), и суммы элементов остальных строк (для проверки) T0=1617 T1=1616 T2=1613 T3=1600 T4=1501 Проверка состоит в том, что по формуле условного матожидания Ti=pi,i+1Ti+1+ pi,i-1Ti-1+1 (потрачен один шаг, и попали либо в состояние i+1, откуда в среднем Ti+1 шагов, либо в состояние i-1, откуда в среднем Ti-1 шагов. Из самого поглощающего состояния -0 шагов. Проверка сошлась. Решение: 1617 шагов (в условии не сказано, что это дни. Ну в общем единиц времени) Решение. Надо сравнить 4 варианта марковских цепей (i*=1,2,3,4) В каждом из этих случаев матрица P другая, схема расчетов та же. i*=1 P 0 1 0 0 0 0 0 0 1 0 0 0 0 3/4 0 1/4 0 0 0 0 3/4 0 1/4 0 0 0 0 7/8 0 1/8 0 0 0 0 0 1 I-Q 1 -1 0 0 0 0 1 -1 0 0 0 -0,75 1 -0,25 0 0 0 -0,75 1 -0,25 0 0 0 -0,875 1 Фунд.матрица (I-Q)^(-1) 1 76 100 32 8 T0=217 0 76 100 32 8 216 0 75 100 32 8 215 0 72 96 32 8 208 0 63 84 28 8 183 i*=2 P 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 0 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 3/4 0 1/4 0 0 0 0 0 1 I-Q 1 -1 0 0 0 -0,5 1 -0,5 0 0 0 0 1 -1 0 0 0 -0,5 1 -0,5 0 0 0 -0,75 1 Фунд.матрица (I-Q)^(-1) 2 2 5 8 4 T0=21 1 2 5 8 4 20 0 0 5 8 4 17 0 0 4 8 4 16 0 0 3 6 4 13 i*=3 P 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 3/4 0 1/4 0 0 0 0 0 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 0 1 I-Q 1 -1 0 0 0 -0,5 1 -0,5 0 0 0 -0,75 1 -0,25 0 0 0 0 1 -1 0 0 0 -0,5 1 Фунд.матрица (I-Q)^(-1) 5 8 4 2 2 T0=21 4 8 4 2 2 20 3 6 4 2 2 17 0 0 0 2 2 4 0 0 0 1 2 3 i*=4 P 0 1 0 0 0 0 1/2 0 1/2 0 0 0 0 3/4 0 1/4 0 0 0 0 7/8 0 1/8 0 0 0 0 0 0 1 0 0 0 0 0 1 I-Q 1 -1 0 0 0 -0,5 1 -0,5 0 0 0 -0,75 1 -0,25 0 0 0 -0,875 1 -0,125 0 0 0 0 1 Фунд.матрица (I-Q)^(-1) 26 50 32 8 1 T0=117 25 50 32 8 1 116 24 48 32 8 1 113 21 42 28 8 1 100 0 0 0 0 1 1 Результаты T0 – среднее время достижения вершины –наилучшие для ситуаций i*=2 и i*=3 , по 21 шагу. Ответ: на 2й или 3й стоянке. Решение...Посмотреть предложения по расчету стоимости