Умова

Дівчинка починає маршрут великими сходами, які складаються з \(K\) сходинок. Вона може ставати або на наступну сходинку або перестрибувати через одну. З якою імовірністю вона при цьому потрапить на \(k\)-ту \(\left( {k < K} \right)\) сходинку?

Розв’язок

Простір елементарних подій описаного стохастичного експерименту задамо наступним чином: \[\Omega = \{ ({a_1},{a_2},...{a_n}) ~|~ {a_{i + 1}} > {a_i}, ~ {a_{i + 1}} - {a_i} \le 2, ~ {a_n} = K\}, \] де індекси відповідають номерам кроків дівчинки, а елементи відповідають номерам сходинок. Подію \(A = \){дівчинка потрапила на \(k\)-ту сходинку} формалізуємо так: \[A = \{ ({a_1},{a_2},...{a_n}) ~|~ {a_{i + 1}} > {a_i}, ~ {a_{i + 1}} - {a_i} \le 2, ~ {a_n} = K, ~ \exists j:{a_j} = k\}. \] Кількість способів рахуватимемо таким чином: на першу сходинку дівчинка може потрапити одним способом – з «нульового рівня», на другу двома: з «нульового рівня» або через першу. На кожну наступну сходинку кількість способів потрапити на неї буде рівна сумі способів попадання на дві попередні сходинки. Тому на \(K\)-ту сходинку можна потрапити \({F_K}\) способами, де \({F_K}\) – це \(K\)-ий член послідовності Фібоначчі \({F_1} = 1\), \({F_2} = 2\), . . . , \({F_i} = {F_{i - 1}} + {F_{i - 2}}\), . . . Тобто \(\left| \Omega \right| = {F_K}\), аналогічно \(\left| A \right| = {F_k}\). За класичним визначенням ймовірності \[P\left( A \right) = \frac{{{F_k}}}{{{F_K}}}.\]

Відповідь: \(P\left( A \right) = \dfrac{{{F_k}}}{{{F_K}}}\), де \({F_k}\) – це \(k\)-ий член послідовності Фібоначчі \({F_1} = 1\), \({F_2} = 2\), . . . , \({F_i} = {F_{i - 1}} + {F_{i - 2}}\), . . .

Перевірка Для перевірки отриманого результату напишемо просту програму мовою Javascript:

function Fibonacci(i){
    if(i<3) return i;
    return Fibonacci(i-1) + Fibonacci(i-2);
}

const K=8;
const k=5;

let m = 0;
let n = 100000000;

function step(s){
    if(Math.random()<0.5) s++;
    else s += 2;
	return s;
}

for(let i=0; i<n; i++){
    for(let s = 0; s<K; s = step(s)){
        if(s == k) m++;
    }    
}

console.log('m/n =', m/n);
console.log('F(k)/F(K) =', Fibonacci(k)/Fibonacci(K));

Функція \(Fibonacci(i)\) повертає \(i\)-те число Фібоначчі. Константи \(K=8\) та \(k=5\) є обраними нам параметрами моделювання. Число \(n = 100000000\) є кількістю експериментів, які ми проведемо. Функція \(step(s)\) збільшує аргумента або на 1, або на 2, що відповідає величині можливого кроку (кожен з цих двох варіантиів обирається з однаковою ймовірністю 0.5). В циклі \(for\) проводимо моделювання експериментів з підрахунком кількості тих, коли відбувається наступання на содинку з номером \(k\).

Результат роботи цієї програми:

m/n = 0.65628228
F(k)/F(K) = 0.23529411764705882

Подив викликає розбіжність результату моделювання (відносна частота) та обчисленої ймовірності. Що ж не так? Спробуємо проаналізувати. Перед тим, як читати далі, спробуйте самостійно подумати, в чому може бути причина ;)

