Јануар 2024 (English ≽)

Stochastic

Питање: Шта значи реч „стохастички“?

Одговор: Стохастичка појава има насумичну поделу вероватноћа и или образац који се статистички да анализирати, али не прецизно предвидети.

Стохастички, случајни процес је колекција случајних варијабли индексирана одређеним скупом. Сваку од случајних променљих таквог процеса једнозначно вежу елементи тог и скупа индекса.

Статистичка вероватноћа је број P(ω) = M/N, тј. повољних исхода подељен бројем свих покушаја у понављању увек истог догађаја.

На пример, фер коцку бацам N = 100 пута (симулација) и добијем M = 15 „шестица“. То је статистичке вероватноће P = 15/100. Понављајући исту серију добио сам P = 17/100 и опет понављајући по трећи пут P = 11/100. Наредних седам пробавања исте, давале су ми статистичке вероватноће 26/100, 15/100, 18/100, 17/100, 13/100, 13/100 и 15/100. Теорија одреди услове када P → p, а пракса то без изузетка потврђује.

Математичка вероватноћа, или краће вероватноћа је број p ∈ [0, 1] око кога се групишу статистичке вероватноће. Другим речима, P → p, када број понављања (истог) опита неограничено расте. Бацањем фер коцке вероватноћа „шестице“ била би p = 1/6. Бацањем нефер коцке сваки од шест бројева имао би неке вероватноће p₁, ..., p₆ збира један. Сви такви исходи ω₁, ω₂, ..., од којих се тачно један догађа, чине дискретни скуп Ω који називамо простор догађаја, или простор узорака, чије вероватноће називамо расподела вероватноћа.

Постоје и расподеле непрекидних догађаја, ω ∈ Ω, густина вероватноћа ρ(ω) ≥ 0, чији је интеграл по скупу Ω један, ако би се тада догађао тачно један исход тог скупа. Занимљиве детаље о вероватноћама наћи ћете у мојој елементарној скрипти (Математика IV, 6. Вјероватноћа). Тамо се налази и следећи задатак са детаљнијим решењем (Примјер 6.2.10).

1. Пример. Њих двоје се договоре да се нађу између 1 и 2 часа и да се на уговореном месту сачекају 20 минута. Колика је вјероватноћа да ће доћи до сусрета?

Решење: На горњој слици лево, времена доласка њих двоје су x и y, у мин након почетка времена долазака. Укупни период долазака је 60 × 60 min, а за период састанка важи |x - y| ≤ 20 min, тј. x - 20 ≤ y ≤ x + 20. То су две праве које одвајају сенчени део површине 3600 - 40 × 40. Количник њих, сенченог дела и целог квадрата, је 2000/3600 = 0,56. То је тражена вероватноћа. □

Условна вероватноћа је вероватноћа исхода који се догађају под условима који ограничавају опције. Следећи пример је варијација бацања новчића.

2. Пример. Отац има двоје деце. Једно је женско. Колика је вероватноћа да је и друго дете женско?

Решење: Од четири {ЖЖ, ЖМ, МЖ, ММ} равноправне могућности само три имају „Ж“, а од њих само је једна и са другим „Ж“. Дакле, тражена је условна вероватноћа 1/3. □

Вероватоћа да ће се десити ω₁ када се зна да се десило ω₂ дефинише се са

P(ω₂|ω₁) = P(ω₂ω₁)/P(ω₁).

Отуда

P(ω₁)P(ω₂|ω₁) = P(ω₂)P(ω₁|ω₂).

У наведеном примеру, ω₁ је догађај „бар једно је Ж“, а ω₁ω₂ је „оба су Ж“, вероватноћа редом 3/4 и 1/4, па је P(ω₂|ω₁) = (1/4)/(3/4) = 1/3.

Аналогно, код два бацања новчића имамо равноправна четири исхода {ПП, ПГ, ГП, ГГ}, што је лако проверити узастопним бацањем по два новчића много пута. Наиме, ако би ПГ и ГП био један исти исход, онда дати скуп има само три равноправна, па би рецимо ПП (писмо-писмо) било у око трећине свих бацања. Али, оно се дешава у око четвртине таквих опита.

Информација је попут мајстора заплета у комбинаторним примерима. Када имамо n = 1, 2, 3, ... позиција за цифре базе b = 2, 3, 4, ... система писања бројева, онда њима можемо написати N = bⁿ разних вредности. Са две позиције (n = 2) у бинарном систему (b = 2) могуће је написати укупно N = 2² = 4 различита броја. На три позиције (n = 2) смештамо укупно N = 2³ = 8 бројева. Да би се дешавала једна од N равноправних могућности, вероватноћа је p = 1/N, а информација I = log₂ N = -log₂ p бита. О логаритму сам и овде посебно писао.

Conditional

Питање: Појасните ми ту „условну вероватноћу“?

Одговор: Условна вероватноћа за догађај A у односу на догађај B је вероватноћа да се може десити A ако је испуњен догађај B. Ово се пише P(A|B) и вреди

\[ P(A|B) = \frac{P(A\cap B)}{P(B)}. \]

Иначе, пресек скупова (A ∩ B) се може писати као производ (AB), унија (A ∪ B) као збир (A + B), а вероватноћу (енг. Probability) у наставку означавамо са Pr.

1. На слици десно је бубањ (Ω) са четири врсте куглица A, B₁, B₂ и B₃. Све од 30 куглица A беле су, као и свих 10 куглица B₁ и 12 од куглица B₂, док су 4 од B₂ црне. Црне су и свих 10 куглица B₃, или преосталих 34 куглице, рецимо врста C. Свака од куглица има једнаке шансе да буде извучена из бубња. Вероватноћа да извучена куглица буде бела, односно црна је:

Pr(бела) = Pr(A) + Pr(B₁) + Pr(B₂|бела) = 0,30 + 0,10 + 0,12 = 0,52
Pr(црна) = Pr(B₃|црна) + Pr(B₃) + Pr(C) = 0,04 + 0,10 + 0,34 = 0,48

Бити бела или црна куглица овог бубња дисјунктни (немају заједничких) су догађаји и чине потпун скуп (простор узорака, Ω), тако да је

Pr(бела + црна) = Pr(бела) + Pr(црна) = 1.

На истој слици налазимо и следеће условне вероватноће:

Pr(A|B₁) = 1,   Pr(A|B₂) = 0,12/(0,12 + 0,04) = 0,75,   Pr(A|B₃) = 0.

Начин да разумете условну вероватноћу је, поред наведених линкова, да пажљиво анализирате примере које наводим. Приметимо како из B ⊆ A следи A ∪ B = A и A ∩ B = B.

2. Нека су B₁, B₂, ..., B_n дисјунктни скупови (без заједничких елемената), па имамо:

1. A = B₁ + B₂ + ... + B_n ,
2. Pr(A) = Pr(B₁)Pr(A|B₁) + Pr(B₂)Pr(A|B₂) + ... + Pr(B_n)Pr(A|B_n),
3. Pr(B_k|A) = Pr(B_k)Pr(A|B_k)/Pr(A),   k = 1, 2, ..., n.

Тада (a) скупове B_k називамо разбијањем скупа A, следеће (b) је формула потпуне вероватноће, трећи израз (c) је Бајесова формула. Ево неколико типичних примера са овим изразима.

3. Пример. Изложено је n = 2, 3, 4, ... узорака за преглед. Међу којима је m = 0, 1, ..., n неисправних. Насумице се бирају два без враћања. Ако су B₁ и B₂ догађаји да је први и други бирани производ неисправан, наћи овим вероватноће и вероватноћу B₂, под условом да се десило B₁. Израчунати те бројеве за n = 10 и m = 4.

Решење: Јасно је Pr(B₁) = Pr(B₂) = m/n, јер избор без враћања неће мењати вероватноћу неисправног производа. Наиме, први ће бити неисправан B₁ или исправан B'₁, па је вероватноћа бирања другог неисправног:

\[ \Pr(B_2) = \Pr(B'_1)\Pr(B_2|B'_1) + \Pr(B_1)\Pr(B_2|B_1) = \] \[ = \frac{n-m}{n}\frac{m}{n-1} + \frac{m}{n}\frac{m-1}{n-1} = \frac{m(n-1)}{n(n-1)} = \frac{m}{n}. \]

Бројеви исхода датих догађаја су |B₁B₂| = m(m - 1) и |B₁| = m(n - 1), па је:

\[ \Pr(B_2 | B_1) = \frac{|B_1 B_2|}{|B_1|} = \frac{m(m - 1)}{m(n - 1)} = \frac{m - 1}{n - 1} \ne \Pr(B_1). \]

За n = 10 и m = 4, биће Pr(B₁) = Pr(B₂) = 4/10 и Pr(B₂|B₁) = 1/3. □

4. Пример. Кутија са равноправним куглицама има две преграде, тако да има три коморе A, B и C. По четвртина куглица је у првој и трећој од комора, а остале су у другој. Зна се да је 20% куглица прве коморе бело а остале црно, да је 30% куглица друге коморе бело а остале црно, те да је 40% одсто куглица треће коморе бело а остале су црне. Колика је шанса да ће насумице извучена куглица бити бела (X), бити црна (Y)?

Решење: Према формули потпуне вероватноће (2.b) налазимо:

Pr(X) = Pr(A)Pr(X|A) + Pr(B)Pr(X|B) + Pr(C)Pr(X|C) =
= 0,25⋅0,20 + 0,50⋅0,30 + 0,25⋅0,40 = 0,30

Pr(Y) = Pr(A)Pr(Y|A) + Pr(B)Pr(Y|B) + Pr(C)Pr(Y|C) =
= 0,25⋅0,80 + 0,50⋅0,70 + 0,25⋅0,60 = 0,70

Шанса је 3 : 7 да ће извучена куглица бити бела а не црна. □

5. Пример. Када се обрне питање у претходном, 4. примеру, добије се задатак типичан за решавање Бајесовом формулом. Рецимо, када је из кутије насумице извучена бела (X) куглица, колика је вероватноћа да је она била у првој (A), другој (B) и трећој (C) комори?

Одговор: Према формули (2.c) Бајеса налазимо:

Pr(A|X) = Pr(A)Pr(X|A)/Pr(X) = 0,25⋅0,20/0,30 = 1/6

Pr(B|X) = Pr(B)Pr(X|B)/Pr(X) = 0,50⋅0,30/0,30 = 1/2

