HOMC бастаи ҳисоббарории MATLAB мебошад, ки барои таҳлили мустақими занҷирҳои Маркови тартиби баланд дар шакли тензорӣ таҳия шудааст. Дар занҷирҳои классикии Маркови тартиби якум ҳолати оянда танҳо ба ҳолати ҷорӣ вобаста аст, дар ҳоле ки дар занҷирҳои тартиби баланд ҳолати оянда ҳам ба ҳолати ҷорӣ ва ҳам ба як ё якчанд ҳолати гузашта вобаста мебошад. Аз ин рӯ, эҳтимолиятҳои гузариш ба ҷойи матритсаи дученака бо тензори бисёрченакаи гузариш ифода мешаванд. HOMC метавонад аз ин тензорҳои гузариш эҳтимолиятҳои гузариши k-қадамӣ, қиматҳои limiting probability distribution, тензорҳои ever-reaching probability ва тензорҳои mean first passage time-ро ҳисоб кунад; ҳамчунин таҳқиқи regular ё ergodic будани занҷир, гурӯҳбандии ҳолатҳо ҳамчун recurrent/transient ва сохтани матритсаи гузариши reduced first-order chain-и вобастаро дастгирӣ мекунад.

Дар маркази математикии баста амали махсуси тензорӣ бо номи box product (⊠) қарор дорад, ки дар корҳои қаблии муаллиф истифода шудааст. Ин зарб аз зарбҳои классикии тензорӣ маънои эҳтимолиятии дигар дорад ва барои тавлиди мустақими тензори гузариши k-қадамии занҷири Маркови тартиби баланд истифода мешавад. Box product дар ҳолати тартиби ду ба зарби муқаррарии матритсаҳо коҳиш меёбад, аммо дар тартиби се ва болотар associative нест. Аз ин рӯ HOMC қувваҳои тензориро на мисли дараҷабардории классикии матритса, балки бо тартиби пайдарпай ҳисоб мекунад.

Намунаҳои таҳқиқот нишон медиҳанд, ки баста танҳо бо занҷирҳои тартиби баланд маҳдуд нест ва дар ҳолати тартиби ду бо занҷирҳои классикии Маркови тартиби якум низ мувофиқ кор мекунад. Бо вуҷуди ин, таъкиди асосии муаллиф ин аст, ки ҳамаи масъалаҳои Маркови тартиби баландро бо коҳиш додан ба як занҷири вобастаи тартиби якум ҳал кардан мумкин нест. Далели асосии мавҷудияти HOMC фароҳам овардани муҳити ҳисоббарории MATLAB мебошад, ки математикаи тензории сохтори тартиби баландро мустақиман нигоҳ дошта метавонад.

Фарқи занҷири Маркови тартиби якум ва занҷири тартиби баланд чист?

Дар занҷири классикии Маркови тартиби якум ҳолати навбатии система танҳо ба ҳолати ҷорӣ вобаста аст. Вақте фазои ҳолатҳо

\[ S=\{1,2,\ldots,n\} \]

таъриф мешавад, хосияти Марков чунин аст:

\[ \Pr(X_{t+1}=i\mid X_t=j,\ldots,X_1=k) = \Pr(X_{t+1}=i\mid X_t=j) \]

чунин аст.

Эҳтимолияти гузариш:

\[ p_{ij}=\Pr(X_{t+1}=i\mid X_t=j) \]

таъриф мешавад ва ҳамаи гузаришҳоро метавон дар матритсаи стохастикии андозаи \(n\times n\), яъне \(P\), нигоҳ дошт.

Дар занҷири Маркови тартиби баланд бошад, ҳолати оянда на танҳо ба \(X_t\), балки ба якчанд ҳолати гузашта низ вобаста аст. Мувофиқи таърифи мақола, барои \(m\geq3\) занҷири тартиби \((m-1)\):

\[ \Pr( X_{t+1}=i_1 \mid X_t=i_2,\ldots,X_{t-m+2}=i_m,\ldots,X_1=i_{t+1} ) = \Pr( X_{t+1}=i_1 \mid X_t=i_2,\ldots,X_{t-m+2}=i_m ) \]

хосияти зеринро қонеъ мекунад.

Дар ин ҳолат эҳтимолияти гузариш:

\[ p_{i_1i_2\ldots i_m} = \Pr( X_{t+1}=i_1 \mid X_t=i_2,\ldots,X_{t-m+2}=i_m ) \]

мешавад ва ҳамаи эҳтимолиятҳо дар тензори гузариши тартиби \(m\), ки ҳар андозааш \(n\) аст, нигоҳ дошта мешаванд:

\[ \mathcal P=[p_{i_1i_2\ldots i_m}] \]

Ин тензор стохастикӣ аст:

\[ 0\leq p_{i_1i_2\ldots i_m}\leq1 \]

ва барои ҳар як таркиби ҳолатҳои гузашта:

\[ \sum_{i_1\in S}p_{i_1i_2\ldots i_m}=1 \]

бояд иҷро шавад.