Якщо уважно подивитись на код програми, то можна помітити, що фактично результат її роботи не залежить від константи \(K=8\) (див. рядок 19), дійсно, перевірка в рядку 20 ніяк не враховує, до якого саме значення \(K\) працює цикл (рядок 19). Натомість отримана нами відповідь \(P\left( A \right) = \dfrac{{{F_k}}}{{{F_K}}}\) явно залежить від \(K=8\). Що ж зроблено неправильно? Помилка у розв'язанні чи у моделюванні (при перевірці)? І знову пропонуємо читачеві зробити паузу і подумати над цим самостійно перед тим, як читати далі...

Насправді помилки немає, є лише різне тлумачення умови під час розв’язування задачі та під час перевірки. Коли під час розв'язування ми записали потужність простору елементарних подій та за класичним визначенням записали шукану ймовірність, то, очевидно, ми мали на увазі, що усі елементарні наслідки є рівноможливими, тобто діяли так, наче із усіх можливих наборів кроків (маршрутів), які приведуть дівчинку на \(K\)-ту сходинку, вона на самому початку обирає один з "маршрутів" навмання, а потім уже слідує обраному плану. Коли ж ми робили перевірку, то дівчинка кожного разу обирала навмання величину кроку (на наступну сходинку чи через одну) та ще й й умова зупинки (умова завершення циклу в рядку 19) могла при цьому виконатись як при ставанні на останню \(K\)-ту сходинку, так і при переступанні через неї!

Тепер, коли ми зрозуміли причину розбіжності результатів обчислення та моделювання (перевірки), залишається відповісти на два запитання:

1. Як написати програму для перевірки отриманого результату (ймовірності)?
2. Якою мала б бути умова та розв’язання нашої задачі, щоб наведений вище код був її перевіркою?

1) Для коду насправді потрібна лише функція, яка б підтвердила, що кількість способів розкласти число \(K\) на доданки (1 та 2) і є відповідним числом Фібоначчі. Це буде звичайний перебір, а не моделювання (нічого випадкового):

const K = 8;
let counter = 0;

function printSums(n, result = '') {
    if (n < 0) {
        return; // якщо сума перевищує задане число, повертаємось
    }
    if (n === 0) {
        console.log(result.slice(0, -1)); // якщо досягнуто задане число, друкуємо результат
        counter++;
        return;
    }
    
    // додаємо 1 до суми
    printSums(n - 1, result + '1+');
    // додаємо 2 до суми
    printSums(n - 2, result + '2+');
}

// Виклик функції з числом K
printSums(K);
console.log("Усього: ", counter);

Результат роботи цієї програми:

1+1+1+1+1+1+1+1
1+1+1+1+1+1+2
1+1+1+1+1+2+1
1+1+1+1+2+1+1
1+1+1+1+2+2
1+1+1+2+1+1+1
1+1+1+2+1+2
1+1+1+2+2+1
1+1+2+1+1+1+1
...
2+2+1+2+1
2+2+2+1+1
2+2+2+2
Усього:  34

Це і є 8-е число Фібоначчі.

2) А от щодо того, якою мала б бути умова та розв’язання нашої задачі, щоб найперший код був її перевіркою (0.65628228), то після аналізу того коду можна зрозуміти, що йдеться про такий рух сходинками, коли на кожному кроці дівчинка з однаковою ймовірністю робить вибір на користь або стати на наступну сходинку, або переступити через неї. Обчислення ймовірності того, що дівчинка при цьому потрапить на \(k\)-ту \(\left( {k < K} \right)\) сходинку, виходить за межі класичного визначення ймовірності, але код все-таки наведемо:

function Probability(i){
    if(i == 1) return 0.5;
    if(i == 2) return 0.5 + 0.5*0.5;
    return Probability(i-1)*0.5 + Probability(i-2)*0.5;
}

const K=8;
const k=5;

let m = 0;
let n = 10000000;

function step(s){
    if(Math.random() < 0.5) s++;
    else s += 2;
    return s;
}

for(let i=0; i<n; i++){    
    for(s = 0 ; s<K; s = step(s)){
        if(s == k) m++;
    }
}

console.log("m/n =", m/n)
console.log("Probability =", Probability(k))

Результат роботи цієї програми:

m/n = 0.6562369
Probability = 0.65625