Pr(C|X) = Pr(C)Pr(X|C)/Pr(X) = 0,25⋅0,40/0,30 = 1/3

Збир ове три је 1, јер је куглица сигурно из једне од три коморе. □

Без падања и понављања нема напредовања (без неизвесности нема ни виталности), држите се тога читајући ове примере, а ако сте их разумели — то је сјајно, па идемо даље. Нису баш сви задаци условних вероватноћа интуитивно лако разумљиви. То можете осетити већ код 2. примера, а ево једног још јачег.

6. Пример (Монти Хол). Претоставимо да сте у игри, и дат Вам је избор троје врата: Иза једних врата је ауто; иза других, козе. Ви бирате врата, рецимо бр.1 , а домаћин, који зна шта је иза врата, отвара друга врата, рецимо бр.3; иза којих је коза. Онда Вам он каже: „Да ли желите да одаберете врата Бр. 2?“ Да ли је на вашу корист да промените избор?

Објашњење: Такмичар у првом покушају бира врата која откривају козу, не ауто, да домаћин отвори врата која није бирао такмичар и она, такође, откривају козу. Затим, домаћин нуди могућност да такмичар бира између првобитно одабраних врата и других затворених врата.

У првом покушају, шанса добитка A је 1 : 3, у другом је 1 : 2. Неизвесност првог покушаја се смањила, делом потрошена првим избором који није био погодак. Промашај A' у првом и другом бирању има вероватноће 2/3 и 1/2, из чега је јасно да такмичар треба поново одабирати врата. □

Одговор звучи парадоксално, а паметном и поучно, јер интуиција може грешити код сложенијих математичких проблема. Зато израз „очигледно је“ математичари сматрају једним од најклизавијих, док тврђења многих теорема испадају тако неинтуитивна. Било како било, током миленијума (близу три хиљаде година) немамо ни трага о нетачности математичких исказа (физика, па остале природне науке постоје мање од четири века) иако их непрестано преиспитујемо.

Сличан пример са претходном (1975) био је парадокс „Три затвореника“ (1959). Још старији био би формулисан за средњошколску математику о условним вероватноћама, на следећи начин. У првом и другом покушају, добитак је A₁ и A₂, а губитак је A'₁ и A'₂. Стога:

\[ \begin{matrix} \Pr(A_1) = \frac13 & \Pr(A_2|A'_1) = \frac12 \\ \Pr(A'_1) = \frac23 & \Pr(A'_2|A'_1) = \frac12 \end{matrix} \]

У првом бира се једна од три могућности, затим у другом једна од две. У симулацији, када се искључи бирање у другом кораку добијаће се мање погодака, него са поновним бирањем у другом кораку, тада једне од две опције.

Данас би то на компјутерима свакоме било лако проверавати, а рађено је и тада пре пола века са истим резултатом. Међутим, ово тачно решење је својевремено оспоравано и од велике већине гледалаца и забрињавајуће већине „познаваоца“ теорије вероватноће. То наводим само као пример непоузданости чисте интуиције у математици.

Diagnosis

Питање: Можете ли ми послати модул „Процена“?

Одговор: Ни случајно! Те делове „Терминатора“ (пакет програма) због непобедивости у такмичењу против данас знаних стратегија, не дајем никоме. Али, могу вам објаснити један такође успешан алгоритам.

Узгред, добар савет био би вам да вешачку интелигенцију снабдете разним решењима (скоро) истих задатака, са много њих, тако и са приступом великим живим базама података. Прво ради случаја без којег нема креативности, а ово друго ради „машинског учења“. Метода коју ћу вам описати није тачно оно што сте ми тражили, али видећете, уз нешто знања математике, добићете и више од очекиваног.

Дакле, замишљамо да радимо у некој великој болници, или имамо њене податке, са огромним индексираним списком симптома B₁, B₂, ..., B_m са такође уређеним огромним списком болестију A₁, A₂, ..., A_n. Додато томе имамо процене условних вероватноћа Pr(A_i|B_j) = p_ij које се могу (али не морају) стално ажурирати као програму вањска база података.

Идеја је да имамо списак свих могућих m ∈ ℕ симптома и сваких могућих n ∈ ℕ болестију са тим симптомима, али захваљујући Борељ-Кантелијевој леми то и није неопходно. У случају великих спискова могућности, само мали део њих биваће релевантан (зависно од потребе).

Тако, када имамо пацијента са невеликим списком симптома нанизаних у вектор x = (x₁, x₂, ..., x_m), све остале допуњавамо нулама. Те бројеве (x_j) скалирајте да буду сразмерни јачини симптома код појединог пацијента. Формирамо матричну једначину y = Mx, односно

\[ \begin{pmatrix} y_1 \\ y_2 \\ ... \\ y_n \end{pmatrix} = \begin{pmatrix} p_{11} & p_{12} & ... & p_{1m} \\ p_{21} & p_{22} & ... & p_{2m} \\ ... & ... & ... & ... \\ p_{n1} & p_{n2} & ... & p_{nm} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ ... \\ x_m \end{pmatrix} \]

систем линеарних једначина са којим компјутери лако излазе на крај чак и у случају веома дугих низова. Модул треба правити тако да се бројеви m и n могу мењати у бази података, да се база може ажурирати без промена на самом модулу.

За сваку j-ту колону ове матрице важи:

p_1j + p_2j + ... + p_nj = Pr(A₁|B_j) + Pr(A₂|B_j) + ... + Pr(A_n|B_j) = 1,

када имамо пописане (скоро) све болести (A_i) за све врсте симптома (B_j). Свака од колона медицинске матрице M је (приближно) нека расподела вероватноћа, ако је она (приближно) комплетна.

Излазни вектор, низ y = (y₁, y₂, ..., y_n), потом се сортира у низ опадајућих вредности z = (z₁, z₂, ..., z_n) међу којима су први чланови најбоље процене болести које би пацијент могао имати на основу улазних симптома (x) и медицинских знања (M) дате установе. Све даље је чиста алгебра.

Приметимо да овај програм за дијагнозе болестију лако (променама база података) можемо преусмерити у метеоролошке прогнозе, или у процене позиција игара на победу, уопште у много тога — једнако као што и рачун налази своје примене свукуда. Моћ је математике та, што велика тачност води у невероватно велику употребљивост. А то би било и најдаље место које вам желим откривати на горње ми питање.

Chain

Питање: Та „медицинска“ матрица није била квадратна?

Одговор: Не, та матрица (M) није квадратна, ако број симптома (m) није једнак броју болестију (n). Када су њени бројеви редака и колона једнаки (m = n), а збир коефицијената сваке колоне један, она је „стохастичка“.

1. Стохастичка матрица је квадратна матрица сачињена од колона неких вектора расподела вероватноћа. Коефицијенти ових вектора вероватноћа су реални бројеви између 0 и 1 збира 1, а стохастичка матрица копира те у векторе истог типа, коефицијената реалних бројева из [0, 1] збира један.

Заиста, ако је A = (a_ij) стохастичка матрица реда n, тада је

a_1j + a_2j + ... + a_nj = 1,

у свакој колони j = 1, 2, ..., n, па ако имамо x = (x₁, x₂, ..., x_n), такође вектор вероватноће, онда је у вектору y = Ax коефицијент i-тог ретка:

y_i = a_i1x₁ + a_i2x₂ + ... + a_inx_n

за свако i = 1, 2, ..., n. То су ненегативни бројеви збира:

\[ \sum_{i=1}^n y_i = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_j = \sum_{j=1}^n\left(\sum_{i=1}^n a_{ij}\right)x_j = \sum_{j=1}^n x_j = 1, \]

па је и y вектор неке расподеле вероватноће.

7. Пример. Матрица једначином y = Ax

\[ \begin{pmatrix} 0,62 \\ 0,30 \\ 0,08 \end{pmatrix} = \begin{pmatrix} 0,8 & 0,2 & 0,2 \\ 0,2 & 0,7 & 0,2 \\ 0,0 & 0,1 & 0,6 \end{pmatrix} \begin{pmatrix} 0,70 \\ 0,20 \\ 0,10 \end{pmatrix} \]

преводи вектор расподеле x у вектор расподеле y, што је лако проверити непосредним множењем и сабирањем датих бројева. □

2. Важна особина квадратних матрица истог реда је да се могу међусобно множити. Да ће производи стохастичих матрица A и B истог реда (n) опет бити стохастичке матрице (C = AB) видимо из претходног. Свака колона друге матрице (B) је неки вектор вероватноће, као x, који множен првом (A) постаје такође вектор вероватноће, попут y, па су и колоне резултата множења неки вектори вероватноћа, тј. C је стохастичка матрица.

Детаљније исто видимо множењем општих бројева:

\[ \sum_{i=1}^n c_{ik} = \sum_{i=1}^n \sum_{j=1}^n a_{ij}b_{jk} = \sum_{j=1}^n \left(\sum_{i=1}^n a_{ij}\right) b_{jk} = \sum_{j=1}^n b_{jk} = 1, \]

што је тачно за свако k = 1, 2, ..., n, па је и матрица C = (c_ik) стохастичка.

8. Пример. Матрично множење C = AB стохастичких матрица

\[ \begin{pmatrix} 0,50 & 0,32 & 0,26 \\ 0,35 & 0,50 & 0,30 \\ 0,15 & 0,18 & 0,44 \end{pmatrix} = \begin{pmatrix} 0,8 & 0,2 & 0,2 \\ 0,2 & 0,7 & 0,2 \\ 0,0 & 0,1 & 0,6 \end{pmatrix} \begin{pmatrix} 0,5 & 0,2 & 0,1 \\ 0,3 & 0,6 & 0,2 \\ 0,2 & 0,2 & 0,7 \end{pmatrix} \]

даје стохастичку матрицу. Проверите то непосредним израчунавањем. □

3. Зато постоји композиција x' = Ax, x'' = Ax', x''' = Ax'', ..., x^(r+1) = Ax^(r), ... пресликавања стохастичким матрицама. Ово x^(r) = A^rx. Тако низ матрица A, A², ..., A^r, ... постаје Марковљев ланац. Тај „ланац“ је процес генерисан стохастичком матрицом A. Он вектор расподеле вероватноћа (x) корак по корак пресликава у низ x', x'', x''', ... вектора расподела вероватноћа.

9. Пример. Низ A, A², A³, ... стохастичких матрица:

\[ \begin{pmatrix} 0,8 & 0,2 & 0,2 \\ 0,2 & 0,7 & 0,2 \\ 0,0 & 0,1 & 0,6 \end{pmatrix}, \begin{pmatrix} 0,68 & 0,32 & 0,32 \\ 0,30 & 0,55 & 0,30 \\ 0,02 & 0,13 & 0,38 \end{pmatrix}, \begin{pmatrix} 0,608 & 0,392 & 0,392 \\ 0,350 & 0,475 & 0,350 \\ 0,042 & 0,133 & 0,258 \end{pmatrix}, ... \]

је ланац Маркова генерисан матрицом A. Он корак по корак формира низ вектора x, x', x'', x''', ...:

\[ \begin{pmatrix} 0,7 \\ 0,2 \\ 0,1 \end{pmatrix}, \ \begin{pmatrix} 0,62 \\ 0,30 \\ 0,08 \end{pmatrix}, \ \begin{pmatrix} 0,572 \\ 0,350 \\ 0,078 \end{pmatrix}, \ \begin{pmatrix} 0,5432 \\ 0,3750 \\ 0,0818 \end{pmatrix}, \ ... \]

који су неке расподеле вероватноћа. □

Приметимо да се распон коефицијената пресликаног вектора смањује, а постоје и једноставна општа правила када се то догађа.

Narrowing

Питање: Када се распон коефицијената вектора вероватноће смањује и које су последице?

Одговор: Нека су:

m_i = min {a_i1, a_i2, ..., a_in}
M_i = max {a_i1, a_i2, ..., a_in}

минимуми и максимуми i-тог ретка редом свих i = 1, 2, ..., n, стохастичке матрице A = (a_ij).

Тада је свако m_i ≤ y_i ≤ M_i вектора расподеле y = Ax који је слика вектора расподеле x. Наиме:

y_i = a_i1x₁ + ... + a_inx_n,   међутим   m_i ≤ a_i1x₁ + ... + a_inx_n ≤ M_i,

јер је x₁ + ... + x_n = 1.

У претходном, 9. пример, m₁ = 0,2 и M₁ = 8,0 тако да водећи коефицијент 0,7 вектора x прелази у 0,62 овај у 0,572 затим у 0,5432 и тако даље, он се смањује, јер је већи од 0,5 и превелик је. Међутим x₂ = 0,2 је мањи од 0,5 и премален је, па расте: 0,2 → 0,30 → 0,350 → 0,375 → ..., а то је поступак тада уједначавања вероватноћа и повећања информације (Екстреми).

Последицу овог сужавања распона вероватноћа расподеле x → x' → x'' ... и промене (повећања) њене информације видимо као сметњу, шум канала. Ако она настаје додавањем информације, због дезинформација повећава се неизвесност улазне поруке.

Меру „шума канала“, коју теорија информације посебно не одређује, овде можемо дефинисати интензитетом повећавања поменутог сужавања што су вероватноће, па на пример формулом (Ну):

Ν = -∑_i (M_i - m_i)⋅log (M_i - m_i) = -(M₁ - m₁)⋅log (M₁ - m₁) -
(M₂ - m₂)⋅log (M₂ - m₂) - ... - (M_n - m_n)⋅log (M_n - m_n).

Формула подсећа на Шенонову информацију, али она није таква средња вредност, јер разлике (M_i - m_i) које јесу вероватноће, не чине расподелу вероватноће. Управо зато она је добро дефинисана сметња, јер све већа разлика вероватноћа Δp од 1/e ≈ 0,37, као и све мања од истог, чини све мањим сабирак -Δp⋅log Δp.

На пример, претходна матрица (A) има „шум канала“

Ν = -0,6⋅log₂ 0,6 - 0,5⋅log₂ 0,5 - 0,6⋅log₂ 0,6 ≈ 1,38 bit.

Други пример, стохастичка матрица (Трансформације) дефинисана са

\[ C = \begin{pmatrix} \alpha & \alpha & \alpha \\ \beta & \beta & \beta \\ \gamma & \gamma & \gamma \end{pmatrix} \]

нема „шум канала“, јер -Δp⋅log Δp → 0, када Δp → 0. То је доследно, јер је C² = C, односно ова матрица се не мења степеновањем. Али, она ће сваки вектор вероватноће x = (x₁, x₂, x₃) трансформисати у вектор x' = (α, β, γ). Према томе, требамо „шум канала“ и „шум поруке“ разликовати.

Трећи пример, јединична матрица

\[ I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \]

има ове разлике вероватноћа Δp_i = M_i - m_i = 1 - 0 = 1, а јер су сви сабирци „шума канала“ -1⋅log 1 = -1⋅0 = 0, он изостаје. Свака матрица која се добија пермутацијама колона јединичне је стохастичка матрица и такође нема шум.

Ту је и резиме одговора на постављено ми питање, распон коефицијената вектора вероватноће смањује се са бројем Ν, овде одређен „шум канала“, а тачније речено „сужавање“ (енг. Narrowing) канала.

Black Box II

Питање: Није ли је поменута матрица C „црна кутија“?

Одговор: Да, C је једна је од њих (Black Box). Када је „сужавање“ канала Ν = 0, онда је канал или црна кутија (попут C), или нема губитака (попут I) док спроводи расподеле вероватноћа.

У свим осталим случајевима, када је Ν > 0, композиција A^r, када експонент r неограничено расте, конвергира црној кутији. Наиме, када је Ν > 0, онда постоји бар један редак стохастичке матрице A = (a_ij), рецимо i-ти, чија разлика максимума и минимума условних вероватноћа није нула.

10. Став. Разлике Δp_i = M_i - m_i > 0, истог ретка, постају строго опадајући низ композиције A^r, када r расте.

Доказ: Математичком индукцијом. У случају r = 2, код матрице A² имамо коефицијенте a'_ik за које важи:

\[ a'_{ik} = \sum_{j=1}^n a_{ij}a_{jk} \lt M_i \sum_{j=1}^n a_{jk} = M_i \]

јер је по претпоставци бар један члан a_ij и мањи од највећег, а збир свих k-те колоне је 1. Аналогно a'_ik > m_i. Отуда

0 < M'_i - m'_i < M_i - m_i

што значи да се разлика највећег и најмањег коефицијента i-тог ретка матрице смањује.

У другом кораку индукције, претпоставимо да су a'_ik коефицијенти i-тог ретка матрице A^r и да су M'_i и m'_i различити највећи и најмањи елементи њеног i-тог ретка. Тада за матрицу A^rA је:

\[ a''_{ik} = \sum_{j=1}^n a'_{ij}a_{jk} \lt M'_i \sum_{j=1}^n a_{jk} = M'_i \]

на исти начин објашњени као у претхоном, и исто аналогно a'_ik > m'_i, што повлачи

0 < M''_i - m''_i < M'_i - m'_i

чиме је доказ индукцијом завршен. Разлика највећег и најмањег од свих коефицијента истог i-тог ретка матрице A^r смањује се када r = 1, 2, 3, ... расте. ∎

Како је низ ових разлика Δp_i = M_i - m_i > 0 ограничен са доње стране али и строго опадајући, он конвергира некој тачки нагомилавања. Међутим, та не може бити ништа осим нуле, јер би опет имали корак попут претходне индукције, све до нуле.

Према томе, гранична вредност сваког члана i-тог ретка матрице A^r, када r → ∞, нека је константа α (алфа). Редак тада личи на низове константи редака горе поменуте матрице C. Међутим, ако је 0 < α < 1, онда свака колона има још неке ненулте елементе (до збира 1), па има још понеку разлику ретка Δp > 0 која ће конвергирати до нуле, или има све остале ретке неке константе β, γ, ... (попут матрице C) збира α + β + γ + ... = 1. Тиме смо доказали и следеће тврђење.

11. Став. када је Ν > 0, композиција A^r, када експонент r неограничено расте, конвергира црној кутији.

Иначе, црна кутија о којој говоримо, попут матрице C (Трансформације) је стохастичка матрица која сваки вектор расподеле вероватноће копира у један те исти вектор, тако да на основу излаза (копије) не можемо знати шта је био улаз (оригинал).

Message Noise

Питање: Имате ли још нешто о „шуму канала“?

Одговор: Наравно, изненадио би се колико тога има. Али хајдемо и прво размотримо ону разлику „шума поруке“ од „шума канала“, поменуту недавно (Narrowing).

1. Посматрајмо оригинале потом копије, вектора горњих ознака:

x = (x₁, ..., x_n),     x' = (x'₁, ..., x'_n),     x' = Ax,

Израчунајмо разлике (Δx_k = x'_k - x_k) копије и оригинала, вектор:

Δx = x' - x = (A - I)x,

\[ \Delta x = \begin{pmatrix} a_{11} - 1 & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} - 1 & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn} - 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{pmatrix}. \]

Када је овај нула-вектор (Δx = 0), тада преносник (A) нема шум, бар што се тиче дате поруке (x). Ово је сигурно постигнуто, када је детерминанта det(A - I) = 0. Овако постављен проблем „шума поруке“ постаје проблем карактеристичних вредности (eigenvalues) матрице са њима припадним карактеристичним векторима (eigenvectors).

12. Пример. Матрица (A) 7. примера, има карактеристичне (својствене) вредности λ и њима припадне (Ax = λx) карактеристичне, или својствене векторе:

λ₁ = 1     x₁ = (5, 4, 1),
λ₂ = 0,6     x₂ = (√2, 0, -√2),
λ₃ = 0,5     x₃ = ( 0, -√2, √2),

тако да је Ax_k = λ_kx_k. □

Пример указује на главну препреку стохастичких матрица у применама теорема линеарне алгебре. Вектори на које ове матрице примењујемо су расподеле вероватноћа, а такви су само део векторског простора. Ствар је слична решавању осталих алгебарских једначина, када можемо добијати решења која нису реална и кажемо да једначина „нема решења“.

Други је проблем са нормом. Векторски простори се могу нормирати са

\[ \|x\| = \left( \sum_{k=1}^n |\xi_k|^p\right)^{1/p} \]

где је вектор x = (ξ₁, ξ₂, ..., ξ_n), а 1 ≤ p < ∞. Када су коефицијенти ξ_k реални бројеви ову норму означавамо са ℝ_p, а ако су комплексни бројеви са ℂ_p. У случају да димензија векторског простора n → ∞ и збирови конвергирају, ознака норме је ℓ_p. Када вектор x поделимо његовом нормом ∥x∥ ≠ 0, оно што добијамо је јединични вектор, норме 1.

Својствени вектори (обично) су јединичне норме ∥x∥ = 1, на начин како се норма дефинише у датом векторском простору, односно како се она може дефинисати. Међутим, стандардно је норма вектора ℝ₂, еуклидска норма, или 2-норма, која је корен збира квадрата коефицијената вектора. У 12. примеру n = 3, а квадрати су коефицијената (±0,7071...)² = 0,5. Такође је ∥x₁∥ = 1, па пишемо:

λ₁ = 1     x₁ = (-0,7715; -0,6172; -0,1543),
λ₂ = 0,6     x₂ = (0,7071; 0,0000; -0,7071),
λ₃ = 0,5     x₃ = ( 0,0000; -0,7071; 0,7071).

Међутим, онакви или овакви, такви својствени вектори нису и вектори расподела вероватноћа, са ненегативним коефицијентима збира један.

Стохастичка норма је она која нам овде треба, ознаке ∥x∥₁, или просто

∥x∥ = |ξ₁| + |ξ₂| + ... + |ξ_n|,

ако се подразумева ℓ₁. Ову норму означавамо краће ℓ, а зовемо и 1-норма.

2. Код матрица уопште и линеарних оператора које оне представљају, као што знамо, постоје карактеристичне (својствене) једначине Ax = λx. Број карактеристичних вредности (λ₁, λ₂, ..., λ_n) једнак је реду матрице. Овај је једнак броју чланова низа, компоненти вектора, а они су број димензија векторског простора. Свакој појединој λ_k припада неки својствени вектор x_k, тако да је Ax_k = λ_kx_k, за k = 1, 2, ..., n.

Када колоне матрице A разапињу векторски простор исте димензије (n) кажемо да матрица није дегенерисана. Онда су све својствене вредности матрице различите и постоји инверзна матрица тако да је AA^-1 = A^-1A = I. Дакле, када матрица није дегенерисана, њени својствени вектори (x_k иде са λ_k) линеарно су независни. Они су тада колоне једне помоћне матрице P = P[x₁, x₂, ..., x_n] такве да је AP = PD, где је D дијагонална матрица.

13. Пример. Иста претходна матрица A, њена помоћна P и дијагонална матрица D = P^-1AP су редом:

\[ \begin{pmatrix} 0,8 & 0,2 & 0,2 \\ 0,2 & 0,7 & 0,2 \\ 0 & 0,1 & 0,6 \end{pmatrix}, \quad \begin{pmatrix} \frac{5}{\sqrt{42}} & \frac{1}{\sqrt{2}} & 0 \\ \frac{4}{\sqrt{42}} & 0 & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{42}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0,6 & 0 \\ 0 & 0 & 0,5 \end{pmatrix}. \]

Како је A = PDP^-1, то је A² = PD²P^-1, ..., A^r = PD^rP^-1 =

\[ P \begin{pmatrix} 1^r & 0 & 0 \\ 0 & 0,6^r & 0 \\ 0 & 0 & 0,5^r \end{pmatrix} P^{-1} \to P \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} P^{-1} = \begin{pmatrix} 0,5 & 0,5 & 0,5 \\ 0,4 & 0,4 & 0,4 \\ 0,1 & 0,1 & 0,1 \end{pmatrix}. \]