Чаро MATLAB барои ин масъала мувофиқ аст?

Дар занҷирҳои Маркови тартиби баланд сохтори асосии додаҳо тензори бисёрченака мебошад. Сохтори табиии multidimensional array-и MATLAB барои нигоҳ доштани чунин тензорҳои гузариш бевосита мувофиқ аст.

Масалан, frontal slice-ҳои тензори гузариши тартиби \(m\):

P(:,:,i3,...,im)

ба ин шакл дастрас мешаванд. Азбаски ҳар slice матритсаи одии MATLAB бо андозаи \(n\times n\) аст, таҳқиқ ё тағйири бахшҳои гуногуни тензор бевосита бо синтаксиси MATLAB имконпазир мебошад.

Аммо шумораи унсурҳои тензори зичи тартиби \(m\) ва андозаи \(n\):

\[ n^m \]

мебошад, бинобар ин талаботи хотира босуръат афзоиш меёбад. Таҳқиқот мураккабии асосии фазоии HOMC-ро чунин медиҳад:

\[ O(n^m) \]

оварда шудааст.

Муаллиф қайд мекунад, ки барои масъалаи умумӣ ва dense higher-order Markov chain ин ногузир аст, зеро худи тензори гузариш аллакай \(n^m\) унсур дорад.

HOMC чӣ гуна кӯшиш мекунад истифодаи хотираро кам кунад?

Татбиқи соддаи ҳисобкунии box-product-и махсус метавонад сохтани пешакии ҳамаи:

\[ (i_1,i_2,\ldots,i_m) \]

таркибҳои индексҳоро талаб кунад. Қайд мешавад, ки барои қиматҳои калони \(n\) ва \(m\) ин метавонад истеъмоли зиёди хотираи иловагӣ ба вуҷуд орад.

HOMC ба ҷойи ин аз функсияи дарунсохти MATLAB ind2sub истифода бурда, индексҳои заруриро дар ҷараёни ҳисоб тавлид мекунад. Ҳамин равиш дар функсияҳои дигари баста низ дар ҷойҳои мувофиқ истифода шудааст.

Аз ин рӯ сарбории асосии хотира аз ҷадвали азими иловагии индексҳо не, балки аз худи тензори гузариш ва ҳангоми зарурат аз тензорҳои натиҷавии ҳамандоза ба вуҷуд меояд.

Чаро linear indexing зарур аст?

Ба як тартиби ягона овардани индексҳои бисёрченакаи тензор барои амалҳое чун tensor-to-matrix табдилдиҳӣ ва сохтани reduced first-order chain муҳим мебошад.

HOMC барои ин:

ind = lind(s,r)

функсияро пешниҳод мекунад.

Дар ин ҷо:

s = size(P)

вектори андозаи тензори гузариш мебошад. Ҳангоми пешфарз r=1 linear indexing-и муқаррарӣ тавлид мешавад, дар ҳоле ки:

lind(s,-1)

reversed linear indexing ҳосил мекунад.

Дар Намунаи 2.1:

s = [2 2 2 2]

барои он дар маҷмӯъ:

\[ 2^4=16 \]

таркиби индекс ба даст меояд.

Box product чист?

Амали марказии HOMC \(\boxempty\) ё дар навишти манбаъ ⊠ box product мебошад. Барои ду тензори тартиби \(m\) ва ҳамандоза:

\[ \mathcal A=[a_{i_1i_2\ldots i_m}], \qquad \mathcal B=[b_{i_1i_2\ldots i_m}] \]

тензори:

\[ \mathcal C=\mathcal A\boxtimes\mathcal B \]

унсурҳояш чунин таъриф мешаванд:

\[ c_{i_1i_2\ldots i_m} = \sum_{j=1}^{n} a_{i_1ji_2\ldots i_{m-1}} b_{ji_2\ldots i_m} \]

ба ин шакл таъриф мешавад.

Функсияи MATLAB:

C = bprod(A,B)

мебошад.

Ба таври махсус, вақте \(m=2\), тензорҳо матритса мебошанд ва box product ба зарби одии:

\[ AB \]

матритсаҳо табдил меёбад.

Чаро box product аз зарби одии матритса фарқ мекунад?

Муҳимтарин фарқ дар associative набудани он аст. Умуман барои \(m\geq3\):

\[ A\boxtimes(B\boxtimes C) \neq (A\boxtimes B)\boxtimes C \]

буданаш мумкин аст.

Аз ин рӯ, қувваҳои тензориро мисли алгебраи одӣ ба қисмҳо ҷудо кардан мумкин нест.

Масалан:

\[ A^6 \]

умуман ба шакли:

\[ A^3\boxtimes A^3 \]

ҳисоб карда намешавад.

HOMC қувваи тензориро чӣ гуна таъриф мекунад?

Қувваи тензорӣ рекурсивӣ чунин таъриф мешавад:

\[ A^{k+1}=A^k\boxtimes A \]

ба ин шакл таъриф мешавад.

Функсияи MATLAB:

