fy"> x s , x ( s +1, w )),
де x (s, w) - послідовність незалежних випадкових величин, визначеним на деякому вероятностном просторі (W, U, P) w? W - елементарні випадкові події, причому M {g (s, x, w)}=0 при будь-яких x? E 1. Для вирішення цього завдання Роббінса-Монро запропонована наступна процедура
s +1= x s + c s f s +1 ( x s , w ),
де x 0 - довільне число. Послідовність позитивних чисел cs задовольняє умовам Роббінса-Монро
Перша з цих умов необхідно для збіжності xs до x0 при s ®? навіть за відсутності випадкових помилок. Іншими словами, необхідно, щоб cs були не надто малими. з іншого боку cs повинні бути не дуже великими, в іншому випадку випадкові помилки порушують цю збіжність, тому необхідно виконання другої умови (1.4.5).
Теорема 1.1. Нехай виконані нерівності:
) sup f ( x ) ( xx 0) <0" e > 0,
e << i> x-x 0 << i> e - 1,
) f 2 ( x ) + M { g 2 ( s, x, w )} << i> b (1 - x 2), b> 0 - постійна.
Тоді при виконанні умов Роббінса-Монро для будь-якого x? Е1, процес xs, який визначається (1.4.4), сходиться з імовірністю 1 при s ®? до кореня рівняння f (x)=0, тобто до x0 і
P { lim x s = x 0}=1.
Можна також показати, що xs сходиться до x0 в середньоквадратичному.
Алгоритм Літвакова
Алгоритм Літвакова дозволяє відшукати близьке до оптимального значення вектора параметрів за допомогою наступної процедури
прі не оптимальному.
Сутність його полягає в наступному.
Нехай дана навчальна вибірка об'єму. Поклавши і, де а - деяка постійна, здійснюється ітеративний процес обчислень за формулою на п -му кроці знаходиться, яке приймається в якості нового початкової умови і процес обчислень триває з тієї ж самої вибірці.
В результаті отримуємо оцінку. Продовжуючи цей процес до -раз, знайдемо оцінку. Результат Літвакова і полягає в тому, що оцінка для досить великих до (точніше) наближається до. У багатьох практичних завданнях до не перевищує 5.
Алгоритм Кестена
Відомо, що швидкість збіжності рекурентних імовірнісних алгоритмів типу при визначається статечним знаком - це наслідок вплив перешкод. Якби перешкоди були відсутні, то слід було б і швидкість збіжності при цьому зростає і визначається показовим законом.
Сутність алгоритму Кестена полягає в тому, що далеко від роль перешкод при вимірах мала і різниця буде мати постійний знак, а поблизу знак вже істотно залежить від перешкод і буде змінюватися. Тому в алгоритмі Кестена не змінюється, коли різниця вже не змінює свого знака, і змінюється, якщо знак змінюється.
Щоб визначити різницю необхідно принаймні два спостереження. Тому і вибираються довільно (зазвичай рівними одиниці). Подальше визначен...
