Кездейсоқ қимылдардың математикалық формалдануы

Кіріспе

Кездейсоқ қадамдардан тұратын жолды математикалық формализациялау. Математикада кездейсоқ жүріс, кейде "мастың қадамы" деп те аталады, – бұл кездейсоқ процесс, ол белгілі бір математикалық кеңістікте кездейсоқ қадамдардан тұратын жолды сипаттайды. Кездейсоқ жүрістің қарапайым мысалы – 0-ден басталатын бүтін сандар түзуіндегі кездейсоқ жүріс, онда әр қадам +1 немесе -1 тең мүмкіндікпен жасалады. Басқа мысалдарға сұйық немесе газ ішінде қозғалатын молекуланың траекториясы (Браун қозғалысын қараңыз), азық іздейтін жануардың іздеу жолы, құбылмалы акцияның бағасы және құмар ойыншының қаржылық жағдайы жатады. Кездейсоқ жүрістер инженерлік және экология, психология, компьютерлік ғылым, физика, химия, биология, экономика және социология сияқты көптеген ғылыми салаларда қолданылады. "Кездейсоқ жүріс" терминін алғаш рет 1905 жылы Карл Пирсон енгізді. Кездейсоқ жүрістерді Монте-Карло әдісімен модельдеуге болады.

Желілік кездейсоқ жүріс

Кездейсоқ жүріс үлгісі – бұл реттелген тордағы кездейсоқ жүріс, онда әр қадамда орналасу белгілі бір ықтималдық таралымы бойынша басқа нүктеге секіреді. Қарапайым кездейсоқ жүрісте орналасу тек тордың көршілес нүктелеріне секіріп, тор жолын құрайды. Жергілікті шекті тордағы қарапайым симметриялық кездейсоқ жүрісте орналасудың әрбір жақын көршісіне секіру ықтималдығы бірдей болады. Ең көп зерттелген мысал – d өлшемді бүтін сандар торындағы (кейде гиперкубтық тор деп аталатын) кездейсоқ жүріс. Егер күй кеңістігі шекті өлшемдермен шектелсе, кездейсоқ жүріс моделі қарапайым шекаралық симметриялық кездейсоқ жүріс деп аталады, ал көшу ықтималдықтары күйдің орналасуына байланысты, себебі шеттік және бұрыштық күйлерде қозғалыс шектелген.

Гетерогендік жалпылау

Гетерогендік кездейсоқ жүріс әр уақыт қадамында жергілікті секіру ықтималдығын анықтайтын кездейсоқ санды, содан кейін нақты секіру бағытын анықтайтын кездейсоқ санды тартады. Басты сұрақ – жасалған секірулерден кейін әр түрлі нүктеде қалу ықтималдығы және бұл ықтималдықтың саны шексіз үлкенге жақындағандағы лимиті.

Жоғары өлшемдер

Жоғары өлшемдерде кездейсоқ жүріп өткен нүктелер жиыны қызықты геометриялық қасиеттерге ие. Шын мәнінде, дискретті фрактал пайда болады, яғни үлкен масштабта стохастикалық өзіне ұқсастық көрсететін жиынтық. Кіші масштабта жүріс жүргізілген тордың нәтижесінде туындаған "тігіршіктілік" байқалады. Кездейсоқ жүріс траекториясы – жүріс нүктеге келген уақытын ескермей, басып өткен нүктелер жиынтығы ретінде қарастырылады. Бір өлшемде траектория – жүріс ең төменгі және ең жоғары биіктікке жеткен арасындағы барлық нүктелер (екеуі де орташа есеппен бірдей шамада болады). Екі өлшемді жағдайды елестету үшін қалада кездейсоқ серуендеп жүрген адамды көзге елестетуге болады. Қала тиімді түрде шексіз және төртбұрышты тротуарлардың торынан тұрады. Әр қиылыста адам төрт мүмкін бағыттың бірін (бастапқыда таңдалған бағытты қоса алғанда) кездейсоқ таңдайды. Формальды түрде, бұл – бүтін координаттары бар жазықтықтағы барлық нүктелер жиынтығындағы кездейсоқ жүріс. Адамның бастапқы нүктеге қайта оралуы мүмкін бе деген сұраққа жауап беру үшін, бұл жоғарыда талқыланған деңгейлерді кесіп өту мәселесінің екі өлшемді нұсқасы. 1921 жылы Джордж Поля екі өлшемді кездейсоқ жүрісте адамның дерлік сөзсіз қайта оралатынын дәлелдеді, бірақ үш өлшем немесе одан жоғары өлшемдер үшін өлшемдер саны артқан сайын бастапқы нүктеге оралу ықтималдығы төмендейді. Үш өлшемде бұл ықтималдық шамамен 34%-ға төмендейді. Математик Шидзуо Какутани осы нәтижеге қатысты былай деді: "Мас адам үйіне жол табады, бірақ мас құс мәңгілікке адасып қалуы мүмкін". Поля осы мәселенің тағы бір түрін де қойған: "Егер екі адам бірдей бастапқы нүктеден шығып кетсе, олар қайтадан кездеседі ме?" Олардың орналасулары арасындағы айырмашылық (екі тәуелсіз кездейсоқ жүріс) де қарапайым кездейсоқ жүріс екенін көрсетуге болады, сондықтан олар екі өлшемді жүрісте дерлік сөзсіз қайтадан кездеседі, бірақ үш өлшем және одан жоғары өлшемдерде ықтималдық өлшемдер санымен азаяды. Пол Эрдош және Сэмюэл Джеймс Тейлор 1960 жылы төрт өлшемге тең немесе кіші өлшемдер үшін кез келген екі нүктеден басталатын екі тәуелсіз кездейсоқ жүрістің дерлік сөзсіз шексіз көп қиылыс нүктелері болатынын көрсетті, бірақ бес өлшемнен жоғары өлшемдерде олар дерлік сөзсіз тек шекті саны ғана қиылысады. Қадамдар саны артқан сайын екі өлшемді кездейсоқ жүріс үшін асимптотикалық функция Рейли таралымымен беріледі. Ықтималдық үлестірімі – бастапқы нүктеден радиусқа тәуелді функция, ал әр қадам үшін қадам ұзындығы тұрақты. Мұнда қадам ұзындығы 1 деп есептеледі, N – қадамдардың жалпы саны, ал r – бастапқы нүктеден радиус.