C = bpow(A,k)

мебошад.

Барои қувваи сифрӣ тензори махсуси identity-и тартиби \(m\) истифода мешавад:

\[ \mathcal I=[\delta_{i_1i_2\ldots i_m}] \]

ва:

\[ \delta_{i_1i_2\ldots i_m} = \begin{cases} 1,& i_1=i_2\\ 0,& \text{aksi halde} \end{cases} \]

таъриф мешавад.

Ин тензор:

\[ I\boxtimes A=A \]

хосиятро қонеъ мекунад, аммо умуман:

\[ A\boxtimes I\neq A \]

буданаш мумкин аст.

Identity tensor бо:

I = eyet(s)

сохта мешавад.

Маънои эҳтимолиятии box product чист?

Агар тензори гузариши занҷири тартиби баланд \(\mathcal P\) бошад:

\[ \mathcal P^k = [p^{(k)}_{i_1i_2\ldots i_m}] \]

ҳар унсури ин тензор:

\[ p^{(k)}_{i_1i_2\ldots i_m} = \Pr( X_{t+k}=i_1 \mid X_t=i_2,\ldots,X_{t-m+2}=i_m ) \]

эҳтимолияти гузариши k-қадамиро ифода мекунад.

Аз ин рӯ bpow(P,k) танҳо қувваи абстрактии тензориро ҳисоб намекунад; он бевосита эҳтимолиятҳои ҳолати пас аз k қадамро истеҳсол мекунад.

Оё занҷири regular ва ergodic-и тартиби баланд як чизанд?

Не. Таҳқиқот фарқи ин ду мафҳумро бо ду намуна махсусан равшан мекунад.

Намунаи 2.2: Дар занҷири тартиби дуюми чорҳолата:

bpow(P,10)

ҳисоб карда мешавад ва дида мешавад, ки ҳамаи вурудҳои \(P^{10}\) мусбатанд. Ба ибораи дигар, барои ягон \(k\geq1\):

\[ P^k>0 \]

шарт иҷро мешавад, бинобар ин занҷир regular аст.

Манбаъ қайд мекунад, ки занҷири regular-и тартиби баланд unique limiting probability distribution дорад.

Намунаи 2.3: Дар занҷири дигари тартиби дуюми сеҳолата бошад:

\[ P^k=P \]

барои қиматҳои тоқи \(k\), ва барои қиматҳои ҷуфти \(k\) тензори дигар такрор мешавад. Аз ин рӯ, чун дар ягон қувва ҳамаи вурудҳо мусбат нестанд, занҷир regular нест.

Бо вуҷуди ин, барои ҳар як таркиби оғоз/ҳадаф \(k\)-и мувофиқ ёфтан мумкин аст, бинобар ин занҷир ergodic аст.

Ин намуна дар истилоҳоти higher-order Markov-и истифодашуда дар кори манбаъ нишон медиҳад, ки:

ergodic будан ва regular будан як шарт нестанд.

Diagonal tensor барои чӣ истифода мешавад?

Қисми diagonal-и тензор бо:

\[ A_d=[a^{(d)}_{i_1i_2\ldots i_m}] \]

нишон дода мешавад ва:

\[ a^{(d)}_{i_1i_2\ldots i_m} = \begin{cases} a_{i_1i_2\ldots i_m},&i_1=i_2\\ 0,&\text{aksi halde} \end{cases} \]

таъриф мешавад.

Функсияи HOMC:

D = diagt(A)

аст.

Ин сохтор махсусан дар муодилаҳои ever-reaching probability ва mean first passage time истифода мешавад.

Тензор чӣ гуна ба матритса табдил дода мешавад?

HOMC ҳам matricization ва ҳам tensorization-ро дастгирӣ мекунад.

Барои тензори тартиби \(m\) ва андозаи \(n\):

\[ N=n^{m-1} \]

бошад, натиҷаи mode-k matricization матритсаи \(n\times N\) мебошад.

Функсияҳо:

B = t2mat(A,k)

ва барои амали баръакс:

A = mat2t(B,k)

мебошанд.

Дар Намунаи 2.5:

A = reshape(1:16,2,2,2,2)

тензори \(2\times2\times2\times2\), ки бо он сохта шудааст, тавассути mode-3 ба матритсаи:

\[ B= \begin{bmatrix} 1&2&3&4&9&10&11&12\\ 5&6&7&8&13&14&15&16 \end{bmatrix} \]

табдил дода мешавад ва:

mat2t(B,3)

тензори аслиро бармегардонад.

Чаро занҷири тартиби баланд ба занҷири тартиби якум табдил дода мешавад?

Бо баррасии таркибҳои ҳолатҳои гузаштаи занҷири Маркови тартиби \((m-1)\) ҳамчун як ҳолати васеъшуда, метавон first-order chain-и вобастаро сохт.

Фазои нави ҳолатҳо:

\[ T= \{ i_1i_2\ldots i_{m-1}: i_1,\ldots,i_{m-1}\in S \} \]

