Вероятность появления трехсимвольной строки в случайно сгенерированном пароле

Question

Если у вас есть случайно сгенерированный пароль, состоящий только из буквенно-цифровых символов, длиной 12, и сравнение выполняется без учета регистра (то есть 'A' == 'a'), какова вероятность того, что одна конкретная строка длиной 3(например, «ABC») появится в этом пароле?

Я знаю, что общее количество возможных комбинаций составляет (26 + 10) ^ 12, но кроме этого я немного растерялся.Объяснение математики также было бы очень полезно.

Answer 1

Строка "abc" может появляться в первой позиции, что делает строку похожей на это:

abcXXXXXXXXX

... где X может быть любой буквой или цифрой. (26 + 10) ^ 9 таких строк.

Может появиться во второй позиции, что делает строку похожей на:

XabcXXXXXXXX

И есть (26 + 10) ^ 9 таких строк.

Поскольку «abc» может появляться в любом месте с первой по десятую позиции, таких строк может быть 10 * 36 ^ 9.

Но это переоценивает, потому что он считает (например) строки, как это дважды:

abcXXXabcXXX

Итак, нам нужно посчитать все строки, подобные этой, и вычесть их из нашей общей суммы.

Поскольку в этом шаблоне 6 X, есть 36 ^ 6 строк, соответствующих этому шаблону.

Я получаю 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 таких шаблонов. (Если первый «abc» находится в начале, второй может быть в любом из 7 мест. Если первый «abc» находится на втором месте, второй может быть в любом из 6 мест. И т. Д.)

Итак, вычтите 28 * 36 ^ 6.

... но это вычитает слишком много, потому что он вычитал из строк три раза, а не один раз:

abcXabcXabcX

Итак, мы должны добавить обратно в строки, как это, дважды. Я получаю 4 + 3 + 2 + 1 + 3 + 2 + 1 + 2 + 1 + 1 = 20 из этих паттернов, что означает, что мы должны добавить обратно в 2 * 20 * (36 ^ 3).

Но эта математика насчитала эту строку четыре раза:

abcabcabcabc

... поэтому мы должны вычесть 3.

Окончательный ответ:

10*36^9 - 28*36^6 + 2*20*(36^3) - 3

Разделите это на 36 ^ 12, чтобы получить свою вероятность.

См. Также Принцип включения-исключения . И дайте мне знать, если я сделал ошибку в моем подсчете.

Answer 2

Если A не равно C, вероятность P(n) из ABC в строке длиной n (при условии, что каждый буквенно-цифровой символ одинаково вероятен) равна

P(n)=P(n-1)+P(3)[1-P(n-3)]

, где

P(0)=P(1)=P(2)=0 and P(3)=1/(36)^3

Answer 3

Чтобы расширить ответ Пола Р. Вероятность (для одинаково вероятных результатов) - это число возможных результатов вашего мероприятия, деленное на общее количество возможных результатов.

Есть 10 возможных мест, где строка длины 3 может быть найдена в строке длины 12. И есть еще 9 мест, которые могут быть заполнены любыми другими буквенно-цифровыми символами, что приводит к возможностям 36^9. Таким образом, число возможных результатов вашего мероприятия составляет 10 * 36^9.

Разделите это на общее количество результатов 36^12. И ваш ответ 10 * 36^-3 = 0.000214

РЕДАКТИРОВАТЬ: Это не совсем правильно. В этом решении некоторые случаи учитываются дважды. Однако они только вносят очень малый вклад в вероятность, поэтому этот ответ по-прежнему верен до 11 знаков после запятой. Если вы хотите получить полный ответ, см. Ответ Немо.