Добили смо матрицу C са почетка ових разматрања (Narrowing), која је такође стохастичка, али је „црна кутија“ канала преноса података. Она сваки вектор пресликава у вектор (0,5; 0,4; 0,1). □

3. Информације колона матрице A су (приближно):

-0,8⋅log₂0,8 - 0,2⋅log₂0,2 - 0⋅log₂0 = 0,722
-0,2⋅log₂0,2 - 0,7⋅log₂0,7 - 0,1⋅log₂0,1 = 1,157
-0,2⋅log₂0,2 - 0,2⋅log₂0,2 - 0,6⋅log₂0,6 = 1,371

збирно 3,250 bit-а. Она конвергира матрици A^r → C информације колоне

-0,5⋅log₂0,5 - 0,4⋅log₂0,4 - 0,1⋅log₂0,1 = 1,361

или збирно три пута 4,083 bit. Како је претходно примећено, повећањем дужине ланца, ова информација расте. Међутим Cx је

\[ \begin{pmatrix} 0,5 & 0,5 & 0,5 \\ 0,4 & 0,4 & 0,4 \\ 0,1 & 0,1 & 0,1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 0,5 \\ 0,4 \\ 0,1 \end{pmatrix} \]

за сваки вектор вероватноће x = (x₁, x₂, x₃), јер је x₁ + x₂ + x₃ = 1, па је промена улазне и излазне информације променљиве вредности. Ово такође спада у разлике између „шума поруке“ и „шума канала“.

4. Дакле, када је генератор Марковљевог ланца недегенерисана матрица канала, попут A, колоне су јој вектори расподела вероватноћа и разапињу векторски простор димензије реда матрице. Детерминанта јој није нула и таква има инверзну матрицу, различите својствене вредности и припадне својствене векторе који разапињу простор исте димензије. Та се матрица може дијагонализовати. Свеједно, видели смо, степеновањем она може дегенерисати у „црну кутију“.

Оно што је важно приметити код таквих недегенерисаних матрица је да степеновањем, композицијом трансформација, детерминанта све дужег ланца тежи нули, ако је |det(A)| < 1, као у наведеном случају, det(A) = 0,3. Како је детерминанта производа једнака производу детерминанти, то је:

det(A^r) = (det A)^r = (0,3)^r → 0,   r → ∞.

Гранична вредност низа трансформација је матрица детерминанте нула. Питање конвергенције Марковљевог ланца ка „црној кутији“ тако поста ствар дегенерације генератора ланца, са јединственим критеријумом. А дегенерација се дешава ако и само ако је |det(A)| < 1.

5. Ту је и опште правило. Матрица нулте детерминанте није регуларна, нема инверзну матрицу. Она пресликава тако да на основу копије није могуће одредити оригинал, те је „црна кутија“. Свака ће матрица A чија детерминанта |det(A)| < 1 имаће „шум канала“. Међутим, постоје поруке које ће се и тада тачно преносити. У 13. примеру таква је (0,5; 0,4; 0,1), вектор у који иначе сваки прелази.

Горња троугаона матрица испод главне дијагонале има све коефицијенте нуле, а на дијагонали су њене својствене вредности. Када је стохастичка, први елеменат дијагонале је 1, јер збир те колоне мора бити 1. Међутим, она зато има својствену вредност λ₁ = 1 и одговарајући својствени вектор x₁ = (1, 0, ..., 0) који јесте расподела вероватноћа.

Уколико горња троугаона матрица T нема других јединица на дијагонали сем прве, степеновањем имаће све мање дијагоналне елементе и све веће изнад, да би у граничном случају то могла била матрица са јединицама у првом ретку и свим осталим елементима нулама.

14. Пример. Горња троугаона стохастичка матрица

\[ T = \begin{pmatrix} 1 & 0,2 & 0,1 \\ 0 & 0,8 & 0,2 \\ 0 & 0 & 0,7 \end{pmatrix} \]

има својствене вредности λ₁ = 1, λ₂ = 0,8 и λ₃ = 0,7 припадних својствених вектора, истим редом:

\[ x_1 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \quad x_2 = \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}, \quad x_3 = \begin{pmatrix} 1 \\ -2 \\ 1 \end{pmatrix} \]

Први од њих x₁ је и вектор расподеле вероватноће, па из Tx = λ₁x₁ следи T^rx₁ = T^r-1x₁ = ... = x₁. То је својствени вектор и ланца Маркова. □

Детерминанта матрице је производ свих својствених вредности матрице, а траг је њихов збир. Према томе, горња троугаона стохастичка матрица са свим позитивним бројевима дијагонале има позитивну детерминанту, ова det(T) = 0,56. Такав број степеновањем постаје све мањи и тежи нули, a ланац Маркова генерисан матрицом T дегенерише у „црну кутију“. Али сваки исечак тог ланца има непромењен својствени пар λ₁ и x₁ тако да ће „шум поруке“ и у овом случају бити мимо „шума канала“.

Degeneration

Питање: Неке се информације не мењају током „дегенерације канала“?

Одговор: Тако је, видљиво је то у прошлом одговору (14. Пример). Троугаона стохастичка матрица дегенерише, док ниже карике

T → T² → ... → T^k → ... C

корацима ланца Маркова који конвергира црној кутији C. При томе, вектор x₁ = (1, 0, 0) остаје својствени свакој дужини T^k, са својственом вредношћу λ₁ = 1.

15. Пример. Размотримо стохастичку горњу троугаону матрицу трећег реда у општем облику

\[ T = \begin{pmatrix} 1 & λ' & α \\ 0 & λ & β \\ 0 & 0 & γ \end{pmatrix} \]

чији су сви коефицијенти ненегативни, а λ' + λ = 1 и α + β + γ = 1. Нађимо општи облик за T^k за k = 1, 2, 3, ... и границу T^k → C, када k → ∞.

Решење: Јасно је да је

\[ T^k = \begin{pmatrix} 1 & λ'_k & α_k \\ 0 & λ^k & β_k \\ 0 & 0 & γ^k \end{pmatrix}, \]

где је λ'_k = 1 - λ^k и α_k + β_k + γ^k = 1. Множећи прву матрицу са другом (TT^k), налазимо:

β_k+1 = λβ_k + βγ^k = ... = β(λ^k + λ^k-1γ + ... + γ^k),
β_k = β(λ^k - γ^k)/(λ - γ),   λ - γ ≠ 0,
λ^k, γ^k → 0,   γ, λ < 1.

Добијамо исто множећи прву матрицу са другом (TT^k) и другу са првом (T^kT) и изједначавањем:

β_k+1 = λβ_k + βγ^k = λ^kβ + β_kγ,
(λ - γ)β_k = (λ^k - γ^k)β → 0,   γ, λ < 1.

Множења прве са другом и друге са првом такође дају:

α_k+1 = α_k + λ'β_k + αγ^k = α + λ'_kβ + α_kγ,
(1 - γ)α_k = α + λ'_kβ - λ'β_k - αγ^k.

Када λ < 1, тада (1 - γ)α_k → α + β. Ако λ = 1, онда (1 - γ)α_k → α. □

Општа решења из овог примера проверавамо уврштавајући вредности константи (T^k → C, k → ∞). Које су написане нису нуле:

\[ 1. \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}^k \to \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \] \[ 2. \quad \begin{pmatrix} 1 & \lambda' & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & 1 \end{pmatrix}^k \to \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \] \[ 3. \quad \begin{pmatrix} 1 & 0 & \alpha \\ 0 & 1 & 0 \\ 0 & 0 & \gamma \end{pmatrix}^k \to \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}, \] \[ 4. \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & \beta \\ 0 & 0 & \gamma \end{pmatrix}^k \to \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}, \] \[ 5. \quad \begin{pmatrix} 1 & 0 & \alpha \\ 0 & 1 & \beta \\ 0 & 0 & \gamma \end{pmatrix}^k \to \begin{pmatrix} 1 & 0 & \frac{\alpha}{\alpha + \beta} \\ 0 & 1 & \frac{\beta}{\alpha + \beta} \\ 0 & 0 & 0 \end{pmatrix}, \] \[ 6. \quad \begin{pmatrix} 1 & \lambda' & \alpha \\ 0 & \lambda & \beta \\ 0 & 0 & \gamma \end{pmatrix}^k \to \begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}. \]