мешавад ва андозаи он:

\[ N=n^{m-1} \]

аст.

Раванди нав:

\[ Y_t= [X_t,X_{t-1},\ldots,X_{t-m+2}]^T \]

таъриф мешавад.

Ин занҷир дар манбаъ reduced first-order chain номида мешавад.

Матритсаи гузариши reduced-chain дар MATLAB чӣ гуна сохта мешавад?

Аввал mode-1 matricization-и тензори гузариш сохта мешавад. Сипас columnwise Khatri-Rao product истифода мегардад.

HOMC барои ин ду функсия пешниҳод мекунад:

krprod(A,B)

ва барои матритсаи мустақими reduced-chain:

Q = rcmat(P)

Дар занҷири тартиби дуюми чорҳолатаи Намунаи 2.2:

\[ N=4^2=16 \]

аз ин рӯ reduced first-order transition matrix-и ҳосилшуда:

\[ Q\in\mathbb R^{16\times16} \]

андоза дорад.

Limiting probability distribution чӣ гуна ёфта мешавад?

Мувофиқи манбаъ, занҷири regular-и тартиби баланд unique limiting distribution:

\[ \pi=\lim_{t\rightarrow\infty}x_t \]

дорад.

Барои dominant eigenvalue-и матритсаи reduced-chain \(Q\):

\[ \lambda=1 \]

eigenvector-и рости мувофиқ \(y\) ёфта мешавад ва:

\[ y\geq0, \qquad \|y\|_1=1 \]

ба ин шакл нормализатсия мешавад.

Сипас бо mode-1 matricization-и identity tensor, ки дар манбаъ ҳамчун \(\mathcal P^{(0)}\) таъриф шудааст:

\[ \pi=\mathcal P^{(0)}y \]

ҳисоб карда мешавад.

Дар Намунаи 2.6 ҳангоми истифодаи функсияи eig-и MATLAB, гарчанде multiplicity-и \(\lambda=1\) баробари 2 буда, ду eigenvector-и гуногун ба даст меоянд, ҳар ду ҳамон limiting distribution-ро истеҳсол мекунанд:

\[ \pi= \begin{bmatrix} 0.2857\\ 0.2857\\ 0.2857\\ 0.1429 \end{bmatrix} \]

Ever-reaching probability чист?

Ever-reaching probability эҳтимолияти он аст, ки ҳангоми оғоз аз пайдарпаии муайяни ҳолатҳои гузашта ба ҳолати ҳадаф дар оянда ҳадди ақал як бор расида шавад.

Эҳтимолияти он ки вақти гузариши аввал маҳз дар қадами \(k\) рух диҳад, бо:

\[ f^{[k]}_{i_1i_2\ldots i_m} \]

нишон дода мешавад.

Тензори аввал:

\[ F^{[1]}=P \]

ва тензорҳои баъдӣ бо рекурсияи:

\[ F^{[k+1]} = (F^{[k]}-F^{[k]}_d)\boxtimes P \]

ҳисоб карда мешаванд.

Ever-reaching probability tensor:

\[ F=\sum_{k=1}^{\infty}F^{[k]} \]

таъриф мешавад.

Функсияи HOMC:

F = erp(P,tol)

аст.

Таҳаммули пешфарз:

\[ 10^{-6} \]

дода шудааст. Агар дар ягон \(k\) унсури бузургтарини мутлақи \(F^{[k]}\) аз таҳаммул камтар шавад, силсила дар ҳамон нуқта қатъ карда шуда, \(F\)-и тақрибӣ баргардонида мешавад.

Бо ever-reaching probability ҳолатҳо чӣ гуна гурӯҳбандӣ мешаванд?

Ҳолати \(i\), агар ҳамаи эҳтимолиятҳои diagonal ever-reaching-и лозима ба 1 баробар бошанд, ҳамчун recurrent гурӯҳбандӣ мешавад.

Агар ҳадди ақал яке аз онҳо 1 набошад, ҳолат transient аст.

Агар ҳамаи қиматҳои дахлдор аз 1 кам бошанд, ҳолат fully transient номида мешавад.

Дар Намунаи 3.1 ҳисоби erp(P,1e-8) бо истифода аз аввалин 67 аъзои силсила ҳамгаро мешавад ва натиҷа чунин гурӯҳбандӣ шудааст:

• Ҳолати 1: transient, вале fully transient нест,
• Ҳолати 2: recurrent,
• Ҳолати 3: fully transient

.

Mean first passage time чист?

Mean first passage time шумораи миёнаи қадамҳоест, ки барои бори аввал аз таркиби ибтидоии ҳолатҳои гузашта ба ҳолати ҳадаф расидан лозим аст.

Манбаъ таърифи:

\[ \mu_{i_1i_2\ldots i_m} = E(\eta_{i_1i_2\ldots i_m}) = \sum_{k=1}^{\infty} k f^{[k]}_{i_1i_2\ldots i_m} \]

ро истифода мебарад.

Ҳамаи қиматҳо дар mean first passage time tensor:

