Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей
Запропоновано новий метод дослiдження асимптотичної поведiнки моментiв лiнiйних випадкових рекурсивних послiдовностей, який базується на технiцi iтеративних функцiй. За допомогою цього методу показано, що моменти числа зiткнень та моменти часу поглинання в коалесцентi Пуассона–Дiрiхле асимптотично з...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/37262 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей / О.В. Маринич // Доп. НАН України. — 2011. — № 3. — С. 23-27. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859778911030738944 |
|---|---|
| author | Маринич, О.В. |
| author_facet | Маринич, О.В. |
| citation_txt | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей / О.В. Маринич // Доп. НАН України. — 2011. — № 3. — С. 23-27. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Запропоновано новий метод дослiдження асимптотичної поведiнки моментiв лiнiйних випадкових рекурсивних послiдовностей, який базується на технiцi iтеративних функцiй. За допомогою цього методу показано, що моменти числа зiткнень та моменти часу поглинання в коалесцентi Пуассона–Дiрiхле асимптотично зростають як степенi функцiї ln*(·), яка зростає повiльнiше за будь-яку iтерацiю логарифму, та доведено слабкi закони великих чисел для вказаних функцiоналiв.
We propose a new method of analyzing the asymptotics of moments of certain random recurrences which is based on the technique of iterative functions. By using the method, we show that the moments of the number of collisions and the absorption time in the Poisson–Dirichlet coalescent behave like powers of the ln*(·) function which grows slower than any iteration of the logarithm, and thereby prove the weak laws of large numbers.
|
| first_indexed | 2025-12-02T09:15:28Z |
| format | Article |
| fulltext |
УДК 519.214.6
© 2011
О.В. Маринич
Про асимптотичну поведiнку моментiв випадкових
рекурсивних послiдовностей
(Представлено членом-кореспондентом НАН України М. I. Портенком)
Запропоновано новий метод дослiдження асимптотичної поведiнки моментiв лiнiйних
випадкових рекурсивних послiдовностей, який базується на технiцi iтеративних функ-
цiй. За допомогою цього методу показано, що моменти числа зiткнень та моменти
часу поглинання в коалесцентi Пуассона–Дiрiхле асимптотично зростають як степе-
нi функцiї ln∗(·), яка зростає повiльнiше за будь-яку iтерацiю логарифму, та доведено
слабкi закони великих чисел для вказаних функцiоналiв.
Лiнiйною випадковою рекурсивною послiдовнiстю називається послiдовнiсть випадкових ве-
личин {Xn, n ∈ N}, маргiнальнi розподiли якої задовольняють рiвнiсть розподiлiв
X1 = a > 0, Xn
d
= Vn +
K∑
r=1
Ar(n)X
(r)
In
(r)
, n > 2. (1)
У цiй рiвностi розподiлiв K > 1 — фiксоване натуральне число, випадковi величини (iн-
декси) In(r) набувають значень з множини {1, . . . , n}, для кожного r = 1, . . . ,K послiдов-
нiсть {X
(r)
k , k ∈ N} є незалежною копiєю {Xk, k ∈ N}, Vn > 0 — випадковий неодно-
рiдний член, Ar(n) > 0 — випадковi ваговi множники. Припускається, що послiдовностi
{(In(1), . . . , I
n
(K), A1(n), . . . , AK(n), Vn), n ∈ N} та {X(1)
n , n ∈ N}, . . . , {X(K)
n , n ∈ N} є незале-
жними.
Першим кроком у дослiдженнi асимптотичної поведiнки випадкової рекурсивної послi-
довностi (1) є знаходження асимптотичної поведiнки моментiв EXk
n та центральних момен-
тiв E(Xn − EXn)
k при n → ∞. Ця задача зводиться до вивчення звичайного рекурентного
спiввiдношення вигляду
a1 = â, an = bn +
n−1∑
k=1
cnkak, n > 2, (2)
де {bn, n ∈ N} та {cnk, n > 2, k < n} є заданими числовими послiдовностями.
Асимптотичний аналiз рекурсiї (2) є складною аналiтичною задачею, проте iснують
деякi загальнi методи. Найпопулярнiшими є: метод сингулярного аналiзу твiрних функ-
цiй [1, 2], репертуарний метод [3] та метод, який базується на гармонiчному аналiзi та
теорiї потенцiалу [4].
Метод, описаний в данiй роботi, спочатку був запропонований для розв’язку задачi про
моменти числа зiткнень Xn та часу поглинання Tn у коалесцентi Пуассона–Дiрiхле. Ця за-
дача була поставлена на початку 2008 р. M. Möhle. Використовуючи запропонований метод,
ми доведемо, що послiдовностi EXk
n та ET k
n асимптотично еквiвалентнi степеням функцiї
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №3 23
“лог-зiрочка”, яка зростає повiльнiше за будь-яку iтерацiю логарифма. Така екзотична по-
ведiнка моментiв частково пояснює, чому для розв’язку цiєї задачi застосування вiдомих
методiв не дало результатiв. Докладна iнформацiя про коалесцент Пуассона–Дiрiхле ви-
кладена в роботi [5].
Доведення основних результатiв не наводиться, їх можна знайти в [6].
У роботi використано такi позначення: g◦(0)(x) := x, g◦(k)(x) := g(g◦(k−1)(x)), k > 1;
f(x) ∼ g(x) при x → x0 означає f(x)/g(x) → 1 при x → x0.
1. Iтеративнi функцiї.
Означення 1. Нехай g : R+ → R
+ є зростаючою необмеженою неперервною функцiєю,
яка задовольняє умову:
(А) Для деякого x0 > 0 та довiльного x1 > x0 iснує εx1 > 0 таке, що x − g(x) > εx1
для всiх x ∈ (x0, x1).
Припустимо, що функцiї h : R+ → R
+ та k : [0, x0] → R є неперервними на областi
задання. Визначимо функцiю g∗ : R+ → R таким чином:
g∗(x) =
m0(x)∑
i=1
h(g◦(i−1)(x)) + k(g◦(m0(x))(x)), (3)
де m0(x) := inf{k > 0: g◦(k)(x) 6 x0}. Функцiя g∗ називається iтеративною функцiєю,
породженою четвiркою (h, g, x0, k), та позначається g∗ = Iter(h, g, x0, k).
Зауваження 1. З означення випливає, що g∗ задовольняє функцiональне рiвняння
g∗(x) = h(x) + g∗(g(x)), x > x0, (4)
з початковою умовою g∗(x) = k(x), x 6 x0.
П р и к л ад 1 . Нехай h(x) ≡ 1, g(x) = lnx, x0 = 1, k(x) ≡ 0. Тодi g∗(x) = 1 + g∗(ln x), x > 1, або
g∗(x) = ln∗ x (“лог-зiрочка”) — найвiдомiша нетривiальна iтеративна функцiя.
Введемо вiдношення еквiвалентностi ≈ на множинi iтеративних функцiй за правилом
g∗1 ≈ g∗2 ⇐⇒ g∗1 = Iter(h, g, x0, k1), g∗2 = Iter(h, g, x0, k2).
Це вiдношення породжує розбиття множини iтеративних функцiй на класи еквiвалентностi.
Означення 2. Клас еквiвалентностi F := {F = Iter(h, g, x0, k), k ∈ C[0, x0]} називаєть-
ся iтеративною функцiєю, породженою трiйкою (h, g, x0). Якщо це не викликатиме не-
однозначностi, ми називатимемо iтеративною функцiєю, породженою трiйкою (h, g, x0),
довiльний елемент класу.
Оскiльки |g∗1(x)−g∗2(x)| є обмеженою величиною на R
+ для довiльних функцiй g∗1 , g
∗
2 ∈ F ,
то всi функцiї з одного класу еквiвалентностi є асимптотично еквiвалентними (якщо вони
розбiгаються до +∞).
Означення 3. m-раз диференцiйовною модифiкацiєю iтеративної функцiї g∗ називаєть-
ся довiльна iтеративна функцiя ĝ∗ така, що ĝ∗ ≈ g∗ та ĝ∗ ∈ C(m)[x0,+∞).
З наведеного вище випливає, що за рахунок вибору k(·) функцiю Iter(h, g, x0, k) можна
зробити достатньо гладкою. Формальний результат наведено нижче. Для набору функцiй
f1, . . . , fn позначимо W (f1, . . . , fn) їх визначник Вронського.
Теорема 1. Нехай g, h ∈ C(m)[x0,+∞) та
W (xi − gi(x), i = 0, . . . ,m+ 1)(x0) 6= 0.
24 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №3
Тодi iснує функцiя k вигляду k(x) =
m+1∑
i=1
αix
i така, що iтеративна функцiя породжена
четвiркою (h, g, x0, k), є m-раз диференцiйовною на [x0,+∞).
2. Асимптотична поведiнка рекурсiї (2). При дослiдженнi рекурсiї (2), не зменшу-
ючи загальностi, можна вважати, що для довiльного n > 2
n−1∑
k=1
cnk = 1 та cnk > 0, k = 1, . . . , n− 1 (5)
(див., напр., [4, c. 9]). В подальшому ми називатимемо рекурсiю (2), яка задовольняє (5),
рекурсiєю, зведеною до ймовiрностей. Якщо (5) виконується, позначимо через In випадкову
величину з розподiлом
P{In = k} = cnk, k = 1, . . . , n− 1.
Теорема 2. Припустимо, що {an, n ∈ N} та {a′n, n ∈ N} задовольняють рекурсiї,
зведенi до ймовiрностей
an = bn +
n−1∑
k=1
pnkak, n > N, a′n = b′n +
n−1∑
k=1
pnka
′
k, n > N,
вiдповiдно. Припустимо, що bn > 0 для n > N та lim
n→∞
an = +∞. Тодi:
1) з b′n ∼ bn, n → ∞ випливає a′n ∼ an, n → ∞;
2) з b′n = o(bn), n → ∞ випливає a′n = o(an), n → ∞.
Теорема 3. Припустимо, що послiдовнiсть {an, n ∈ N} задовольняє рекурсiю (2), зведе-
ну до ймовiрностей. Нехай g : R+ → R
+ — неперервна зростаюча та необмежена функцiя
така, що g(n) = EIn + o(EIn), n → ∞, та h : R+ → R
+ — неперервна функцiя така, що
h(n) = bn, n > 2. Якщо
а) lim
n→∞
an = +∞,
б) g∗(EIn) − g∗(g(n)) = o(h(n)), n → ∞,
де g∗ — iтеративна функцiя, породжена трiйкою (h, g, x0) (з пiдхожим x0), то мають
мiсце такi iмплiкацiї:
Eg∗(In)− g∗(EIn) = o(h(n)), n → ∞ =⇒ an ∼ g∗(n), n → ∞, (6)
Eg∗(In)− g∗(EIn) ∼ dh(n), n → ∞, для деякого d < 1 =⇒
=⇒ an ∼ (1− d)−1g∗(n), n → ∞. (7)
Нижченаведена теорема описує асимптотичну поведiнку (2) за деяких припущень на
моменти iндексу In.
Теорема 4. Припустимо, що {an, n ∈ N} задовольняє рекурсiю (2), зведену до ймовiр-
ностей. Нехай g : R+ → R
+ є двiчi диференцiйовною, зростаючою та необмеженою функ-
цiєю такою, що g(n) = EIn + o(EIn), n → ∞, та h : R+ → R
+ є двiчi диференцiйовною
функцiєю такою, що h(n) = bn, n > 2. Якщо виконуються умови:
(C1) lim
n→∞
an = +∞;
(C2) iснує неперервна функцiя k така, що iтеративна функцiя F , породжена четвiр-
кою (h, g, x0, k), є двiчi диференцiйовною;
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №3 25
(C3) F (EIn) − F (g(n)) = o(h(n)), n → ∞;
(C4) iснує M > 0 таке, що для всiх n ∈ N DIn 6 MEIn;
(C5) lim
n→∞
sup
x>EIn/2
|F ′′(x)|
Var In
h(n)
= 0;
(C6) lim
n→∞
sup
16x6n
|F (x)|
h(n)Var In
= 0;
(C7) lim
n→∞
F ′(EIn)
h(n)
= 0,
то an ∼ F (n), n → ∞.
Зауваження 2. Функцiя g в умовах теорем 3, 4 визначається неоднозначно та може бути
обрана так, що умова (С3) завжди виконується.
3. Коалесцент Пуассона–Дiрiхле. Нехай Xn — число зiткнень у звуженому коалес-
центi Пуассона–Дiрiхле з параметром θ > 0, доки не залишиться єдиний блок. Послiдов-
нiсть Xn задовольняє випадкову лiнiйну рекурсiю
X1 = 0, Xn
d
= 1 +X ′
Jn , n > 2, (8)
де Jn має розподiл
P{Jn = k} =
θk
[θ]n − θn
s(n, k), k ∈ {1, 2, . . . , n− 1}, (9)
де {X ′
n : n > 1} — незалежна копiя {Xn : n > 1}, а s(n, k) — абсолютнi (беззнаковi) числа
Стiрлiнга першого роду.
Час поглинання Tn у коалесцентi Пуассона–Дiрiхле задовольняє випадкову лiнiйну ре-
курсiю
T1 = 0, Tn
d
= Vn + T ′
Jn , n > 2, (10)
де Vn має показниковий розподiл з параметром 1− θn/[θ]n i не залежить вiд {T ′
n : n > 1} —
незалежної копiї {Tn : n > 1}.
Моменти випадкових величин Xn або Tn мають таку асимптотичну поведiнку:
Теорема 5. При n → ∞ для довiльного k ∈ N
EY k
n
(ln∗θ(n))
k
→ 1,
де Yn — будь-яка з випадкових величин Xn та Tn, а функцiя x 7→ ln∗θ(x) визначається
функцiональним рiвнянням ln∗θ(x) = (1 + ln∗θ(θ lnx))1{x>e2θ∨1}. Функцiя ln∗θ(x) монотонно
зростає, є необмеженою та росте повiльнiше за будь-яку iтерацiю логарифма.
З теореми 5 та нерiвностi Чебишова випливає слабкий закон великих чисел.
Наслiдок 1. При n → ∞
Xn
ln∗θ(n)
P
→ 1 та
Tn
ln∗θ(n)
P
→ 1.
Схема доведення теореми 5. З формули (9) випливає, що
EJn = θ lnn+O(1), DJn = θ lnn+O(1).
Покладемо g(x) := θ lnx, h(x) := 1 та g∗(x) = Iter(h, g, x0) для деякого фiксованого x0 >
> exp(2θ∨1). Такий вибiр числа x0 гарантує виконання умови (А). Функцiя g∗ задовольняє
26 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №3
функцiональне рiвняння g∗(x) = 1 + g∗(θ lnx), x > x0. Нехай F — це двiчi диференцiйовна
модифiкацiя функцiї g∗ вигляду
F (x) =
{
1 + F (θ lnx), x > x0,
α1x
3 + α2x
2 + α3x, x ∈ [0, x0],
для деяких α1, α2, α3. З цього випливає, що для довiльного j ∈ N
F ′(x) = o
(
1
x lnx · · · ln◦(j)(x)
)
та F ′′(x) = o
(
1
x2(lnx)2 · · · (ln◦(j)(x))2
)
при x → ∞. Застосовуючи теорему 4, отримуємо EXn ∼ g∗(n) ∼ F (n).
За iндукцiєю легко показати, що для k > 2 послiдовнiсть EXk
n задовольняє рекурсiю
EXk
n = en(k) +
n−1∑
i=1
P{Jn = k}EXk
i , n > 2,
де en(k) = k(g∗(n))k−1 + o(k(g∗(n))k−1). Тому твердження теореми для моментiв порядку
k > 2 випливає з теореми 2. Оскiльки g∗(x) ∼ ln∗ x при x → ∞, твердження теореми
доведено для послiдовностi Xn.
Доведення теореми для послiдовностi {Tn, n ∈ N} випливає з того факту, що послiдов-
нiсть ET k
n задовольняє рекурсiю
ET k
n = e′n(k) +
n−1∑
i=1
P{Jn = k}ET k
i , n > 2,
де e′n(k) = kEVnET
k−1
n + o(EVnET
k−1
n ). Можна показати, що e′n(k) ∼ en(k), а тому ET k
n ∼
∼ EXk
n ∼ (g∗(n))k за теоремою 2. Теорема доведена повнiстю.
1. Drmota M. Random trees: An interplay between combinatorics and probability. – New York: Springer,
2009. – 457 p.
2. Flajolet P., Sedgewick R. Analytic combinatorics. – Cambridge: Cambridge University Press, 2008. – 824 p.
3. Greene D.H., Knuth D.E. Mathematics for the analysis of algorithms. – Boston: Birkhäuser, 1990. – 132 p.
4. Rösler U. On the analysis of stochastic divide and conquer algorithms // Algorithmica. – 2001. – 29. –
P. 238–261.
5. Möhle M. Asymptotic results for coalescent processes without proper frequencies and applications to the
two-parameter Poisson-Dirichlet coalescent // Stoch. Process. Appl. – 2010. – 120. – P. 2159–2173.
6. Marynych A. On the asymptotics of moments of linear random recurrences // Theory Stoch. Proc. – 2010. –
16(32). – P. 106–119.
Надiйшло до редакцiї 03.09.2010Київський нацiональний унiверситет
iм. Тараса Шевченка
O.V. Marynych
Asymptotic behavior of moments of random recursive sequences
We propose a new method of analyzing the asymptotics of moments of certain random recurrences
which is based on the technique of iterative functions. By using the method, we show that the
moments of the number of collisions and the absorption time in the Poisson–Dirichlet coalescent
behave like powers of the ln∗(·) function which grows slower than any iteration of the logarithm,
and thereby prove the weak laws of large numbers.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №3 27
|
| id | nasplib_isofts_kiev_ua-123456789-37262 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-02T09:15:28Z |
| publishDate | 2011 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Маринич, О.В. 2012-09-30T19:57:46Z 2012-09-30T19:57:46Z 2011 Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей / О.В. Маринич // Доп. НАН України. — 2011. — № 3. — С. 23-27. — Бібліогр.: 6 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/37262 519.214.6 Запропоновано новий метод дослiдження асимптотичної поведiнки моментiв лiнiйних випадкових рекурсивних послiдовностей, який базується на технiцi iтеративних функцiй. За допомогою цього методу показано, що моменти числа зiткнень та моменти часу поглинання в коалесцентi Пуассона–Дiрiхле асимптотично зростають як степенi функцiї ln*(·), яка зростає повiльнiше за будь-яку iтерацiю логарифму, та доведено слабкi закони великих чисел для вказаних функцiоналiв. We propose a new method of analyzing the asymptotics of moments of certain random recurrences which is based on the technique of iterative functions. By using the method, we show that the moments of the number of collisions and the absorption time in the Poisson–Dirichlet coalescent behave like powers of the ln*(·) function which grows slower than any iteration of the logarithm, and thereby prove the weak laws of large numbers. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей Asymptotic behavior of moments of random recursive sequences Article published earlier |
| spellingShingle | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей Маринич, О.В. Математика |
| title | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| title_alt | Asymptotic behavior of moments of random recursive sequences |
| title_full | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| title_fullStr | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| title_full_unstemmed | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| title_short | Про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| title_sort | про асимптотичну поведінку моментів випадкових рекурсивних послідовностей |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/37262 |
| work_keys_str_mv | AT mariničov proasimptotičnupovedínkumomentívvipadkovihrekursivnihposlídovnostei AT mariničov asymptoticbehaviorofmomentsofrandomrecursivesequences |