In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete fractal, that is, a set which exhibits stochastic self similarity on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed. The trajectory of a random walk is the collection of points visited, considered as a set with disregard to when the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height and the maximum height the walk achieved (both are, on average, on the order of ). To visualize the two dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the plane with integer coordinates. To answer the question of the person ever getting back to the original starting point of the walk, this is the 2 dimensional equivalent of the level crossing problem discussed above. In 1921 George Pólya proved that the person almost surely would in a 2 dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%. The mathematician Shizuo Kakutani was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever". Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?" It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2 dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. Paul Erdős and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often. The asymptotic function for a two dimensional random walk as the number of steps increases is given by a Rayleigh distribution. The probability distribution is a function of the radius from the origin and the step length is constant for each step. Here, the step length is assumed to be 1, N is the total number of steps and r is the radius from the origin.

Жекеленген нысандардың саны

Бір кездейсоқ жүргіншінің аралаған ерекше сайттарының саны шаршы және кубтық торлар, сондай-ақ фракталдар үшін кеңінен зерттелген. Бұл көрсеткіш тұтқынға алу және кинетикалық реакциялар мәселелерін талдауға көмектеседі. Сонымен қатар, ол тербеліс күйінің тығыздығымен, диффузиялық реакциялар процестерімен және экологиядағы популяциялардың таралуымен байланысты.

Ақпарат беру деңгейі

Гаусс кездейсоқ жүрісінің квадраттық қате қашықтығына қатысты ақпарат жылдамдығы, яғни оның квадраттық жылдамдық бұрмалау функциясы, келесідей параметрлік түрде беріледі:

Осыдан, -ты -дан кем биттері бар бинарлық кодты қолданып кодтау және оны күтілетін орташа квадраттық қатесі -дан кем болатындай қалпына келтіру мүмкін емес. Екінші жағынан, кез келген үшін, жеткілікті үлкен және ең көп дегенде түрлі элементтері бар бинарлық код табылады, осы кодтан -ты қалпына келтірудегі күтілетін орташа квадраттық қатесі -дан аспайды.

Нұсқалар

Таза кездейсоқ жүрістерге ұқсас, бірақ қарапайым құрылымын жалпылауға болатын стохастикалық процестердің бірнеше түрі қарастырылды. Таза құрылым тәуелсіз және бірдей үлестірілген кездейсоқ шамалармен анықталатын қадамдармен сипатталады. Кездейсоқ жүрістер графиктер, бүтін сандар, нақты сан сызығы, жазықтық немесе жоғары өлшемді векторлық кеңістіктер, қисық беттер немесе жоғары өлшемді Римандық көптүрліліктер және топтар сияқты әртүрлі кеңістіктерде жүзеге асырылуы мүмкін. Кездейсоқ қадамдарды кездейсоқ уақыттарда жасайтын кездейсоқ жүрістерді анықтау да мүмкін, мұндай жағдайда позицияның барлық t ∈ [0, +∞) уақыттары үшін анықталған болуы керек. Кездейсоқ жүрістердің нақты жағдайлары немесе лимиттері Леви ұшуы және Браун қозғалысы сияқты диффузиялық модельдерді қамтиды.

Өзін-өзі өзара әрекеттесетін кездейсоқ жүріс

Кездейсоқ жолдардың бірқатар қызықты модельдері бар, олардың әр қадамы өткенге күрделі тәсілмен байланысты. Барлығы әдеттегі кездейсоқ қозғалыстан гөрі аналитикалық түрде шешуге қиын; алайда, кездейсоқ қозғалатын кез келген модельдің мінез-құлқы компьютерлерді пайдалану арқылы анықталады. Мысалдар:
Өзін-өзі қиыстырмайтын жол. Ұзындығы n болатын өзін-өзі қиыстырмайтын жол – бұл бастапқы нүктеден басталатын, тек жақын орналасқан нүктелер арасында ғана өтетін, ешқашан бір нүктеге екінші рет оралмайтын және мұндай барлық жолдардың арасынан тең мүмкіндікпен таңдалатын кездейсоқ n қадамдық жол. Екі өлшемде өзін-өзі тұрақтандыру салдарынан, өзін-өзі қиыстырмайтын жолдың әдеттегі ұзындығы өте қысқа, ал жоғары өлшемдерде ол шексіз өседі. Бұл модель полимер физикасында жиі қолданылады (1960 жылдарынан бері). Шаршы өшірілген кездейсоқ жол. Күшейтілген кездейсоқ жол. Зерттеу процесі. Көп агенттік кездейсоқ жол.

Максималды энтропиясы кездейсоқ жүріс

Энтропия жылдамдығын максималдау үшін таңдалған кездейсоқ қозғалыс, локализациялық қасиеттеріне ие, және олар әлдеқайда күшті.

Қарым-қатынас кездейсоқ жүріп өту

Кездейсоқ жүріс, мұнда бір уақыттағы қозғалыс бағыты келесі уақыттағы қозғалыс бағытымен сәйкес келеді. Ол жануарлардың қозғалысын модельдеу үшін пайдаланылады.