\[ \mu=[\mu_{i_1i_2\ldots i_m}] \]

нигоҳ дошта мешаванд.

Барои занҷири ergodic-и тартиби баланд:

\[ \mu= E+(\mu-\mu_d)\boxtimes P \]

муодилаи тензорӣ эътибор дорад.

HOMC mean first passage time-ро бо ду усули гуногун ҳисоб мекунад

Усули мустақим:

mu = mfptd(P)

Функсия системаи хаттиеро, ки аз муодилаи тензорӣ ба вуҷуд меояд, мустақим ҳал мекунад.

Аммо манбаъ ҳалли тамоми масъаларо ҳамчун як системаи хаттии ягонаи:

\[ n^m\times n^m \]

тавсия намедиҳад.

Вақте қиматҳои unknown бо тартиби reversed linear indexing ҷойгир карда мешаванд, матритсаи коэффисиентҳо ба \(n\) diagonal block ҷудо мешавад, бинобар ин HOMC аз ин сохтор истифода бурда системаро ба \(n\) зер масъалаи хурд тақсим мекунад.

Усули итеративӣ:

\[ \mu^{(k+1)} = E+ (\mu^{(k)}-\mu^{(k)}_d)\boxtimes P \]

итератсия истифода мешавад.

Функсияи MATLAB:

mu = mfpti(P,mu0,tol)

аст.

Оғози пешфарз:

\[ \mu^{(0)}=E \]

ва таҳаммули пешфарз:

\[ 10^{-6} \]

дода мешаванд.

Оё HOMC дар занҷирҳои тартиби якум ҳам кор мекунад?

Бале. Дар манбаъ, вақте \(m=2\), таърифи higher-order ба занҷири классикии Марков коҳиш меёбад ва мутобиқати функсияҳои HOMC бо ин ҳолат махсус санҷида шудааст.

Дар Намунаи 2.4 барои матритсаи гузариши сеҳолатаи:

\[ P= \begin{bmatrix} 0.5&0.5&0\\ 0.5&0&1\\ 0&0.5&0 \end{bmatrix} \]

натиҷаи:

bpow(P,5)

чунин ба даст омадааст:

\[ \begin{bmatrix} 0.3750&0.4688&0.3125\\ 0.4688&0.2188&0.6250\\ 0.1562&0.3125&0.0625 \end{bmatrix} \]

ва нишон дода шудааст, ки ин бо натиҷаи классикии MATLAB:

P^5

якхела аст.

Оё direct ва iterative MFPT як натиҷа медиҳанд?

Дар намунаҳои манбаъ — ҳа.

Барои занҷири ergodic-и тартиби дуюм mfptd(P):

\[ \mu(:,:,i_3)= \begin{bmatrix} 4&3&4\\ 1&2&1\\ 4&3&4 \end{bmatrix}, \qquad i_3=1,2,3 \]

натиҷаро медиҳад.

Манбаъ ҳамчунин натиҷаро бо ифодаи:

mu-ones(s)-bprod(mu-diagt(mu),P)

ба муодилаи (7) баргардонда, бо ба даст овардани тензори сифрӣ онро месанҷад.

mfpti(P) бошад, бо таҳаммули пешфарз дар 40 итератсия:

\[ 3.9999971,\quad 2.9999981,\quad 1.0000000 \]

ба қиматҳои интизоршудаи 4, 3 ва 1-и ҳалли direct наздик мешавад.

Оё намунаи MFPT барои тартиби якум ҳам ҳаст?

Бале. Дар Намунаи 3.3 барои ҳамон матритсаи классикии Марков ҳалли direct:

\[ M= \begin{bmatrix} 2.5&3&4\\ 2&2.5&1\\ 6&4&5 \end{bmatrix} \]

ба даст омадааст.

Усули iterative mfpti(P) бо таҳаммули пешфарз дар 66 итератсия тақрибан ба ин қиматҳо ҳамгаро мешавад.

Чаро HOMC танҳо ҷойгузини абзорҳои reduced first-order chain нест?

Гарчанде expanded-state first-order representation-и занҷири тартиби баландро сохтан мумкин аст, яке аз паёмҳои асосии назариявии кори манбаъ ин аст, ки ҳамаи саволҳои higher-order Markov бо чунин табдилдиҳӣ ҳал намешаванд.

Равиши reduced-chain махсусан барои масъалаҳои муайян, аз ҷумла limiting distribution, муфид мебошад. Баръакс, сохторҳои higher-order k-step transition, ever-reaching probability ва mean first passage time дар шакли тензорӣ маълумоти математикии хоси худро нигоҳ медоранд.

Аз ин рӯ HOMC ҳам:

• функсияҳои higher-order-и тензорӣ ва ҳам
• абзорҳои табдил ба first-order chain-и вобастаро ҳангоми зарурат

дар як баста пешниҳод мекунад.

Барои Тоҷикистон чӣ маъно дорад?

