Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1.
1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
Здравствуйте, nikov, Вы писали:
N>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
1001 / 2 ^ 999
N>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
1 / 2 ^ 1000 + 999 / 2^1001
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, nikov, Вы писали:
N>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? S>1001 / 2 ^ 999
N>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов? S>1 / 2 ^ 1000 + 999 / 2^1001 1 / 2 ^ 999 + 999 / 2^1001
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, Smal, Вы писали:
S>>Здравствуйте, nikov, Вы писали:
N>>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? S>>1001 / 2 ^ 999
??? что-то большая...
1/2 ^ 1000
N>>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов? S>>1 / 2 ^ 1000 + 999 / 2^1001 S>1 / 2 ^ 999 + 999 / 2^1001
Здравствуйте, Neila, Вы писали:
N>Здравствуйте, Smal, Вы писали:
S>>Здравствуйте, Smal, Вы писали:
S>>>Здравствуйте, nikov, Вы писали:
N>>>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? S>>>1001 / 2 ^ 999
N>??? что-то большая... N>1/2 ^ 1000
Перепроверьте
N>>>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов? S>>>1 / 2 ^ 1000 + 999 / 2^1001 S>>1 / 2 ^ 999 + 999 / 2^1001
N>ИМХО 1/2 ^1000 * 1/2 ^ 1000
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, Neila, Вы писали:
N>>Здравствуйте, Smal, Вы писали:
S>>>Здравствуйте, Smal, Вы писали:
S>>>>Здравствуйте, nikov, Вы писали:
N>>>>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>>>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? S>>>>1001 / 2 ^ 999
N>>??? что-то большая... N>>1/2 ^ 1000 S>Перепроверьте
А в чем проблема
Вероятность одного события 1/2
Вероятность второго 1/2 , а если вместе с первым 1/2 * 1/2 (логическое "и" )
Хммм хотя мы может получить последовательность больше чем тысяча, так что вероятность выше.
Но формулу не помню и смотреть сейчас некогда...
N>>>>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов? S>>>>1 / 2 ^ 1000 + 999 / 2^1001 S>>>1 / 2 ^ 999 + 999 / 2^1001
N>>ИМХО 1/2 ^1000 * 1/2 ^ 1000
S>Это равно 1/2^2000. Такая строка только одна?
Опечатка имел ввиду 1/2 ^1000 * 1/2 ^ 1 то бишь
Вероятность цепочки 1/2 ^1000 и умножение на вероятность следующего.
Хотя тоже нет помому там что-то хитрее... Эх надо повторять.....
Здравствуйте, Neila, Вы писали:
N>>>>>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>>>>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? S>>>>>1001 / 2 ^ 999
N>>>??? что-то большая... N>>>1/2 ^ 1000 S>>Перепроверьте
N>А в чем проблема N>Вероятность одного события 1/2 N>Вероятность второго 1/2 , а если вместе с первым 1/2 * 1/2 (логическое "и" ) N>Хммм хотя мы может получить последовательность больше чем тысяча, так что вероятность выше. N>Но формулу не помню и смотреть сейчас некогда...
Тут я наврал. Хотя ваша формула тоже не верна.
N>>>>>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов? S>>>>>1 / 2 ^ 1000 + 999 / 2^1001 S>>>>1 / 2 ^ 999 + 999 / 2^1001
А тут, ИМХО, всё верно. Некоторые комбинации считаются несколько раз.
N>>>ИМХО 1/2 ^1000 * 1/2 ^ 1000
S>>Это равно 1/2^2000. Такая строка только одна?
N>Опечатка имел ввиду 1/2 ^1000 * 1/2 ^ 1 то бишь N>Вероятность цепочки 1/2 ^1000 и умножение на вероятность следующего. N>Хотя тоже нет помому там что-то хитрее... Эх надо повторять.....
Здравствуйте, nikov, Вы писали:
N>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? N>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
Думаю так:
Имеем равновероятностный набор бит.
1)Значит вероятность получить строку длиной в 1000 одинаковых бит будет равна:
Количество вариантов где подряд 1000 одинаковых бит, деленное на полное количество вариантов. Умноженное на 2, так как не оговаривается какие имеено значения 0, или 1.
Ответ: 2000 / (2^2000)
2)В количестве 2000 бит может только 4 случая, когда встретится строка из 1000 одинаковых бит 2 раза. 00, 01, 10, 11
Значит количество вариантов с одинаковой 1000 бит подряд из предыдущей задачи следует уменьшить на 4.
Ответ: 1996 / (2^2000)
Позвольте исправиться
N>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
1002 / 2^1000
N>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, nikov, Вы писали:
N>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? N>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
S>Думаю так: S>Имеем равновероятностный набор бит. S>1)Значит вероятность получить строку длиной в 1000 одинаковых бит будет равна: S>Количество вариантов где подряд 1000 одинаковых бит, деленное на полное количество вариантов. Умноженное на 2, так как не оговаривается какие имеено значения 0, или 1. S>Ответ: 2000 / (2^2000) S>2)В количестве 2000 бит может только 4 случая, когда встретится строка из 1000 одинаковых бит 2 раза. 00, 01, 10, 11 S>Значит количество вариантов с одинаковой 1000 бит подряд из предыдущей задачи следует уменьшить на 4. S>Ответ: 1996 / (2^2000)
И ещё раз (благодаря Seon). Совсем забыл про случаи из двух подстрок по 1000.
N>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
S>1002 / 2^1000
(1002 * 2^1000 — 2) / 2^2000
N>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
S>1003 / 2^1001
(1003 * 2^999 — 2) / 2^2000
Здравствуйте, Smal, Вы писали:
N>>>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>>>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
S>>1002 / 2^1000 S>(1002 * 2^1000 — 2) / 2^2000
N>>>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
S>>1003 / 2^1001 S>(1003 * 2^999 — 4) / 2^2000
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, Seon, Вы писали:
S>>2)В количестве 2000 бит может только 4 случая, когда встретится строка из 1000 одинаковых бит 2 раза. 00, 01, 10, 11
N>Почему же? Например, если строка состоит из 2000 нулей, то там можно найти 1001 подстроку длиной 1000, состоящую из одинаковых битов.
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, nikov, Вы писали:
N>>Здравствуйте, Seon, Вы писали:
S>>>2)В количестве 2000 бит может только 4 случая, когда встретится строка из 1000 одинаковых бит 2 раза. 00, 01, 10, 11
N>>Почему же? Например, если строка состоит из 2000 нулей, то там можно найти 1001 подстроку длиной 1000, состоящую из одинаковых битов.
S>А, ну если так....
Тогда эта вероятность равна сумме вероятностей получить строки длиной в 1000, 1001, 1002, 1003 и т.д. символов..
Формулой затрудняюсь выразить...
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, nikov, Вы писали:
N>>>Здравствуйте, Seon, Вы писали:
S>>>>2)В количестве 2000 бит может только 4 случая, когда встретится строка из 1000 одинаковых бит 2 раза. 00, 01, 10, 11
N>>>Почему же? Например, если строка состоит из 2000 нулей, то там можно найти 1001 подстроку длиной 1000, состоящую из одинаковых битов.
S>>А, ну если так....
S>Тогда эта вероятность равна сумме вероятностей получить строки длиной в 1000, 1001, 1002, 1003 и т.д. символов.. S>Формулой затрудняюсь выразить...
А точнее, вероятность получить строку из 1000 одинаковых символов подряд, минут сумма вероятностей получить строки из 1001, 1002, 1003 и т.д.
Формула типа:
2 * (2^1000) / (2^2000) — SUMM(2 * (2^(1000 + i)) / (2^2000), i = 1 до 1000)
Здравствуйте, Seon, Вы писали:
S>Тогда эта вероятность равна сумме вероятностей получить строки длиной в 1000, 1001, 1002, 1003 и т.д. символов.. S>Формулой затрудняюсь выразить...
Давайте все вместе разберемся.
1. Вероятность того, что начало подстроки совпадает с началом строки.
Здравствуйте, Smal, Вы писали:
S>2. Вероятность того, что начало подстроки совпадает с началом строки.
S>2 * 2 ^ 999 / 2 ^ 2000 = 2 ^ 1000 / 2 ^ 2000
S>999 — потому, что бит в позиции 1000 != бит в позиции 1001.
S>+ Вероятность того, что конец подстроки совпадает с концом строки.
S>(аналогично)
S>2 * 2 ^ 999 / 2 ^ 2000 = 2 ^ 1000 / 2 ^ 2000
S>+ (Вероятность того, что строка начинается в позиции k.) * 999 S>(2 * 2 ^ 998 / 2 ^ 2000) * 999 = 999 * 2 ^ 999 / 2 ^ 2000
S>- 2 / 2000 (два варианта, которые мы посчитали дважды: 11...100...1)
Мы эти варианты и единожды считать не должны
S>Итого: (2 ^ 1001 + 999 * 2 ^ 999 — 4) / 2 ^ 2000
Здравствуйте, nikov, Вы писали:
N>Есть строка S, состоящая из 2000 битов, сконструированная случайным образом так, что каждый бит независимо от дргих равновероятно может иметь значение 0 или 1. N>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов? N>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
Для решения задачи надо подсчитать число возможных строк, с указанными условиями.
N>1) Какова вероятность того, что в S найдется подстрока длиной 1000, состоящая из одинаковых битов?
Найдем сначала число строк S_0 у которых есть подстрока из нулей длины 1000.
Обозначим через S_0(i) число строк, у которых i — самая первая позиция, с которой начинается подстрока из тысячи нулей. Ясно , что 1 <= i <= 1001, а также, что S_0 = S_0(1) + S_0(2) + ... S_0(1001)
Числа S_0(i) легко найти.
S_0(1) = 2^1000 Так как на оставшихся последние 1000 позизияй можно поставить любые числа 0 или 1
Рассмотрим случай, когда 1 < i <= 1001
В этом случае на позиции (i-1) должна стоять 1, а на всех остальных 999 позициях может стоять что угодно
Таким образом S_0(i) = 2^999 при 1 < i <= 1001
Итак
S_0 = 2^1000 + 1000*2^999 = 1002*2^999
Аналогичным образом пусть S_1 число строк у которых есть подстрока из единиц длины 1000.
Ясно в силу симметрии, что S_0 = S_1.
Однако эти два множества пересекаются по двум строкам: 111..1000...0 и 000..0111...1
Таким образом S = S_0 + S_1 — 2 = 1002*2^1000 — 2
А значит ответ: вероятность P = S/2^2000 = (1002*2^1000 — 2)/2^2000
N>2) Какова вероятность того, что в S найдется ровно одна подстрока длиной 1000, состоящая из одинаковых битов?
Найдем сначала число строк S_0 у которых эта единственная подстрока длины 1000 состоит из нулей.
Обозначим через S_0(i) число тех из этих строк, у которых данная подстрока начинается с позиции i.
Ясно , что 1 <= i <= 1001, а также, что S_0 = S_0(1) + S_0(2) + ... S_0(1001)
Числа S_0(i) легко найти.
S_0(1) = 2^999 Так как на 10001 позиции должна стоять 1, а на оставшихся последних 999 позизиях можно поставить любые числа 0 или 1
S_0(1001) = 2^999 — 1 Так как на 10000 позиции должна стоять 1, а на оставшихся первых 999 позизиях можно поставить любые числа 0 или 1, кроме одних единиц
Рассмотрим случай, когда 1 < i < 1001
В этом случае на позициях (i-1) и ( i + 1000 ) должна стоять 1, а на всех остальных 998 позициях может стоять что угодно. Таким образом S_0(i) = 2^998 при 1 < i < 1001
Аналогичным образом пусть S_1 число строк у которых у которых единственная подстрока длины 1000 состоит из единиц.
Ясно в силу симметрии, что S_0 = S_1. Также ясно, что множества S_0 и S_1 не пересекаются.
Таким образом S = S_0 + S_1 = 2*S_0 = 1003*2^999 — 2
А значит ответ: вероятность P = S/2^2000 = (1003*2^999 — 2)/2^2000