Директним множењем, TC = C, утврђујемо тачност ових.

Други начин да проверавамо овакве формуле је помоћу конкретних вредности и рачунања, рецимо за k = 16 на три децимале.

\[ 1. \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}^{16} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \] \[ 2. \quad \begin{pmatrix} 1 & 0,2 & 0 \\ 0 & 0,8 & 0 \\ 0 & 0 & 1 \end{pmatrix}^{16} \approx \begin{pmatrix} 1 & 0,832 & 0 \\ 0 & 0,168 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \] \[ 3. \quad \begin{pmatrix} 1 & 0 & \alpha \\ 0 & 1 & 0 \\ 0 & 0 & \gamma \end{pmatrix}^{16} \approx \begin{pmatrix} 1 & 0 & 0,997 \\ 0 & 1 & 0 \\ 0 & 0 & 0,003 \end{pmatrix}, \] \[ 4. \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & \beta \\ 0 & 0 & \gamma \end{pmatrix}^{16} \approx \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0,997 \\ 0 & 0 & 0,003 \end{pmatrix}, \] \[ 5. \quad \begin{pmatrix} 1 & 0 & 0,1 \\ 0 & 1 & 0,2 \\ 0 & 0 & 0,7 \end{pmatrix}^{16} \approx \begin{pmatrix} 1 & 0 & 0,332 \\ 0 & 1 & 0,665 \\ 0 & 0 & 0,003 \end{pmatrix}, \] \[ 6. \quad \begin{pmatrix} 1 & 0,2 & 0,1 \\ 0 & 0,8 & 0,2 \\ 0 & 0 & 0,7 \end{pmatrix}^{16} \approx \begin{pmatrix} 1 & 0,972 & 0,947 \\ 0 & 0,028 & 0,050 \\ 0 & 0 & 0,003 \end{pmatrix}. \]

Значење ових бројева је уобичајено На пример други случај (2): други сигнал (x₂) ће сваким кораком ланца Маркова (T) са вероватноћом 0,2 бити прослеђен у први сигнал (x₁), са вероватноћом 0,8 у други (исти који је послат), а никада у трећи (x₃). Након 16 корака (матрицом T¹⁶) други ће сигнал прећи у први са вероватноћом 0,832 и са вероватноћом 0,168 у други, а такође никада у трећи. Иако је порука x = (x₁, x₂, x₃) независна расподела вероватноћа, канал их корацима адаптира.

Када посматрамо карактеристичну једначину T^kx = x, која не мења вектор x, налазимо да је у првом случају (1) сваки вектор својствени. Други случај (2) има x = (1, 0, 0) и (0, 0, 1) својствене векторе. У трећем (3), четвртом (4) и петом (5) случају је својствени сваки вектор (p, q, 0) негативних коефицијената збира један. Својствени вектор шестог (6) случаја је (1, 0, 0), иначе заједнички за свих шест.

Као што видимо, линеарна алгебра дозвољава исто оно што ова теорија информације на свој начин предвиђа (Far Before). Неке се информације не мењају током „дегенерације канала“ и то отвара могућност преноса у садашњост и прастарих информација из „времена пре времена“. Поред „без садржајних“ и подразумеваних неизвесности попут (p, q, 0), то су и извесности законитости попут (1, 0, 0). Наравно, разматрана матрица T није једина врста генератора ланаца Маркова.

Cyclical

Питање: Може ли канал без шума имати „шум поруке“?

Одговор: Може, рецимо кружним дезинформацијама. Када се први сигнал извесно преслика у други, други у трећи и тако даље редом, а задњи у први.

Матрица A овакве обмане има по јединицу у свакој колони тако да јој је детерминанта det(A) = 1. То значи да низ n = 1, 2, 3, ... корака канала има исту детерминанту, јер det(Aⁿ) = (det A)...(det A) = 1. Даље ово значи да Марковљев ланац не дегенерише у „црну кутију“. Он пермутира лажи у нове лажи, али повремено (у не дуже од n корака) искаже и тачну полазну поруку.

Помоћу нове дефиниције „шума канала“ (Narrowing) добијамо исто, јер је сваки сабирак -Δp_k⋅log Δp_k = 0, било да су дате вероватноћа јединице или нуле, а поменута матрица A такве једино има. Збир свих тих „Шенонових сабирака“ је нула, па је „шум канала“ Ν = 0. Удаљеност ∥x' - x∥ излазне од улазне поруке (x' = Ax) може бити драстична, па се таквим може видети и „шума поруке“ појединог корака канала. Међутим, сваких неког периода (корака), порука постаје почетна и поново креће у свој циклус.

16. Пример. Стохастичка матрица

\[ Ax = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} x_2 \\ x_3 \\ x_1 \end{pmatrix} = x' \]

ради управо описану пермутацију, дезинформацију. Међутим, A²x = x'' би била још једна циклична замена у нову дезинформацију, али би наредни, трећи корак ланца, A³x = x, дао почетну вредност. □

Ово је био пример матрице трећег реда (n = 3) и довољно једноставан да се лако види цикличност која настаје њеним степеновањем. Показује се да слично важи за сваку стохастичку матрицу (n ∈ ℕ) која је пермутација колона јединичне. Штавише, показује се да су цикличне појаве свукуда око нас и прешироко подручје (Ротације) за један кратак одговор.

Regular

Питање: Шта је то стохастичка, а шта је регуларна матрица?

Одговор: Матрица K назива се стохастичка када је њен сваки елеменат ненегативан, а збир сваке њене колоне је јединица. Производ таквих матрица, ако постоји биће опет стохастичка матрица неког канала, па ће и степени такве давати стохастичке матрице K^r. Детерминанта регуларне матрица је она за коју детерминанта није нула. Када det(K) = 0, матрица је сингуларна.

1. Често се погрешно каже да је стохастичка матрица K „регуларна“ ако су сви елементи бар неког њеног степена K^r позитивни. То се узима њеном „уобичајеном“ дефиницијом, па и да зато она има инверзну матрицу K^-1 за коју важи KK^-1 = K^-1K = I, где је I јединична матрица. Али са тиме смо у контрадикцији са матрицом на претходној слици чија детерминанта јесте нула. Наводи да матрице са позитивним елементима имају детерминанте различите од нуле нису тачни, већ за матрицу на тој слици десно.

Дакле, детерминанта регуларне матрице K није нула (det K ≠ 0), она има инверзну матрицу K^-1 са којом множена даје јединичну, њени сви ступци су линеарно независни вектори, регуларна матрица се дијагонализује, и тако даље ..., није сингуларна.

2. У опису матрица канала (Channel, Теорема), ради бржег препознавања, наводио сам да је матрица регуларна (има ненулту детерминанту), када је сваки њен дијагонални елеменат већи од збира осталих тог ретка. Наиме, ако детерминанта јесте нула, једначина Kx = 0, посматрана као хомогени систем линеарних једначина произвољних непознатих x = (p₁, p₂, ..., p_n), ће имати нетривијално решење (x ≠ 0).

Ако је |p_i| највећа од тих варијабли, посматрамо i-ти редак:

k_i1p₁ + ... + k_iip_i + ... + k_inp_n = 0,
|k_iip_i| = |∑_j:j≠i k_ijp_j| ≤ ∑_j:j≠i |k_ijp_j|,
|k_ii| = ≤ ∑_j:j≠i |k_ij p_j/p_i| ≤ ∑_j:j≠i |k_ij|,
|k_ii| = ≤ ∑_j:j≠i |k_ij|

а ово би била контрадикција са претпоставком, јер дијагонални елеменат није већи од збира осталих свог ретка. У доказу се користе шири скупови варијабли, али тврђење теореме остаје тачно и за расподеле вероватноћа.

3. Међутим, да обрнуто не стоји видимо из примера следеће матрице чија је детерминанта -1/16 = -0,0625.

\[ K = \begin{pmatrix} 0,50 & 0,25 & 0,25 \\ 0,25 & 0,50 & 0,25 \\ 0,25 & 0,25 & 0,50 \end{pmatrix} \]

Својствене вредности ове стохастичке матрице су λ₁ = 1 и два пута λ₂ = λ₃ = 0,25. Само прва од њих има својствени вектор x = (1/3, 1/3, 1/3) који је уједно вектор расподеле вероватноће, па K^r дивергира матрици чији сви коефицијенти износе 1/3. Све полазне расподеле кроз Марковљев ланац генерисан овом матрицом тако, током ланца, конвергирају наведеној x.

Исти пример показује нам још нешто, да „дегенерисана“ матрица (са поновљеним својственим вредностима) није исто што и „сингуларна“ матрица (детерминанте нула).

Fredkin

Питање: Како да употребим Марковљеве матрице?

Одговор: Инжењерски је посао претварање теорије у праксу, а мало шире гледано, на сличним задацима су многи од научника до занатлија. Нећемо се мешати у њихове ствари када погледамо неколико примера.

1. Пример дијагностике, који сам недавно навео, поучан је и поприлично универзалан. Уз мало познавања елементарне физике, он се лако преводи у „рад силе на путу“, ΔE = F⋅Δx. У матричној једначини (E = Fx), рад силе поприма облик

\[ \begin{pmatrix} E_1 \\ E_2 \end{pmatrix} = \begin{pmatrix} F_{11} & F_{12} \\ F_{21} & F_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \]