Кори манбаъ маҷмӯи додаҳо ё татбиқи махсуси Тоҷикистонро дар бар намегирад. Аз ин рӯ аз таҳқиқот натиҷаи махсуси модели Марков барои Тоҷикистон баровардан мумкин нест.

Бо вуҷуди ин, азбаски HOMC абзори умумимақсади математикӣ мебошад, он метавонад дар масъалаҳои таҳқиқотие истифода шавад, ки рафтори гузариш на танҳо ба ҳолати охирин, балки ба гузаштаи дарозтар низ вобаста аст. Дар адабиёти татбиқие, ки мақолаи манбаъ ба он истинод мекунад, соҳаҳое чун нархҳои энергия, пешгӯии истеҳсоли фотоэлектрикӣ, пешгӯии ишғоли бино, силсилаҳои вақт, пайгирии ҳадаф ва sequential recommendation ҳамчун самтҳои истифодаи Маркови тартиби баланд оварда шудаанд. Инҳо дар мақолаи HOMC ҳамчун таҷрибаҳои нави татбиқӣ санҷида нашуда, танҳо ҳамчун намунаҳои соҳаҳои мавҷудаи истифодаи занҷирҳои higher-order Markov истинод шудаанд.

Натиҷаҳое, ки таҳқиқот дастгирӣ мекунад

• HOMC барои higher-order Markov chains функсияҳои тензории ҳисоббарории MATLAB пешниҳод мекунад.
• Тензорҳои гузариш метавонанд мустақиман ҳамчун MATLAB multidimensional array ифода шаванд.
• bprod амали махсуси box-product-ро иҷро мекунад.
• bpow тензори гузариши k-қадамиро ҳисоб мекунад.
• Box product барои \(m\geq3\) умуман associative нест.
• eyet сохтори махсуси identity tensor-и мақоларо месозад.
• diagt diagonal tensor-ро ҷудо мекунад.
• t2mat ва mat2t matricization/tensorization-ро таъмин мекунанд.
• rcmat метавонад матритсаи гузариши reduced first-order chain-ро созад.
• Бо reduced-chain функсияи MATLAB eig метавонад дар ҳисоби limiting distribution истифода шавад.
• erp ҳисоби ever-reaching probability tensor-ро дастгирӣ мекунад.
• Қиматҳои diagonal-и ever-reaching probability метавонанд барои гурӯҳбандии ҳолатҳои recurrent ва transient истифода шаванд.
• mfptd муодилаи mean first passage time-ро бо истифода аз сохтори блокӣ мустақим ҳал мекунад.
• mfpti ҳамин масъаларо ба таври итеративӣ ҳал карда метавонад.
• Баста дар ҳолати махсуси \(m=2\) бо занҷирҳои классикии first-order Markov низ кор мекунад.

Натиҷаҳое, ки таҳқиқот дастгирӣ намекунад ё нишон намедиҳад

• Нишон дода нашудааст, ки HOMC аз ҳамаи нармафзорҳои эҳтимолии higher-order Markov тезтар аст.
• Мақола барои қиматҳои гуногуни \(n\) ва \(m\) runtime benchmark-и систематикӣ пешниҳод намекунад.
• Баста миқёси хотираи \(O(n^m)\)-ро барои тензорҳои зич аз байн намебарад.
• Таҳқиқот барои тензорҳои sparse ё хеле калон усули ҷудогонаи миқёспазириро тасдиқ намекунад.
• Ибораи муаллиф “first dedicated MATLAB package” даъвои навовариест, ки ба арзёбии адабиёти таҳқиқот такя мекунад; мақола таҳқиқоти мустақили инвентаризатсияи нармафзор нест.
• Муваффақияти намунаҳои математикӣ маънои бартарии худкори пешгӯиро дар маҷмӯи додаҳои муайяни ҷаҳони воқеӣ надорад.
• Имкони табдил додани higher-order chain ба reduced first-order chain маънои онро надорад, ки ҳамаи масъалаҳои higher-order танҳо бо нармафзори first-order ҳал мешаванд.
• Дар версияи 2025-и манбаъ функсияи fund, ки баъдтар илова шудааст, ё хусусиятҳои absorbing-chain fundamental tensor вуҷуд надоранд.

Усул ва натиҷаҳои таҳқиқот

Функсияҳои асосии HOMC, ки дар манбаъ муайян шудаанд

Ҳадафи илмии намунаҳо

Намунаи 2.2: натиҷаи regularity

Тензори гузариши занҷири тартиби дуюми чорҳолата бо чор frontal slice-и \(4\times4\) таъриф мешавад.

Дар натиҷаи bpow(P,10) манбаъ ҳамаи вурудҳои чор матритсаи ҷудогонаи \(P^{10}(:,:,i_3)\)-ро мусбат медиҳад.

Аз ин рӯ:

\[ P^{10}>0 \]

ва занҷир ҳамчун regular гурӯҳбандӣ мешавад.

Намунаи 2.3: занҷири ergodic, вале regular набуда

Дар занҷири тартиби дуюми сеҳолата қувваи тензорӣ рафтори даврӣ нишон медиҳад:

