Проблема с вероятностью ошибки на python
Пишу код, имитирующий генерацию ошибок в неком канале, и для собственно генерации используются модели на цепях Маркова. Моделей всего три: Гильберта, Эллиота-Гильберта и Смита-Боуэна-Джойса. Для описания конкретной проблемы возьмём только первые две модели.
Сам канал представляет собой длинный массив, состоящий из условных сигналов, принимающих значения 1 или 0, где 0 - отсутствие ошибки, а 1 - её наличие. Каждый элемент массива - условный "бит", который может быть как "хорошим", так и "плохим"
Начнём с модели Гильберта: у канала есть два состояния, хорошее и плохое. Канал находится в "хорошем" состоянии по умолчанию. В этом "хорошем" состоянии канал не будет генерировать ошибок, однако существует некоторая вероятность, что канал перейдёт из "хорошего" в "плохое" состояние. В "плохом" состоянии канал каждый новый "бит" может с некоторой вероятностью испортится (т.е. стать 1). Но так же с некоторой вероятностью канал может после этого вернутся в "хорошее" состояние и так далее до конца длины канала. Таким образом, мы получаем три необходимые случайные величины: вероятность ошибки в плохом состоянии (Eps), вероятность остаться в хорошем состоянии (p00) и вероятность остаться в плохом состоянии (p11). Собственно функция, описанная ниже, делает то что нужно, и в конце подсчитывает итоговую вероятность ошибки в уже сгенерированном канале
def hilbert_model(length, channel, err_probability, p00, p11):
flag = True # флаг состояния, True - хорошее, False - плохое
true_err1 = 0 # фактические вероятности ошибки
true_err2 = 0
for i in range(length):
t = r.random() # случайное число для определения вероятности перехода из одного состояния в другое
if flag == True:
if t >= p00: # переход в плохое состояние
flag = False
true_err1 = r.random()
if true_err1 <= err_probability: # вероятность получения ошибки
channel.append(1)
else:
channel.append(0)
else: # остаться в хорошем состоянии
channel.append(0)
else:
if t >= p11: # возвращение в хорошее
flag = True
channel.append(0)
else: # остаться в плохом состоянии
true_err2 = r.random()
if true_err2 <= err_probability: # вероятность получения ошибки
channel.append(1)
else:
channel.append(0)
count = 0.0
for i in range(len(channel)):
if channel[i] == 1:
count += 1
err_probability_real = count / len(channel) # итоговая вероятность ошибки в канале
return err_probability_real
У этой модели так же существует рукописная формула вычисления вероятности, с которой я сверяюсь.
error_channel_h = []
length = 1000000
Eps = r.uniform(0, 0.5)
p00_1 = r.uniform(0.3, 0.99) # вероятность остаться в хорошем состоянии
p11_1 = r.uniform(0.5, 0.99)
teor1 = (Eps * (1 - p00_1)) / (1 - p00_1 + 1 - p11_1)
print(teor1)
*> 0.17361527424884937*
hilbert_model(length,error_channel_h,Eps,p00_1,p11_1)
*> 0.173726*
Вероятности здесь задаются мной, но действуют по принципу: Вероятность получить ошибку равна примерно 50%, а вероятности остаться в состоянии должны быть больше, чем вероятность перейти в другое состояние.
Вероятности в "теоретической" и "практической" версии Модели Гильберта после множества перезапусков и генерации новых случайных величин совпадают от трёх знаков и больше, и это хороший результат. Его можно улучшить, увеличив дину канала, но это слишком затратно - достаточно трёх знаков после запятой. Но проблема во второй модели - Эллиота-Гильберта
От первой модели Эллиот-Гильберт отличается лишь наличием вероятности ошибки в "хорошем" состоянии - она существенно ниже, но есть. Поэтому я взял код функции, генерирующий ошибки по модели Гильберта, и модифицировал её с необходимым условием.
def elliot_hilbert_model(length, channel, err_probability1, err_probability2, p00, p11):
flag = True # флаг состояния, True - хорошее, False - плохое
for i in range(length):
true_err1 = 0 #фактические вероятности ошибки
true_err2 = 0
true_err3 = 0
true_err4 = 0
t = r.random() # случайное число для определения вероятности перехода из одного состояния в другое
if flag == True:
if t >= p00: # переход в плохое состояние
flag = False
true_err1 = r.random()
if true_err1 <= err_probability1: # вероятность получения ошибки
channel.append(1)
else:
channel.append(0)
else: # остаться в хорошем состоянии
flag = True
true_err2 = r.random()
if true_err2 <= err_probability2:
channel.append(1)
else:
channel.append(0)
else:
if t >= p11: # возвращение в хорошее
flag = True
true_err3 = r.random()
if true_err3 <= err_probability2: # вероятность получения ошибки в хорошем состоянии, снижена
channel.append(1)
else:
channel.append(0)
else: # остаться в плохом состоянии
flag = False
true_err4 = r.random()
if true_err4 <= err_probability1: # вероятность получения ошибки
channel.append(1)
else:
channel.append(0)
count = 0.0
for i in range(len(channel)):
if channel[i] == 1:
count += 1
err_probability_real = count / len(channel) # итоговая вероятность ошибки в канале
return err_probability_real
Однако в случае с моделью Эллиота-Гильберта совпадений практически нет - теоретическая и практическая вероятность совпадают в лучшем случае на один знак, а зачастую имеют большой разброс или вообще не сходятся.
error_channel_eh = []
length = 500000
Eps1 = r.uniform(0, 0.5)
Eps2 = r.uniform(0, 0.1)
p00_2 = r.uniform(0.5, 0.99) # вероятность остаться в хорошем состоянии
p11_2 = r.uniform(0.5, 0.99)
teor3 = (Eps1 * (1 - p11_2) + Eps2 * (1 - p00_2)) / (1 - p00_2 + 1 - p11_2)
#teor3 = Eps1*((1-p11_2)/(1-p11_2+1-p00_2)) + Eps2*((1-p00_2)/(1-p11_2+1-p00_2))
*> 0.16668092928351588 *
elliot_hilbert_model(length, error_channel_eh, Eps1, Eps2, p00_2, p11_2)
*> 0.017138 *
В общем то, проблема в том что функция не менялась радикально, но перестала выполнять свою задачу. Ошибки в теоретических формулах быть не может - проблема только в коде. Прошу знатоков указать на ошибку и, если можно, подсказать как оптимизировать код.