Кіріспе
Кездейсоқ қарапайым жолдың моделі
Математикада, цикл өшірілген кездейсоқ жүріс – комбинаторика, физика және кванттық өріс теориясында маңызды қолданыстары бар кездейсоқ қарапайым жолдың моделі. Ол кездейсоқ ағаштың моделі болып табылатын бірыңғай жайылған ағашпен тығыз байланысты. Осы тақырыпты толығырақ қарастыру үшін кездейсоқ жүріске қараңыз.
Анықтама
G – кез келген граф және G-де n ұзындығы бар жол деп есептейік. Яғни, G-нің төбелері осындай және олар жиекпен байланысқан. Содан кейін, жолдың циклдерді өшіруі (loop erasure) – бұл жолдың барлық циклдарын хронологиялық тәртіппен өшіру арқылы құрылатын жаңа қарапайым жол. Формальды түрде, біз индекстерді индуктивті түрде анықтаймыз:
where "max" here means up to the length of the path The induction stops when for some we have
In words, to find , we hold in one hand, and with the other hand, we trace back from the end: , until we either hit some , in which case we set , or we end up at , in which case we set
Assume this happens at J i. e. is the last Then the loop erasure of , denoted by is a simple path of length J defined by
Now let G be some graph, let v be a vertex of G, and let R be a random walk on G starting from v. Let T be some stopping time for R. Then the loop erased random walk until time T is LE(R([1,T])). In other words, take R from its beginning until T — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path. The stopping time T may be fixed, i. e. one may perform n steps and then loop erase. However, it is usually more natural to take T to be the hitting time in some set. For example, let G be the graph Z2 and let R be a random walk starting from the point (0,0). Let T be the time when R first hits the circle of radius 100 (we mean here of course a discretized circle). LE(R) is called the loop erased random walk starting at (0,0) and stopped at the circle.
мұнда "max" жолдың ұзындығына дейін дегенді білдіреді. Индукция тоқтатылады, егер бізде болса. Бір қолымызбен ұстап, екінші қолымызбен соңынан кері қарай іздейміз: , біз кездескенше, онда біз белгілейміз , немесе біз бастапқы нүктеге жетеміз , онда біз белгілейміз. Егер бұл J нүктесінде болса, яғни J – соңғы нүкте болса, онда жолдың циклдерді өшіруі, деп белгіленеді, J ұзындығы бар қарапайым жолмен анықталады.
where "max" here means up to the length of the path The induction stops when for some we have
In words, to find , we hold in one hand, and with the other hand, we trace back from the end: , until we either hit some , in which case we set , or we end up at , in which case we set
Assume this happens at J i. e. is the last Then the loop erasure of , denoted by is a simple path of length J defined by
Now let G be some graph, let v be a vertex of G, and let R be a random walk on G starting from v. Let T be some stopping time for R. Then the loop erased random walk until time T is LE(R([1,T])). In other words, take R from its beginning until T — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path. The stopping time T may be fixed, i. e. one may perform n steps and then loop erase. However, it is usually more natural to take T to be the hitting time in some set. For example, let G be the graph Z2 and let R be a random walk starting from the point (0,0). Let T be the time when R first hits the circle of radius 100 (we mean here of course a discretized circle). LE(R) is called the loop erased random walk starting at (0,0) and stopped at the circle.
Енді G – кез келген граф болсын, v – G төбесі болсын, ал R – v нүктесінен басталатын G-дегі кездейсоқ жүріс болсын. T – R үшін тоқтату уақыты болсын. Онда T уақытына дейінгі циклдерді өшірілген кездейсоқ жүріс LE(R([1,T])) болады. Яғни, R-ді бастауынан T-ға дейін алыңыз – бұл (кездейсоқ) жол, жоғарыда көрсетілгендей барлық циклдарды хронологиялық тәртіппен өшіріңіз – сіз кездейсоқ қарапайым жол аласыз. Тоқтату уақыты T белгілі болуы мүмкін, яғни n қадам жасап, содан кейін циклдерді өшіруді орындауға болады. Дегенмен, көбінесе T-ні кейбір жиынға жететін уақыт деп қабылдау табиғирақ. Мысалы, G – Z2 графигі болсын және R – (0,0) нүктесінен басталатын кездейсоқ жүріс болсын. T – R радиусы 100 болатын шеңберге алғаш рет жететін уақыт болсын (әрине, біз дискретті шеңберді айтамыз). LE(R) – (0,0) нүктесінен басталып, шеңберде тоқтатылған, циклдері өшірілген кездейсоқ жүріс.
where "max" here means up to the length of the path The induction stops when for some we have
In words, to find , we hold in one hand, and with the other hand, we trace back from the end: , until we either hit some , in which case we set , or we end up at , in which case we set
Assume this happens at J i. e. is the last Then the loop erasure of , denoted by is a simple path of length J defined by
Now let G be some graph, let v be a vertex of G, and let R be a random walk on G starting from v. Let T be some stopping time for R. Then the loop erased random walk until time T is LE(R([1,T])). In other words, take R from its beginning until T — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path. The stopping time T may be fixed, i. e. one may perform n steps and then loop erase. However, it is usually more natural to take T to be the hitting time in some set. For example, let G be the graph Z2 and let R be a random walk starting from the point (0,0). Let T be the time when R first hits the circle of radius 100 (we mean here of course a discretized circle). LE(R) is called the loop erased random walk starting at (0,0) and stopped at the circle.
Біркелкі шапшаң ағашы
Кез келген G графигі үшін, G-нің ену ағашы – G-нің барлық төбелерін және кейбір қабырғаларын қамтитын, ағаш болып табылатын (яғни, байланысты және циклдары жоқ) субграфигі. Мүмкін болатын барлық ену ағаштарының арасынан тең ықтималдықпен кездейсоқ таңдалған ену ағашы біркелкі ену ағашы деп аталады. Әдетте, ену ағаштарының саны экспоненциалды түрде көп (олардың бәрін жасап, содан кейін кездейсоқ біреуін таңдау тым қиын); оның орнына, біркелкі ену ағаштары циклді жоятын кездейсоқ саяхаттарды қолданатын Вильсон алгоритмі деп аталатын алгоритм арқылы тиімдірек құрылуы мүмкін. Алгоритм келесі қадамдар бойынша жүзеге асырылады. Біріншіден, кез келген бір төбе таңдалып, жалғыз төбелі T ағашы құрастырылады. Содан кейін, егер құрылған T ағашы графтың барлық төбелерін қамтымаса, T-де жоқ кез келген v төбесі алынып, v-ден T ағашындағы төбеге жететінше циклді жоятын кездейсоқ саяхат жасалады және алынған жол T ағашына қосылады. Барлық төбелер енгізілгенге дейін осы процесті қайталау, әр қадамда төбелерді кездейсоқ таңдауға қарамастан, біркелкі таратылған ағаш береді. Кері байланыс та дұрыс. Егер v және w G графигіндегі екі төбе болса, кез келген ену ағашында олар бірегей жолмен байланысқан болады. Бұл жолды біркелкі ену ағашында қолдану кездейсоқ қарапайым жол береді. Бұл жолдың таралуы v төбесінен басталып, w төбесінде тоқтатылған циклді жоятын кездейсоқ саяхаттың таралуымен сәйкес екені анықталды. Бұл факт Вильсон алгоритмінің дұрыстығын негіздеу үшін пайдаланылуы мүмкін. Тағы бір салдар – циклді жоятын кездейсоқ саяхат басталу және аяқталу нүктелерінде симметриялы. Нақтырақ айтқанда, v төбесінен басталып, w төбесінде тоқтатылған циклді жоятын кездейсоқ саяхаттың таралуы w төбесінен басталып, v төбесінде тоқтатылған циклді жоятын кездейсоқ саяхаттың кері таралуымен бірдей. Циклді жоятын кездейсоқ саяхатты және кері саяхатты жою, әдетте, бірдей нәтиже бермейді, бірақ осы нәтижеге сәйкес екі циклді жоятын саяхаттың таралуы бірдей.
Торлар
d өлшемді болсын, оны кем дегенде 2 деп есептейміз. Zd-ні қарастырайық, яғни бүтін санды координаталары бар барлық нүктелерді. Бұл әрбір нүктенің ең жақын көршілеріне қосылған кезде 2d дәрежесіне ие шексіз граф. Енді осы графтың немесе оның ішкі графтарының циклдарды жоятын кездейсоқ жүрісін қарастырамыз.
Жоғары өлшемдер
Талдау үшін ең оңай жағдай – 5 және одан жоғары өлшем. Бұл жағдайда қиылыстар тек жергілікті болып шығады. Есептеу көрсеткендей, егер n ұзындығындағы кездейсоқ жүріс алса, оның циклді жою ұзындығы сол шамаға ие, яғни n. Сәйкес масштабтау бойынша, циклді жою кездейсоқ жүріс (тиісті мағынада) n шексізге ұмтылғанда Браун қозғалысына жақындайды. 4-өлшем күрделірек, бірақ жалпы картина бұрынғыдай сақталады. n ұзындығындағы кездейсоқ жүрістің циклді жою шамамен нүктелерге ие екендігі анықталды, бірақ қайта масштабтағаннан кейін (лог. факторды ескере отырып) циклді жою жүрісі Браун қозғалысына жақындайды.
Екі өлшемді
Екі өлшемде конформдық өріс теориясы және модельдеу нәтижелері бірқатар қызықты болжамдарға әкелді. D жазықтықтағы жай ғана байланысқан домен болсын, ал x – D доменіндегі нүкте. G графигін D-ге шектелген, қабырғасы ε болатын тор ретінде қарастырайық. v – G графигінде x нүктесіне ең жақын төбе болсын. Енді v төбесінен басталатын және G графигінің "шекарасына" жеткенде тоқтатылатын цикл өшірілген кездейсоқ жүрісті қарастырайық, яғни D шекарасына сәйкес келетін G графигінің төбелерін. Онда болжамдар мынадай: ε нөлге жақындағанда, жүріс үлестірілімі x-тен D шекарасына дейінгі жай жолдардың белгілі бір үлестіріліміне айналады (әрине, Браун қозғалысынан өзгеше – 2 өлшемде Браун қозғалысының жолдары жай емес). Бұл үлестіруді (оны арқылы белгілейміз) цикл өшірілген кездейсоқ жүрістің масштабтау шегі деп атайды. Бұл үлестірулер конформдық инвариантты болып табылады. Атап айтқанда, егер φ – D және екінші домен E арасындағы Риман бейнелеуі болса, онда осы жолдардың Хаусдорф өлшемі дерлік барлық жағдайларда 5/4-ке тең. Бұл болжамдарға алғашқы тырысқан шабуыл домино плиткалары бағытынан келді. G графигінің жайған ағашын алып, оған оның жазықтықтағы қос ағашын қоссақ, арнайы туынды графтың домино плиткасын аламыз (оны H деп атайық). H графигінің әрбір төбесі G графигінің төбесіне, қабырғасына немесе жағына сәйкес келеді, ал H графигінің қабырғалары қай төбе қай қабырғада және қай қабырға қай жақта жатқанын көрсетеді. G графигінің біркелкі жайған ағашын алу H графигінің біркелкі үлестірілген кездейсоқ домино плиткасына әкеледі. Графтың домино плиткаларының санын есептеу үшін арнайы матрицалардың анықтамасын пайдалануға болады, бұл оны конформдық инвариантқа жуық дискретті Грин функциясымен байланыстыруға мүмкіндік береді. Бұл аргументтер цикл өшірілген кездейсоқ жүрістің белгілі бір өлшенетін шамаларының (шекте) конформдық инвариантты екенін, ал радиусы r шеңберінде тоқтатылған цикл өшірілген кездейсоқ жүрістегі төбелердің күтілетін санының реті шамамен көрсетуге мүмкіндік берді. 2002 жылы бұл болжамдар (оң пішімде) шешілді. Бұл, өте жуықтап айтқанда, цикл өшірілген кездейсоқ жүрістің (және көптеген басқа да ықтималдық процестердің) Марков қасиетін ұстауға мүмкіндік беретін, конформдық инвариантты қарапайым дифференциалдық теңдеу болып табылады.
that is, a grid of side length ε restricted to D. Let v be the vertex of G closest to x. Examine now a loop erased random walk starting from v and stopped when hitting the "boundary" of G, i. e. the vertices of G which correspond to the boundary of D. Then the conjectures are
As ε goes to zero the distribution of the path converges to some distribution on simple paths from x to the boundary of D (different from Brownian motion, of course — in 2 dimensions paths of Brownian motion are not simple). This distribution (denote it by ) is called the scaling limit of loop erased random walk. These distributions are conformally invariant. Namely, if φ is a Riemann map between D and a second domain E then
The Hausdorff dimension of these paths is 5/4 almost surely. The first attack at these conjectures came from the direction of domino tilings. Taking a spanning tree of G and adding to it its planar dual one gets a domino tiling of a special derived graph (call it H). Each vertex of H corresponds to a vertex, edge or face of G, and the edges of H show which vertex lies on which edge and which edge on which face. It turns out that taking a uniform spanning tree of G leads to a uniformly distributed random domino tiling of H. The number of domino tilings of a graph can be calculated using the determinant of special matrices, which allow to connect it to the discrete Green function which is approximately conformally invariant. These arguments allowed to show that certain measurables of loop erased random walk are (in the limit) conformally invariant, and that the expected number of vertices in a loop erased random walk stopped at a circle of radius r is of the order of
In 2002 these conjectures were resolved (positively) using Stochastic Löwner Evolution. Very roughly, it is a stochastic conformally invariant ordinary differential equation which allows to catch the Markov property of loop erased random walk (and many other probabilistic processes).
Үш өлшемді
Масштабталу шегі бар және айналулар мен кеңейтулерге қатысты инвариантты. Егер r қашықтығына жеткенше циклді өшіретін кездейсоқ жүрістегі төбелердің күтілетін саны деп белгіленсе, онда
мұнда ε, c және C – оң сандар (принцип бойынша, сандар дәлелдемелерден есептелуі мүмкін, бірақ автор оны есептемеген). Бұл масштабталу шегінің Хаусдорф өлшемі дерлік нақтылықпен 2 және 5/3 аралығында болуы керек екенін көрсетеді. Сандық тәжірибелер оның болатынын көрсетеді.