• \(k\)-и тоқ: \(P^k=P\),
• \(k\)-и ҷуфт: тензори дуюми собит.

Аз ин рӯ қуввае вуҷуд надорад, ки дар ҳамон \(k\) ҳамаи вурудҳо мусбат бошанд.

Бо вуҷуди ин, азбаски барои ҳар таркиби ҳолат ҳадди ақал як k-қадами дастрас мавҷуд аст, занҷир мувофиқи таърифи манбаъ ergodic мебошад.

Намунаи 2.6: limiting distribution

Шумораи reduced-state-и занҷири тартиби дуюми чорҳолата:

\[ 4^2=16 \]

мебошад, бинобар ин:

\[ Q\in\mathbb R^{16\times16} \]

матритсаи гузариш ба даст меояд.

Ду eigenvector-и гуногуни \(\lambda=1\), ки бо MATLAB eig ёфта шудаанд, ҳамон:

\[ \pi= [0.2857,\ 0.2857,\ 0.2857,\ 0.1429]^T \]

limiting distribution-ро истеҳсол мекунанд.

Намунаи 3.1: ҳамгароии ever-reaching probability

Намунаи 3.2: higher-order mean first passage time

Намунаи 3.3: first-order mean first passage time

Барои занҷири first-order-и сеҳолата ҳалли direct:

\[ M= \begin{bmatrix} 2.5&3&4\\ 2&2.5&1\\ 6&4&5 \end{bmatrix} \]

ба даст омадааст.

Усули iterative бо таҳаммули пешфарз дар 66 итератсия ба ин матритса наздик мешавад.

Манбаъ дар бораи миқёспазирии ҳисоббарорӣ чӣ мегӯяд?

Мақола барои вақти иҷро benchmark-и систематикӣ намедиҳад. Аммо маҳдудияти асосии хотираро ба таври возеҳ нишон медиҳад:

\[ O(n^m) \]

Сабаб дар он аст, ки тензори гузариши general dense higher-order Markov chain худ аллакай \(n^m\) қимати эҳтимолият дорад.

Аз ин рӯ, масалан, зиёд кардани шумораи ҳолатҳо ё тартиб метавонад андозаи масъаларо на хаттӣ, балки экспоненсиалӣ зиёд кунад.

Ин ҷадвал робитаҳои андозагирии формулаҳои худи мақоларо ҷамъбаст мекунад; он benchmark-и нави иҷро нест.

Саҳми асосии таҳқиқот

Саҳми HOMC на як модели нави умумимақсади Марков, балки табдил додани натиҷаҳои тензории таҳиякардаи муаллиф ва ҳамкоронаш оид ба higher-order Markov chains ба функсияҳои бевосита истифодашавандаи MATLAB мебошад.

Ин баста махсусан барои:

• таҷрибаи ададӣ,
• прототипсозии алгоритм,
• таҳқиқоти higher-order transition tensor,
• state classification,
• limiting distribution,
• ever-reaching probability,
• mean first passage time

фароҳам овардани зерсохтори ягонаи ҳисоббарориро ҳадаф дорад.

Маҳдудиятҳои асосӣ

• Миқёси \(n^m\)-и тензори зич маҳдудияти асосии хотира дар масъалаҳои калон аст.
• Манбаъ benchmark-и систематикии суръати CPU/GPU пешниҳод намекунад.
• GPU, parallel computing ё sparse-tensor optimization мавзӯи мақола нест.
• Намунаҳо занҷирҳои математикӣ/синтетикӣ мебошанд; таҳлили нави додаҳои саҳроии соҳаҳои татбиқӣ пешниҳод нашудааст.
• Box product аз tensor product-ҳои классикӣ фарқ мекунад; онро набояд бо амалҳои дигар tensor toolbox баробар донист.
• Аз сабаби non-associativity баъзе интуитсияҳои тезондани ҳисоб, ки дар алгебраи матритса истифода мешаванд, барои ҳисоби қувваҳо мустақиман татбиқ намешаванд.
• Reduced first-order chain муфид аст, аммо наметавонад ҳамаи масъалаҳои higher-order-ро иваз кунад.

Ёддошт оид ба манбаъ ва усул

Номи пурраи аслии кор: HOMC: A MATLAB Package for Higher Order Markov Chains

Муаллиф: Jianhong Xu.

Муаллифи масъул: Jianhong Xu.

Ҳаммуаллифи аввал/саҳми баробар: Азбаски кор якмуаллифӣ аст, изҳороти саҳми баробар вуҷуд надорад.

Муассиса: School of Mathematical and Statistical Sciences, Southern Illinois University Carbondale, Carbondale, Illinois, USA.

Навъи манбаъ: Таҳқиқоти нармафзори илмии математикӣ ва усули ададии асосёфта ба MATLAB.

Версияи боршуда: arXiv:2510.02664v1 [stat.CO].

Санаи аввалини ирсол ба ArXiv: 3 октябри 2025.

