Создан заказ №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).
Доказательство. (работа была выполнена специалистами Автор 24) Поместим начало координат куба в точку 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й стоянке.
Решение...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
16 сентября 2016
Заказ завершен, заказчик получил финальный файл с работой
5
Начало решения Расстоянием Хэмминга между двумя двоичными последовательностями одинаковой длины называется число разрядов.jpg
2021-04-06 02:25
Последний отзыв студента о бирже Автор24
Общая оценка
4.5
Положительно
Очень рекомендую автора, решает сложные задачи по математике, всегда если появляется вопрос , отвечает быстро и развёрнуто) спасибо большое за помощь
Хочешь такую же работу?
300 ₽