где је E_ij = F_ijx_j потрошена енергија (E_i) за дејство силе (F_ij) током њеног дејства на путу дужине (x_j). Ове силе су константне, иначе су путеви мала растојања при потрошњи одговарајућих мањих порција рада. Поједине су силе матрице (формално) условне вероватноће, или условно-последичне размене одговарајућих енергија.

Као што видимо, у примени „дијагностике“ ће нешто знања, мало маште и инжењерске прецизности овде употребљених појмова бити довољни да се зачас нађемо у чистој физици. Да је „само небо граница“ таквима који би да користе Марковљеве ланце сведочи и следећи пример.

2. На слици горе лево је „Фредкинова капија“, универзално компјутерско коло, или електрични прекидач за има-нема тока струје, односно тачно-нетачно алгебре логике. То је веома мала склопка са три улаза (a, b, c) и три излаза (a', b', c'). Обично је b = ā и b' = ā', a c' = c.

Када је на улазу c = 0 (нема струје, или нетачно ⊥), а a = 1 и b = 0, биће на излазу обрнуто a' = 0 и b' = 1, а c = 0. Тада a = 0 на улазу постаће a' = 1 на излазу. Ако је на улазу c = 1 (има струје, или тачно ⊤), а a = 1 и b = 0, биће на излазу a' = 1 и b' = 0, а c = 1. Тада a = 0 на улазу остаће a' = 0 на излазу.

Ово можемо описати матричном једначином (x' = Fx)

\[ \begin{pmatrix} a' \\ b' \end{pmatrix} = \begin{pmatrix} \bar{c} & c \\ c & \bar{c} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \]

где множење значи конјункцију алгебре логике, а сабирање дисјункцију. Отуда је само корак до вероватноће, \( c \in [0, 1] \) и \( \bar{c} = 1 - c \), са матрицом F која постаје генератор ланца Маркова.

3. Јединичну матрицу I можемо растављати на факторе, што иначе није могуће са бројевима, рецимо на квадрате Паулијевих матрица:

\[ \sigma_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \sigma_2 = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad \sigma_3 = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}. \]

За сваку од ових је σ² = I, па сваки вектор можемо писати бар на следећа три формално једнака начина x = Ix = σ²x, а различитих интерпретација. Сваки од ових случајева је посебна прича примена Марковљевих ланаца, толико опширна да ће морати чекати бољу прилику.

Право питање није има ли примена Марковљевих ланаца, него зашто их је толико пуно. Заједнички разлози су им повод узимања свеприсутности информације у природним појавама, а лакоћа везивања интерпретација за вероватноће разлог је тражењу суштине информације у неизвесности. Како то све увезати, биће занимљива и тек проблематична област.

Alignment

Питање: Порука се прилагођава преноснику, али и обрнуто?

Одговор: Тако је. Прилагођавање стања и процеса у основи је ове теорије информације (A Blur), а понашање порука примећено у Марковљевом ланцу ограничена је врста формалне потврде.

Константност генератора ланца, матрице A, једна је од врста тих ограничења. Друга је да се више или мање таквих матрица могу смењивати током процеса. Али као једноставан модел, у првој фази уочавања ситуација и промена информација, Марковљев ланац је поучан и приближно довољан.

1. Не комуницира све са свачим, па околина не преузима и не прослеђује све своје појаве једнако. Свака од „порука“ која комуницира са околином тако постаје и „преносник“, па у стварности обе адаптације, информација које се преносе на канал преноса и канала информацијама, неизбежне су. Прве су брже, лакше видљиве, а прилагођавања укупне околине на своје чиниоце сложенији је ток сталног усредњавања.

Због начелне тежње мањој информацији, може се очекивати да вредност детерминанте процеса (det A) у просеку расте. Да супротно дегенерацији поједине поруке тече процес регенерације самог канала, али обзиром на већу тежину канала, да дегенерације надвладавају. Аналогно поравнању орбита планета Сунчевог система које постаје видљивије, од револуције масовног Сунца по сличној.

2. Попут периодичног обртања планета око сунца (револуција), могуће су разне периодичне појаве. Тада једна „карика“ ланца Маркова и сама бива ниска трансформација A = A₁A₂...A_m, при чему се временом (t) и m-члани низови полако мењају A = A(t). Садашњост одмиче брзином светлости c, највећом од физичких брзина, остављајући траг прошлости иза себе тако да је њена густина информације све мања, а заоставштина све дебља.

Посматрајући „кретање“ садашњости у 6-дим простор-времену, обзиром на закон одржања (садашњост) + (прошлост) = const, намеће се и питање брзине стизања нас од стране прошлих инвормација. Становишта сам да нема глупих питања, сем евентуално глупих одговора, па би и један такав сумњивац могла бити идеја да брзина светлости, или велика брзина које год информације, садашњости успорава у односу на бивше. Брже поруке тако даље стижу, а светлост је по том посебна јер њена брзина не зависи од брзине посматрача.

3. Међутим, прошлост је псеудо-реалност и њена „кретања“ нису шире прихватљива. Тада стварнија могућност преноса порука из прошлости у садашњост била би дуже очување извесних парчића, таквих отпорнијих на хабање. Смањена дегенерација појединих детаља од просечне могућа је због начелне разноликости, а исто и њихова конзерввација за емисије некој будућој садашњости.

Прва „сулуда“ (хипо)теза, о већој брзини светлости некад него сад, иначе се слаже са растућом васионом, са све већом (опаженом) брзином њеног ширења и умањењем густине енергије или масе свемира. Са геометријом 6-дим простор-времена која тако „гравитационо“ вуче напред наш 4-дим свет догађаја. Такође са опадањем неизвесности садашњости све бољим њеним усмераварњем из прошлости.

4. Гледајући низ информација x = (x₁, x₂, ..., x_n), x' = Ax, x'' = Ax', ..., или уопште x^(r) = A^rx, где је r = 0, 1, 2, ..., примећујемо да све дужи преноси, одломци композиција, стижу из све даљег од садашњости и све ближег евентуалној „црној кутији“. Са становишта текућег, тада уоченог корака преноса, они бивши што су даљи то имају већу количину неизвесности, информацију. Ово иде у прилог „минимализму“.

У том смислу формуле за мерење сужавања канала употребљиве иначе за дефинисање брзине дегенерације (по кораку трансформације), могу бити и мера „привлачне силе“ будућности. Она је врста „силе вероватноће“, те одбојне „силе неизвесности“, а на дужем штапу и поменутог успоравања брзине светлости у јачој гравитацији.

Flows

Питање: Како и зашто уопште долази до интеракција, ако оне нису у нарави природе?

Одговор: Кључ свега дешавања, па и „немогућег“ је неизвесност. Полазећи од тога, а издвајајући делове интеракција, извесније има предност, не и ексклузиву. Затим приметићемо да постоје смернице мањка правилности.

1. Видели смо како Марковљеви процеси дегенеришу у „црне кутије“, а посебно такве које свако стање (вектор вероватноће) производе у једно исто. Тада остајемо без могућности да на основу примљених сазнајемо послате поруке. Када такав један процес (A) делује на стање, па сличан други (B), дешава се следеће:

\[ BA = \begin{pmatrix} b_1 & b_1 & ... & b_1 \\ b_2 & b_2 & ... & b_2 \\ ... & ... & ... & ... \\ b_n & b_n & ... & b_n \end{pmatrix} \begin{pmatrix} a_1 & a_1 & ... & a_1 \\ a_2 & a_2 & ... & a_2 \\ ... & ... & ... & ... \\ a_n & a_n & ... & a_n \end{pmatrix} = B, \]

јер је a₁ + a₂ + ... + a_n = 1. Нови процес апсорбује првог. Он то чини тако што пресликава сваку његову колону, као иначе расподеле вероватноћа. Преузимање вектора тече каскадно BAx = Ba = b без памћења.

Стања су поруке, вектори расподела вероватноћа:

x = (x₁, x₂, ..., x_n),
a = (a₁, a₂, ..., a_n)
b = (b₁, b₂, ..., b_n),

коефицијената x_k, a_k, или b_k ненегативних (реалних) бројева збира један.

2. Памћење елементарним честицама даје окружење. Оне га многе немају по себи и стичу као правце сопственог кретања, или уопште трајекторија најмањег дејства, релативно у односу на дате посматраче. Интеракције са околином дефинишу субјекте физичког деловања, па они који у томе не учествују и не постоје (за укупни систем). Тек тренутак мерења електрона одредиће и његову дотадашњу путању, приметили су оснивачи квантне механике, а ми даље објашњавамо: јер се дејствујући изјашњава, губи нешто од неизвесности и добија на извесности.

У том смислу претходни (1) процеси без меморије „постоје“ само сами по себи, не онакви каквима бисмо их могли виђати. Као и у случају честице (поруке, стања), са становишта посматрача ове процесе такође усмерава прошлост датог, његовог окружења. Прошлост и смер кроз садашњост у будућност маси (мноштву) дефинишу закони великих бројева из теорије вероватноће и евентуалних, можда још неоткривених.

3. Континуитет појава постоји онолико колико смо га својим присуством остварили. Отуда принцип најмањег дејства физичког свега око нас, или тежња система ка мањој информацији. Природе без комуникације нема, али чиниће све да њих и интеракција буде што мање. Најозбиљније међу препрекама у томе јој је закон одржања информације. Зато нема давања без примања и нема бега из свег зачараног круга размењивања.

Што се више супстанце удружује да би веће биле прилике за давања, то су и већа ограничења појединца у односу на смернице колектива. Утапајући се у веће токове притоке губе нешто од својих слобода, па сума сумарум, поигравајући се тако, шира природа као да нигде не доспева. Осим што успева држати се начела непоновљивости.

4. Развојност је неопходна због закона одржања и јединствености, а отуда и интеракције. Међутим, такве се потребе на различите начине подвлаче под начело мањeг дејства, па прикључивање мањих јединица већем броју постаје ствар Чебишевљеве неједнакости, као и опште гравитације, или Бернулијеве једначине (Fluid). Прилазећи већем (мноштву, телу, флуксу) постиже се локално смањење информације.

Објашњење Ајнштајновом теоријом релативности производње магнетног поља кретањем електирчног набоја видите у необичном прилогу овде, уз одбојну узајамну силу због кретања усамљених електрона (Current). Када такве супротности виђамо у примерима од поменутих, па до ограђености живе ћелије и њене склоности удруживању, не признамо им повезаност јер још увек не познајемо формализам попут математичког који им даје структуру.

5. Иза свих ових појава стоји начелна штедљивост информације, или на елементарном нивоу гледано, тежња да се вероватнији исходи дешавају чешће. Као код Комптоновог ефекта (Collision) када фотон сударајући се са електроном губи енергију повећавајући таласну дужину, прелазећи на размазанију путању мање густине вероватноће, тако се и уопште дешава интеракција због локалне тежње субјекта за мањим дејством.

Нема изузетака у тим тежњама у данас познатој теоријској физици, нити тада има изостанка комуникације у овим њеним интерпретацијама које јој додајем. Дакле, на питање како и зашто имамо интеракције, одговор је у настојањима ка мањем и немогућности да се то заиста постигне. Сви потребни детаљи те приче не могу стати у један краћи опис.

6. Сложенији системи где доминирају приближавања средње (Шенонове) информације ка вероватноћи, код трансфера попут Марковљевих ланаца, а у случајевима неких меморисања (0 < |det A|, |det B| < 1), композицијом граде процесе мање вредности детерминанте од сваког од фактора:

|det(AB)| = |det(A)| ⋅ |det(B)| < min{|det(A)|, |det(B)|},

што значи неизбежну дегенерацију. Посебно, облик AB = C₁ биће

\[ \begin{pmatrix} 0,9 & 0,2 \\ 0,1 & 0,8 \end{pmatrix} \begin{pmatrix} 0,6 & 0,3 \\ 0,4 & 0,7 \end{pmatrix} = \begin{pmatrix} 0,62 & 0,41 \\ 0,38 & 0,59 \end{pmatrix}, \]

са детерминантама 0,7 ⋅ 0,3 = 0,21. Обрнуто множење BA = C₂ даје

\[ \begin{pmatrix} 0,6 & 0,3 \\ 0,4 & 0,7 \end{pmatrix} \begin{pmatrix} 0,9 & 0,2 \\ 0,1 & 0,8 \end{pmatrix} = \begin{pmatrix} 0,57 & 0,36 \\ 0,43 & 0,64 \end{pmatrix} \]

дакле, другачију матрицу са истом детерминантом претходној. Видимо у првом множењу (C₁) извеснију прву колона расподела вероватноћа, него исту колону другог множења (C₂), а обрнуто других колона. Обзиром да се множење вектора матрицом рачуна са десна у лево, то значи да новије множење покрива старије у првим коефицијентима вектора (расподеле).

7. Последњи догађаји су битнији, видљивији, за водеће вероватноће. Ако имамо дуге низове исхода и истичемо напред оне вероватније, да би иза могло остајати и бесконачно много небитних, извеснији крајњи процеси даваће извесније текуће, крајње векторе. Такав, стабилан развој је управо онај који нам се дешава. Он се слива у извеснију садашњост док за собом вуче све дужи траг прошлости.

Symmetry

Питање: Шта је то дупла, двоструко стохастичка матрица?

Одговор: Квадратна је матрица лева стохастичка, ако се састоји од ненегативних реалних бројева чији збир сваке колоне је 1. Десна стохастичка матрица квадратна је такође ненегативних реалних бројева, али збира сваког ретка 1. Двоструко стохастичка матрица је квадратна ненегативних уноса са сваким редом и колоном збира један.

Транспоновањем леве (заменом колона и редова) добија се десна стохастичка матрица и обрнуто. Производ десних биће десна, као што је производ левих увек лева стохастичка матрица (Chain, 2). Према томе, производ двоструко стохастичких матрица увек је двоструко стохастичка матрица.

1. Следећа су два примера дупле стохастичке матрице (A) која јесте и која није (B) симетрична:

\[ \begin{pmatrix} 0,7 & 0,2 & 0,1 \\ 0,2 & 0,5 & 0,3 \\ 0,1 & 0,3 & 0,6 \end{pmatrix}, \quad \begin{pmatrix} 0,7 & 0,1 & 0,2 \\ 0,2 & 0,6 & 0,2 \\ 0,1 & 0,3 & 0,6 \end{pmatrix}, \]

јер прва је једнака себи транспонованој (A^⊤ = A), а друга није (B^⊤ ≠ B). Те, симетричне стохастичке матрице подврста су ермитских, комплексних и небитног збира коефицијената, али инваријантне (непромењиве) након транспоновања са коњуговањем, тзв. адјунговања (H^† = H).

Својствне вредности само-адјунгованог оператора су реалне, па су такве и својствене вредности симетричне стохастичке матрице. У првом случају је det(A) = 0,13 са својственим вредностима (eigenvalue) λ₁ = 1, λ₂ ≈ 0,57 и λ₃ ≈ 0,23. Други случај има детерминанту det(B) = 0,2 и такође позитивне својствене вредности λ₁ = 1, λ₂ = 0,5 и λ₃ = 0,4.

Свака дупла стохастичка матрица M реда n ∈ ℕ, била симетрична или не, има својствену вредност λ = 1 којој одговара својствени вектор расподеле вероватноће x = (1/n, 1/n, ..., 1/n), тако да је Mx = x. Остали од својствених вектора не морају бити расподеле вероватноћа.

2. Стандардна интерпретација матрице M = (p_ij) генератора Марковљевог ланца је да коефицијент p_ij значи условну вероватноћу да ће послати j-ти сигнал бити прослеђен као i-ти. Ако j-та колона сигурно садржи неки од могућих сигнала, редом индексираних ретка i = 1, 2, ..., n, онда је матрица M лева стохастичка, или краће стохастичка. Додатно, ако сваки i-ти редак сигурно може препознати неки од j = 1, 2, ..., n могућих послатих сигнала, онда је матрица и десна стохастичка, односно она је дупла стохастичка.

Приметимо да претходно подразумева независност и потпуност условних вероватноћа, коефицијената матрице M. Тада су и њене колоне и редови расподеле вероватноћа, а то је подразумевана ситуација, а таква матрица је дупла стохастичка. Међутим, може доћи до грешака, рецимо да се j-ти сигнал протумачи вишеструко или никако, када се може десити пребачај или подбачај збира један. Слично се може десити са i-тим ретком и исти да препознаје вишеструко или никако послати сигнал. Тада је матрица M приближно дупла стохастичка.

Познат је случај шаховског меча тада првака света велемајстора Гарија Каспарова против суперкомпјутера (1997), када га је компјутер победио резултатом 3,5 : 2,5. Рачунар је у једној повукао необичан потез који су велемајстор и саветници сатима и целу ноћ покушавали одгонетнути. А тек су инжењери дуго након победе машине установили да је тај чудни потез био последица грешке у електричним колима — која се ретко али ипак догађа.

3. Чак и када матрица канала непогрешиво ради, била она типа A или B из претходног примера (1), сигурно ће пропустити поменути својствени вектор x својствене вредности λ = 1, иначе максималну неизвесност. Она тако иде кроз дуги ланац Маркова, без обзира на његову дегенерацију.

Уколико сама матрица M прави описане грешке (2), онда ће на тај мало другачији начин неизвесност опет путовати ланцем. Пренос грешака и неизвесности реалним процесима, овако или онако, неизбежан је.

Dominant

Питање: Постоји ли назив за пар својствених вектор-вредност?

Одговор: Пар карактеристичних (eigenvalue/eigenvector) називамо најважнијим паром, претежним, водећим, главним, доминантом.

1. Погледајмо то на усмереном графу, на слици лево (диграф), који представља такмичење три тима (1, 2, и 3 заокружена).

Први је два пута победио други и једном трећи. Други само једном трећег. Трећи тим има по једну победу против првог и једну против другог. Придружимо им матрицу.

\[ A = \begin{pmatrix} 0 & 2 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{pmatrix}, \]

са коефицијентима a_ij, где су бројеви ретка и колоне i, j = 1, 2 и 3 ознаке тимова. Тако је a₁₂ = 2 и значи две победе првог против другог тима, па све до a₃₂ = 1 што значи једну победу трећег против првог тима. Успеси тимова пореданих од најбољег ка лошијем су: 1, 3, 2. Први је имао три победе, трећи две, а други само једну (Perron-Frobenius Theorem).

2. То је пример са n = 3 тима у надметању и вектором x = (x₁, x₂, ..., x_n) са три рангирана учесника уноса x₁ = 3, x₂ = 1 и x₃ = 2, иначе победника где x_j представља снагу j-тог учесника. Додељујемо позитиван скор сваком тиму (i = 1, 2, ..., n):

\[ s_i = \frac{1}{n_i} \sum_{j=1}^n a_{ij}x_j \]

са нормализационим факторима бројем игара (овде свако n_i = 2) који је i-ти тим играо, јер не желимо да рангирање тима буде веће просто због више одиграних партија. Коефицијент матрице иначе a_ij ≥ 0, у примеру је број победа тима i против тима j, али се може вредновати и другачије.

Очекујемо да i-ти тим има скор s_i сразмеран снази x_i тог тима и да је тако за све компоненте вектора скора s = (s₁, s₂, ..., s_n). Дакле, претпостављамо да s = λx. То је заправо рангирање снаге вектора x као карактеристичног (својственог) вектора карактеристичне једначине Ax = λx.

Дати пример (1) има својствену вредност λ ≈ 1,879 и одговарајући вектор x ≈ (0,717; 0,381; 0,584), тако да је Ax ≈ λx. Пример такмичења и диграф (енг. directed graph), придружена (adjacency) матрица са скор-вектором требало би да осмисле назив „доминанта“ за пар својствених вредности-вектора (λ, x) матрице. Погледајте и рад о томе Универзитета у Верони.

3. Матрица је „несводива“ (енг. irreducible) ако преко пермутација није слична горњој блок троугаоној матрици, која има више од једног блока позитивне величине.

Може се показати да је она матрица (A) несводива која позитиван вектор, свих координата позитивних (x > 0), трансформише у позитиван (Ax > 0). Позитивни оператори (матрице) представљају усмерене процесе, који ће стања развијати у позитивна, зато и неповратна. Позитивни оператори су само-адјунговани (A^† = A), а све својствене вредности су му ненегативне.

Несводиву матрицу карактерише и њој придружен диграф (енг. digraph) који је „строго повезан“, што значи да се путем повезница од било којег чвора на неки начин може стићи до сваког чвора.

4. Перон-Фробениусова теорема каже да квадратна матрица A која има ненегативне уносе има и ненегативан својствени вектор x који одговара позитивној својственој вредности λ, тако да је Ax = λx. Када је матрица A несводива (irreducible), онда својствени вектор x (eigenvector) има строго позитивне уносе, јединствен је, једноставан и одговарајуће је својствене вредности (eigenvalue) највеће апсолутне вредности.

Ова теорема односи се и на стохастичке матрице, ненегативних уноса и колона збира један. Стохастички вектор p = (p₁, p₂, ..., p_n) има све уносе ненегативне бројеве, p_j ≥ 0, са збиром p₁ + p₂ + ... + p_n = 1. Стога су им и непосредне репрезентације расподеле вероватноћа. Транспоновањем, колоне постају врсте збира један, па:

\[ A^\top 1 = \begin{pmatrix} a_{11} & a_{21} & ... & a_{n1} \\ a_{12} & a_{22} & ... & a_{n2} \\ ... & ... & ... & ... \\ a_{1n} & a_{2n} & ... & a_{nn} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ ... \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ ... \\ 1 \end{pmatrix} = 1, \]

што значи, A^⊤ 1 = 1. Пошто A и A^⊤ имају исте детерминанте

det(A - λI) = det(A^⊤ - λI) = 0,

то су им и својствене вредности λ исте. Поделимо ли ову једнакост са n, добићемо својствени вектор који је расподела вероватноће. Како десна стохастичка матрица A^⊤ има својствену вредност λ = 1, такву ће имати и стохастичка матрица A. Не обавезно и наведени својствени вектор.

Када би неки својствени вектор p стохастичке матрице A имао својствену вредност |λ| > 1, онда из A^kp = |λ|^kp биће да низ стохастичких матрица A^k има експоненцијално растуће својствене вредности |λ|^k → ∞. То значи да почев од неког великог k ове матрице могу имати коефицијенте веће од један, a_ij > 1, што је немогуће. Множење стохастичких матрица истог реда даје стохастичке матрице (Chain, 2).

Ово је и доказ Перон-Фробениусове теореме за стохастичке матрице, да свака та A има својствену вредност λ = 1 којој одговара својствени вектор вероватноће p, тако да је Ap = p. То је интересантна особина „доминанта“ стохастичких матрица и прилог одговору на постављено ми питање.

Irreducible

Питање: Појасните ми још мало ту „несводивост“ оператора?

Одговор: Ок, на слици десно нека је, рецимо, шема кориштења или тока електричне енергије између центара заокружених бројем 1, 2 и 3. Усмерене повезнице нека су вероватноће тих испорука. Када је x_j количина доступна j-том, од сва n = 3 центра, онда је p_ij шанса слања тог дела у i-ти центар.

Говорим намерно уопштено да бисте модел лакше применили. Центри 1, 2, ..., n, могуће је да су банке са повезницама токовима новца, или су то тржишни центри међу којима колају услуге, робе и новац, или су друштва са познанствима. Па до случаја да говоримо о одузимању, на пример, да је p_ij шанса одвајања енергије од j-тог центра ка i-том.

1. Шта год, узмимо дате бројеве, формирамо матрицу M. Множимо ли је самом собом (степенујемо је) s = 1, 2, 3, ... пута, степен тежи ка граничној матрици M', приближно:

\[ M^s = \begin{pmatrix} 0.8 & 0 & 0 \\ 0.2 & 0.7 & 0.4 \\ 0 & 0.3 & 0.6 \end{pmatrix}^s \to \begin{pmatrix} 0.028 & 0 & 0 \\ 0.560 & 0.571 & 0.571 \\ 0.412 & 0.429 & 0.429 \end{pmatrix} = M', \]

где користимо децималну тачку, уместо децималног зареза. Стохастичка матрица трећег реда (n = 3) је резултат датог графа.

Усмерени граф (диграф) на слици јасно показује да од позиције „1“ нема пута до позиција „2“ и „3“, али су обрнути токови могући, непосредно као и посредно „3“ → „2“ → „1“. Зато остаје немогуће у првом (горњем) ретку степеновањем добијати било шта осим нула на позицијама друге и треће колоне. Отуда кажемо да је матрица M „сводива“ (енг. reducible), јер се да свести на строго одвојене блокове. Она је слична троугаоним матрицама (Degeneration) које се степеновањем не могу ослободити нула.

Посебно, наведена матрица (M) је ненегативан оператор, јер векторе са ненегативним коефицијентима, облика x = (0, x₂, x₃) она трансформише у ненегативне y = (0, y₂, y₃), где је y = Mx. То чини и сваки њен степен. А ако би неки степен s неке квадратне матрице P ненегативних уноса био са свим позитивним коефицијентима, онда би матрица била „несводива“ (енг. irreducible). Дати степен (s) дао би позитиван оператор, матрицу.

Усмерени граф се назива јако повезаним ако је свако теме доступно из сваког другог темена. Када посматрамо P = (p_ij) као матрицу која припада усмереном графу, где кажемо да се чвор i усмерава према j ако и само ако је p_ij ≠ 0. Таква дефиниција потврђује да је сам граф снажно повезан. Такав се не може разбијати на мање јако повезане блокове и зато се назива несводљивим.

Следећа матрица несводива је (N^s → N', када s → ∞):

\[ N^s = \begin{pmatrix} 0.8 & 0.1 & 0 \\ 0.1 & 0.7 & 0.4 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}^s \to \begin{pmatrix} 0.235 & 0.235 & 0.235 \\ 0.471 & 0.471 & 0.471 \\ 0.294 & 0.294 & 0.294 \end{pmatrix} = N', \]

јер она већ од другог степена (s ≥ 2) нема нула-коефицијената. Када од ње формирамо граф, попут оног на слици горе десно, добијамо следећи.

То је повезани граф. Стрелицама се, повезницама чворова 1, 2 и 3, од све и једног чвора може стићи до сваког чвора. Понављам, тај се не може разбијати на мање јако повезане блокове и називамо га несводљивим.

На пример, када бисмо друштво раздвојили на скупове сиромаха, средњу класу и богате и хтели да први не могу допрети до осталих, користили бисмо методу графа M са веома поузданим знањима алгебре и при томе згодно несхватљивим многима, да бисмо третирали такве. Али, ако бисмо свим учесницима хтели дати неку шансу, користићемо методе графа N и одговарајућа математичка знања.

Koмпјутери ће изненађујуће лако излазити на крај са прилично великим матрицама реда n ∈ ℕ. Оно што је кориснику потребно је разумевање ове методе, а у програмском језику Python (pip install quantecon) код је:

import numpy as np
import quantecon as qe
M = np.array([[0.8, 0.0, 0.0],
              [0.2, 0.7, 0.4],
              [0.0, 0.3, 0.6]])
N = np.array([[0.8, 0.1, 0.0],
              [0.1, 0.7, 0.4],
              [0.1, 0.2, 0.6]])
print('\nMatrica M:')
print(M)
M = M.transpose()
mc = qe.MarkovChain(M, ('1', '2', '3'))
print('M:', mc.is_irreducible)
print('\nMatrica N:')
print(N)
N = N.transpose()
nc = qe.MarkovChain(N, ('1', '2', '3'))
print('N:', nc.is_irreducible)

Извршење овог програма даће:

Matrica M:
[[0.8 0.  0. ]
 [0.2 0.7 0.4]
 [0.  0.3 0.6]]
M: False

Matrica N:
[[0.8 0.1 0. ]
 [0.1 0.7 0.4]
 [0.1 0.2 0.6]]
N: True

То значи да матрица M није несводљива (False), док матрица N јесте несводљива (True). Наравно, у пракси радићете са огромним бројем центара потрошача енергије, банака, тржница, заједница и којечега, међутим овај исти код (са матрицама много већег реда n) ће једнако ефикасно препознавати (не)сводљивост.

Genesis

Питање: Да ли је свака галаксија „центар“ свемира?

Одговор: Може се и тако рећи, са становишта сваке од њих. Свакој светлост касни, путујући из даље прошлости оних даљих, па свака галаксија за себе је изузетна. Она је водећа у времену, у будућности је у односу на сваку коју види.

Свемир се шири и замислимо ли га 2-дим попут површи растућег балона, галаксије као и тачке на њој „бежаће“ свака од осталих, а свака ће себе видети као центар удаљавања.

Тако на слици десно, ми смо (1) галаксија од које се удаљавају остале три (2, 3 и 4), овде једине нацртане од иначе милијарди њих. Удаљеније све мање комуницирају са централном и припада им све мањи коефицијент повезнице (0.3, 0.2 и 0.1), на уштрб већег бављења самим собом (0.7, 0.8 и 0.9), да би шема могла бити представљена стохастичком матрицом:

\[ S = \begin{pmatrix} 0.4 & 0.3 & 0.2 & 0.1 \\ 0.3 & 0.7 & 0 & 0 \\ 0.2 & 0 & 0.8 & 0 \\ 0.1 & 0 & 0 & 0.9 \end{pmatrix}. \]

Лако проверавамо да је она „несводива“ (Irreducible), а већ и њен квадрат (S²) је позитивна матрица. Такође проверимо да ће степен такве матрице конвергирати „црној кутији“ (S^t → S', када t → ∞):

\[ S' = \begin{pmatrix} 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \end{pmatrix}. \]

Да смо узели већи број галаксија, од ових n = 4, или друге коефицијенте повезница графа (a = 0.4, b = 0.3, c = 0.2 и d = 0.1), свеједно би добијена матрица „свемира“ као ланац Маркова несводљиве матрице генератора, конвергирала „црној кутији“, тада матрици свих коефицијената 1/n, док год су a, b, c, ... > 0 са збиром 1. Све док постоји макар нека комуникација наведених галаксија.

Посматрамо ли овај експонент t као меру све већег периода времена од садашњости ка прошлости, онда је матрица S непосредно сада у процесу развоја галаксија свемира, а S' оно што данас видимо филтрирано дугим низом таквих трансформација и оптерећено сметњама, шумом канала. Оно што можемо видети као далеку прошлост васионе, сматрајући да је свака галаксија „центар“ свемира, је безлично униформно стање.

Дакле, опис прошлости васионе који се уклапа у теорију информације, а на начин како је ја третирам (Far Before), доследан је и алгебри процеса. Свемир овде описан релативно је себичан, себи центричан и компактан, јако је повезан. Међутим, он такав дозвољава одвојене блокове догађаја, можда описане у мојим прилозима о димензијама времена.

Јануар 2024 (English ≽)