Санаи навишташуда дар PDF: 6 октябри 2025.

ArXiv DOI: 10.48550/arXiv.2510.02664.

Вазъи нашри версияи боршуда: PDF-и arXiv-и боршуда версияи preprint мебошад.

Вазъи ҷории нашр: Дар санҷиши библиографӣ саҳифаи расмии таҳқиқоти Southern Illinois University ва файли расмии README-и HOMC корро дар ACM Transactions on Mathematical Software ҳамчун “to appear” номбар мекунанд.

DOI-и ҷории маҷалла: 10.1145/3834564.

Версияи истифодашуда дар мундариҷаи илмӣ: Таърифҳо, функсияҳо, муодилаҳо, намунаҳо ва натиҷаҳои ададии ин мақолаи Verianla ба версияи боршудаи arXiv v1 асос меёбанд. Навсозиҳои баъдии нармафзор ё мақола ба мундариҷаи асосии илмӣ ба таври бозгаштӣ илова нашудаанд.

Коди манбаъ: Таҳқиқоти боршуда қайд мекунад, ки файлҳои манбаи MATLAB-и HOMC дар директорияи neumann.math.siu.edu/homc дар сервери Southern Illinois University барои умум дастрасанд.

Фарқи нармафзори ҷорӣ: Файли расмии README-и HOMC қайд мекунад, ки моҳи июни 2026 барои higher-order absorbing Markov chains функсияи нави fund илова шудааст. Азбаски ин функсия дар маҷмӯи функсияҳои мақолаи боршудаи соли 2025 вуҷуд надошт, он ба рӯйхати хусусиятҳои илмии ин мақола дохил карда нашудааст.

Функсияҳои асосии дар манбаъ тавсифшуда:lind, bprod, bpow, eyet, diagt, t2mat, mat2t, krprod, rcmat, erp, mfptd ва mfpti.

Функсияҳои built-in-и MATLAB: Манбаъ махсусан аз абзорҳои MATLAB чун size, ones, eig, ind2sub, fliplr ва reshape истифода мебарад.

Сохтори асосии математикӣ: Тензорҳои гузариши тартиби m, box product-и махсус, қувваҳои тензорӣ, mode-k matricization, Khatri-Rao product, reduced first-order chain, ever-reaching probability ва тензорҳои mean first passage time.

Мураккабии хотира: Манбаъ хароҷоти асосии нигоҳдориро барои ҳисобҳои general dense higher-order Markov chain ҳамчун \(O(n^m)\) медиҳад.

Runtime benchmark: Таҳқиқот benchmark-и систематикии вақти иҷро ё иҷроиш дар сахтафзорҳои гуногунро гузориш намедиҳад.

Ҳудуди ибораи “бастаи аввал”: Муаллиф корро мувофиқи арзёбии адабиёти худ ҳамчун first dedicated MATLAB package барои higher-order Markov chains муайян мекунад. Ин изҳорот натиҷаи таҳқиқоти мустақили ҳамаҷонибаи инвентаризатсияи нармафзор нест.

Ҳудуди татбиқ: Дар мақола бо истинодҳо қайд мешавад, ки higher-order Markov chains дар соҳаҳое чун rating transitions, occupancy prediction, силсилаҳои вақт, PageRank, target tracking, пешгӯии истеҳсоли PV, electricity price dynamics ва sequential recommendation истифода мешаванд. Худи мақолаи HOMC дар ин соҳаҳо маҷмӯи додаҳои нави татбиқӣ ё таҷрибаи муқоисавӣ пешниҳод намекунад.

Барқхӯрди манфиатҳо: Дар матни боршудаи arXiv v1 изҳороти ҷудогонаи competing-interest вуҷуд надорад; аз ин набудани бархӯрди манфиатҳо хулоса карда нашудааст.

Маблағгузорӣ: Дар матни боршудаи arXiv v1 бахши ҷудогонаи funding acknowledgement вуҷуд надорад.

CRediT/саҳми муаллиф: Кор якмуаллифӣ буда, изҳороти ҷудогонаи CRediT contribution statement надорад.

Ҳудуди тафсири илмӣ: Таҳқиқот бастаи математикӣ ва ҳисоббарории MATLAB-ро барои higher-order Markov chains пешниҳод мекунад. Намунаҳо хусусияти тасдиқи усул ва намоиши истифода доранд; онҳо дар масъалаи муайяни ҷаҳони воқеӣ бартарии пешгӯӣ ё иҷроиши саҳроиро исбот намекунанд.

Ҳудуди мундариҷаи илмӣ: Таърифҳои higher-order Markov, box product, қувваҳои тензорӣ, намунаҳои regularity/ergodicity, табдили reduced-chain, limiting distribution, ever-reaching probability, state classification ва натиҷаҳои mean first passage time дар ин матни Verianla танҳо ба таҳқиқоти боршуда асос меёбанд. Манбаъҳои беруна танҳо барои тасдиқи вазъи библиографии нашр ва вазъи ҷории расмии бастаи HOMC истифода шудаанд.