Luận văn Một số định lý giới hạn cho bước đi ngẫu nhiên có trí nhớ

Xn}. 21 22 Vị tríXn theo thời gian thông qua luật ngẫu nhiên sau. Ở bước n nếu vị trí Xn của người đi bộ nhỏ hơn hẳn vị trí cực đạiMn, thì ở bước tiếp theo, người đi bộ đang ở vị trí hiện tại có thể reset (quay lại) về vị trí cực đại với xác suất r cố định. Với xác suất (1− r) còn lại, người đi bộ có thể bước sang trái hoặc phải với xác suất 1−r2 như nhau. Ngược lại nếuXn = Mn thì người đi bộ bước sang trái hoặc sang phải với xác suất 12 như nhau. Luật tiến hóa ngẫu nhiên này có thể mô tả như sau: nếu Xn < Mn thì (Xn+1,Mn+1) =  (Xn + 1,Mn), với xác suất (1− r)/2, (Xn − 1,Mn), với xác suất (1− r)/2, (Mn,Mn), với xác suất r và ngược lại Xn = Mn thì (Xn+1,Mn+1) = (Mn + 1,Mn + 1), với xác suất 1/2,(Mn − 1,Mn), với xác suất 1/2. Đầu tiên, chúng ta thấy rằng (Xn)n≥0 không phải là một quá trình Markov bởi luật tiến hóa của nó sử dụng trí nhớ về quá khứ (vị trí cực đại mà nó từng đạt được). Tuy nhiên (Xn,Mn)n≥0 là một quá trình Markov trong mặt phẳng hai chiều (X,M). Các tác giả trong [22] đã sử dụng ý tưởng chìa khóa này để tìm hiểu các tính chất của mô hình. Cụ thể, bởi phương pháp hàm sinh và các kỹ thuật giải tích phức tạp, họ tìm ra dáng diệu tiệm cận của kì vọng và phương sai của Xn vàMn: khi r = 0 (nghĩa là trường hợp bước đi ngẫu nhiên đơn giản thông thường) thì E[Xn] = 0, E[Mn] ∼ √ 2n pi ; (2.1.1) V ar[Xn] = n, V ar[Mn] ∼ ( 1− 2 pi ) n (2.1.2) 23 và khi r ∈ (0, 1), E[Xn] ∼ E[Mn] ∼ v(r)n ; (2.1.3) Var[Xn] ∼ Var[Mn] ∼ D(r)n, (2.1.4) với an ∼ bn nghĩa là an bn → 1 khi n→∞, ở đó v(r), D(r) > 0 có công thức tường minh theo r trong phương trình (6) and (10) ở [22] như sau: v(r) = r(1− r) r − 2r2 +√2r − r2 , (2.1.5) D(r) = [ (2− 2r − 5r2 + 3r3) + (2− r − r2 + 2r3) √ r(2− r) ] × (1− r)r 2√ r(2− r)[r − 2r2 +√r(2− r)]3 . (2.1.6) Trong trường hợp khi r = 0, dáng điệu tiệm cận của các đặc trưng về kì vọng và phương sai của vị trí cực đại đã được nghiên cứu hoàn chỉnh [31], [32], [33]. Trong chương này chúng ta chỉ quan tâm đến trường hợp không tầm thường 0 < r < 1 và r không thay đổi theo thời gian . Mặc dù (Xn,Mn)n≥0 là một quá trình Markov nhưng trong mặt phẳng hai chiều nên sử dụng phương pháp hàm sinh trực tiếp, các tính toán vẫn rất phức tạp. Ta quan sát rằng nếu đặt Yn = Mn − Xn thì (Yn)n≥0 là một bước ngẫu nhiên trên Z≥0 = {0, 1, . . .} bắt đầu từ 0, với luật tiến hóa như dưới đây: nếu Yn > 0 thì (Yn+1) =  Yn + 1, với xác suất (1− r)/2, Yn − 1, với xác suất (1− r)/2, 0, với xác suất r. và nếu Yn = 0 thì Yn+1 = 0, với xác suất 1/2,1, với xác suất 1/2. 24 Như vậy, (Yn)n≥0 bước sang trái hoặc sang phải với xác suất (1−r) 2 và reset lại về 0 với xác suất r. Khi Yn = 0 thì nó vẫn ở lại 0 với xác suất 12 hoặc bước tới 1 với xác suất cũng là 12 . Quan sát chìa khóa của chúng ta đó làMi+1 = Mi + 1 nếu Yi = Yi+1 = 0 vàMi+1 = Mi nếu ngược lại. Nói một cách khác,Mn đếm số hai lần bằng 0 liên tiếp của dãy (Yn)n≥0, hay là Mn = n−1∑ i=0 I(Yi = Yi+1 = 0). Xuất phát từ điều này ta gọi (Ti)i≥0 là dãy của thời gian dừng với T0 = 0 và với mọi i ≥ 1, Ti = inf{j ≥ Ti−1 + 1 : Yj = 0}. Do đó (Ti)i≥0 là một quá trình tái tạo và Ti là thời gian tái tạo thứ i và ta viết lạiMn như sau: Mn = Kn∑ i=0 I(Yi = Yi+1 = 0), với Kn = max{i : Ti ≤ n}. Hơn nữa, ta định nghĩa khoảng thời gian tái tạo như sau, với mọi i ≥ 1, τi = Ti − Ti−1. Rõ ràng (τi)i≥1 là dãy biến ngẫu nhiên độc lập cùng phân phối (i.i.d.) với τ = T1 = inf{i ≥ 1 : Yi = 0} và ta thu được Mn = Kn∑ i=1 I(τi = 1), với Kn = max{i : τ1 + τ2 + . . .+ τi ≤ n}. 25 2.2 CÁC ĐỊNH LÝ GIỚI HẠN CHOMn VÀ Xn Mục tiêu chính của phần này là chứng minh định lý sau đây: Định lý 2.2.1. [Các định lý giới hạn choMn và Xn] (i) Luật mạnh của số lớn và kỳ vọng Mn n h.c.c−−→ v(r), Xn n h.c.c−−→ v(r), khi n→∞, và lim n→∞ E[Mn] n = lim n→∞ E[Xn] n = v(r), với v(r) cho bởi (2.1.5). (ii) Định lý giới hạn trung tâm và phương sai Mn − µ′λn√ n d−→ N(0, D(r)), Xn − µ ′λn√ n d−→ N(0, D(r)), khi n→∞, và lim n→∞ Var[Mn] n = lim n→∞ Var[Xn] n = D(r), với D(r) cho bởi (2.1.6). Định lý 2.2.1 sẽ được chứng minh trong phần 2.2.2. Trước hết ta cần nghiên cứu một số tính chất của các ngẫu nhiên τ và Kn. 2.2.1 Tính chất của τ và Kn Bổ đề 2.2.2. Với k ≥ 1, ta có P(τ > k) = 1 2 (1− r)k−1P(T1,0 > k − 1), (2.2.7) ở đó, T1,0 = inf{i ≥ 1 : Zi = 0} là thời gian chạm 0 đầu tiên của bước đi ngẫu nhiên đơn giản (Zi)i≥0 bắt đầu từ 1, hay là Z0 = 1. 26 Từ đó, ta thu được hàm sinh của τ , K(s) := E[sτ ] = s+ s− 1 1− r 1−√1− a2 (a+ √ 1− a2 − 1) , (2.2.8) với a = (1− r)s. Chứng minh. Trước hết, ta có {τ > k} = {Y1 = 1, Y2 6= 0, . . . , Yk 6= 0}. Ta xét Ak = {Y1 = 1} ∩ {(Yi)i≥2 không reset tại các thời điểm i = 2, . . . , k}. (2.2.9) Khi đó, P(Ak) = 1 2 (1− r)k−1. (2.2.10) Hơn nữa, P(τ > k | Ak) = P(Y2 6= 0, . . . , Yk 6= 0 | Ak) = P(Z1 6= 0, . . . , Zk−1 6= 0 | Z0 = 1). (2.2.11) Thật vậy, với mỗi bước 2 ≤ i ≤ k, ta thấy P(Yi = Yi−1 ± 1 | Yi−1 6= 0 ; i không là điểm reset) = (1− r)/2 1− r = 1 2 . Hay nói cách khác, nếu Yi−1 6= 0 và nếu i không là điểm reset thì bước tiếp theo Yi đi lên hoặc đi xuống theo xác suất 1/2 như bước đi ngẫu nhiên đơn giản. Do đó ta có phương trình (2.2.11). Kết hợp (2.2.9) và (2.2.11) ta thu được khẳng định đầu tiên của Bổ đề. Để tính hàm sinh của τ , ta nhận xét rằng K(s) = E[sτ ] = ∞∑ k=0 P(τ = k)sk = ∞∑ k=1 [ P(τ > k − 1)− P(τ > k)]sk + P(τ = 0) 27 = ∞∑ k=1 P(τ > k − 1)sk − ∞∑ k=1 P(τ > k)sk = s ∞∑ k=0 P(τ > k)sk − ∞∑ k=1 P(τ > k)sk = s+ (s− 1) ∞∑ k=1 P(τ > k)sk = s+ s(s− 1) 2 ∞∑ k=0 (1− r)kP(T1,0 > k)sk = s+ s(s− 1) 2 (1 + ∞∑ k=1 (1− r)kP(T1,0 > k)sk). Theo [37], hàm sinh của T1,0 là F (s) = E[sT1,0] = ∞∑ k=0 P(T1,0 = k)sk = 1−√1− s2 s , từ đó suy ra ∞∑ k=1 P(T1,0 > k)sk = F (s)− 1 s− 1 , và vì vậy ∞∑ k=1 P(T1,0 > k)ak = F (a)− 1 a− 1 , với a = (1− r)s. Cuối cùng ta có hàm sinh K(s) = s+ s(s− 1) 2 ( 1 + F (a)− 1 a− 1 ) = s+ s− 1 (1− r) 1−√1− a2 − a 2(a− 1) = s+ s− 1 (1− r) (1−√1− a2 − a)(a+√1− a2 − 1) 2(a− 1)(1−√1− a2) × 1− √ 1− a2 (a+ √ 1− a2 − 1) = s+ s− 1 1− r 1−√1− a2 (a+ √ 1− a2 − 1) , (2.2.12) và bổ đề được chứng minh. 28 Hệ quả 2.2.3. Khi r ∈ (0, 1), chúng ta có E[τ ] = 1 2v(r) , với v(r) như trong (2.1.5), và E[τ 2] = E[τ ] + 2 [ (1− r)√ 2r − r2 (√2r − r2 − r) − ( 1− √ 2r − r2 ) √2r − r2 + r − 1√ 2r − r2(√2r − r2 − r)2 ] . Chứng minh. Đầu tiên ta có đạo hàm bậc nhất của K(s) K ′(s) = 1 + (1− r)(s− 1)s√ 1− (1− r)2s2(√1− (1− r)2s2 + (1− r)s− 1) + 1−√1− (1− r)2s2 (1− r)(√1− (1− r)2s2 + (1− r)s− 1) − (s− 1) ( − (1− r) 2s√ 1− (1− r)2s2 − r + 1 )( 1−√1− (1− r)2s2) (1− r)(√1− (1− r)2s2 + (1− r)s− 1)2 , và do đó E[τ ] = K ′(1) = 1−√2r − r2 (1− r)(√2r − r2 − r) + 1 = (1−√2r − r2)(√2r − r2 + r) (1− r)(√2r − r2 − r)(√2r − r2 + r) + 1 = r(1− 2r) +√2r − r2 2r(1− r) = 1 2v(r) . (2.2.13) Tương tự, chúng ta cũng tính moment bậc hai của τ bởi E[τ 2] = d ds ( sK ′(s) ) s=1 = K ′(1) +K ′′(1) = E[τ ] +K ′′(1), (2.2.14) với K ′′(1) = 2 [ (1− r)√ 2r − r2 (√2r − r2 − r) 29 − ( 1− √ 2r − r2 ) √2r − r2 + r − 1√ 2r − r2(√2r − r2 − r)2 ] . Từ đó, ta thu được công thức cho E[τ 2] như trong phát biểu của Hệ quả. Các định lý giới hạn như luật mạnh của số lớn và định lý giới hạn trung tâm của quá trình đếm (Kn)n≥1 được nghiên cứu tường minh trước đó, ta có thể tìm trong một số tài liệu như khóa học trong [38]. Đặc biệt trong cuốn sách Stopped RandomWalk: Limit Theorems and Applications [29] của Allan Gut tổng kết nhiều kết quả quan trọng về bước đi ngẫu nhiên và quá trình tái tạo. Các kết quả này đã được giới thiệu trong phần kiến thức chuẩn bị của Chương 1. Sử dụng lần lượt Định lý 1.2.5 và Định lý 1.2.7 chúng ta có tương ứng luật mạnh của số lớn và định lý giới hạn trung tâm cho quá trình đếm tái tạo (Kn)n≥0 sau đây: Định lý 2.2.4. [Các định lý giới hạn cho Kn]. Ta đặt λ := 1 E[τ ] = 2v(r), σ2τ = Var[τ ]. (i) Luật mạnh của số lớn Kn n h.c.c−−→ λ khi n→∞. (2.2.15) (ii) Dáng điệu tiệm cận của kì vọng E[Kn] = nλ+ o( √ n). (2.2.16) (iii) Định lý giới hạn trung tâm Kn − nλ√ σ2τλ 3n d−→ N(0, 1) khi n→∞. (2.2.17) (iv) Dáng điệu tiệm cận của phương sai lim n→∞ Var[Kn] n = σ2τ (E(τ))3 = σ2τλ 3. (2.2.18) 30 2.2.2 Các định lý giới hạn choMn và Xn Trong phần này, chúng ta sẽ chứng minh Định lý 2.2.1. I. Luật số lớn và kì vọng củaMn. Trước hết, ta nhớ lại rằng, Mn = Kn∑ i=1 I(τi = 1), với (τi)i≥1 là dãy biến ngẫu nhiên độc lập cùng phân phối với τ (như trong Bổ đề 2.2.2) và Kn = max{i ≥ 1 : τ1 + . . .+ τi ≤ n}. Áp dụng Định lý 1.2.2 cho bước đi ngẫu nhiên (Mi)(i≥0) với dãy gia số ngẫu nhiên i.i.d (I(τi = 1))i≥1 thỏa mãn E[I(τi = 1)] = P(τ = 1) = µ′ = 1 2 và dãy thời gian Kn thỏa mãn Kn n h.c.c−−→ λ = 2v(r) khi n→∞, bởi Định lí 2.2.4, ta thu được luật mạnh của số lớn choMn lim n→∞ Mn n = lim n→∞ ∑Kn i=1 I(τi = 1) n = µ′λ = v(r) h.c.c. (2.2.19) Để thu được dáng điệu tiệm cận của kì vọng của Mn, chúng ta áp dụng Định lý 1.2.4 (chú ý E[Kn] là hữu hạn với mỗi n hữu hạn) và thu được E[Mn] = µ′E[Kn]. (2.2.20) Kết hợp với (2.2.16) ta có lim n→∞ E[Mn] n = µ′ lim n→∞ E[Kn] n = µ′λ = v(r). (2.2.21) II. Định lí giới hạn trung tâm và phương sai củaMn. Bởi phần trước, chúng ta biết rằng E[Mn] = (µ′λ+ o(1))n. Chúng ta thực hiện biến đổi Mn − µ′λn√ n = Mn − µ′λ ∑Kn i=1 τi√ n + µ′λ ∑Kn i=1 τi − n√ n 31 = ∑Kn i=1 Vi√ n + µ′λ TKn − n√ n = SKn√ n + µ′λ TKn − n√ n , với SKn = Kn∑ i=1 Vi và Vi = I(τi = 1)− µ′λτi. (2.2.22) Ta thấy (Vi)i≥1 là dãy biến ngẫu nhiên độc lập cùng phân phối (i.i.d.) với V = I(τ = 1)− µ′λτ . Ta dễ dàng tính được E[Vi] = E[V ] = 0, và Var[Vi] = Var[V ] = E[V 2] = E[(I(τ = 1)− µ′λτ)2] = (µ′)2λ2E[τ 2]− 2µ′λE[τI(τ = 1)] + E[(I(τ = 1))2] = (µ′)2λ2E[τ 2]− 2(µ′)2λ+ µ′. Thay µ′ = 12 , λ = 1 E[τ ] = 2v(r) và sử dụng Hệ quả 2.2.3 cùng các tính toán đại số, chúng ta thu được λVar[V ] = D(r), (2.2.23) với D(r) là hằng số trong (2.1.6). Bởi Định lý 1.2.3 (ii) ta có SKn√ Var[V ]nλ d−→ N(0, 1), điều này tương đương với SKn√ n d−→ N(0, D(r)). (2.2.24) Bổ đề 2.2.5. Chúng ta có sup n≥1 E[Y 4n ] ≤ sup n≥1 E [ (TKn − n)4 ] <∞. (2.2.25) Do đó, khi n→∞, TKn − n√ n h.c.c−−→ 0, Yn√ n h.c.c−−→ 0. (2.2.26) 32 Chứng minh. Trước hết, vì 0 ≤ Yn ≤ n − TKn nên chúng ta chỉ cần chứng minh các khẳng định cho dãy n − TKn. Theo định nghĩa của Kn, ta thấy với mọi k ≥ 1, P(n− TKn ≥ k) ≤ P(TKn+1 − TKn ≥ k) = P(τKn+1 ≥ k) = P(τ ≥ k). Do đó, bởi Bổ đề 2.2.2, E[(n− TKn)4] ≤ E[τ 4] ≤ 16 + ∑ k≥1 (k + 1)4P(τ > k) ≤ 16 + ∑ k≥1 (k + 1)4(1− r)k =: C <∞. Vì vậy, với mọi ε > 0, bởi bất đẳng thức Markov P ( n− TKn√ n ≥ ε ) ≤ E[(n− TKn) 4] ε4n2 ≤ C ε4n2 , và do đó, ∑ n≥1 P ( n− TKn√ n ≥ ε ) <∞. Từ đó, sử dụng Bổ đề Borel-Cantelli ta thu được điều phải chứng minh. Kết hợp (2.2.24) và bổ đề trên ta suy ra định lý giới hạn trung tâm choMn: khi n→∞, Mn − µ′λn√ n = SKn√ n + µ′λ TKn − n√ n d−→ N(0, D(r)). (2.2.27) Bây giờ, chúng ta xem xét dáng điệu tiệm cận phương sai củaMn. Trước hết, ta khẳng định rằng dãy biến ngẫu nhiên( Mn − µ′λn√ n )2 n≥1 là khả tích đều. (2.2.28) Thật vậy, đặt νn = min{s : Ts > n}. Khi đó, νn là dãy thời gian dừng và νn = Kn + 1. Do đó, chúng ta có( Mn − µ′λn√ n )2 = ( Sνn√ n − Vνn√ n − µ′λn− TKn√ n )2 33 Bởi Định lý 1.6.2 hoặc Định lý 1.6.3 trong [29] về tính khả tích đều và Định lý 1.2.5, ta suy ra dãy ( SKn√ n )2 n≥1 là khả tích đều. Dãy ( Vνn√ n )2 n≥1 là khả tích đều do moment bậc 4 của Vνn bị chặn và dãy( n− TKn√ n )2 n≥1 là khả tích đều vì moment bậc 4 của (n − TKn) bị chặn (Bổ đề 2.2.5). Sử dụng định lý về sự bị chặn của dãy khả tích đều, ta suy ra điều phải chứng minh. Mặt khác, bởi E[Mn] = µ′E[Kn] và E[Kn] = λn+ o( √ n) (xem (2.2.16)), chúng ta có thể thay thế µ′λn bởi E[Mn] trong (2.2.28) và thu được rằng dãy( Mn − E[Mn]√ n )2 n≥1 là khả tích đều. Ngoài ra, dãy này cũng hội tụ theo phân phối đến Z = N(0, D(r)), từ đó áp dụng Định lý A.1.1 trong [29] ta thu được lim n→∞ Var[Mn] n = lim n→∞E ( Mn − E[Mn]√ n )2 = D(r). (2.2.29) III. Các định lí giới hạn cho Xn. Chúng ta biết rằng Xn = Mn − Yn và bởi Bổ đề 2.2.5, Yn√n → 0 hầu chắc chắn và supn≥1 E[Y 4n ] là hữu hạn. Do đó, các định lý giới hạn cho Mn cũng đúng cho Xn. Chứng minh Định lý 2.2.1 được hoàn tất. CHƯƠNG 3 BƯỚC ĐI NGẪU NHIÊN CÓ TRÍ NHỚ SUY GIẢM Trong chương trước, chúng ta đã nghiên cứu mô hình bước đi ngẫu nhiên có trí nhớ cố định. Trí nhớ thay đổi, cụ thể là trí nhớ giảm dần theo thời gian, là một hiện tượng thú vị và có thể coi là sự mở rộng của trường hợp trí nhớ không thay đổi. Chúng ta sẽ nghiên cứu sự chuyển pha theo tốc độ suy giảm trí nhớ của mô hình này thông qua dáng điệu tiệm cận của kì vọng. Bây giờ trong chương này, trí nhớ không còn cố định theo mỗi thời gian n mà nó sẽ suy giảm. Cụ thể, ta gọi rn = rn−a ∧ 12 với a∧ b = min(a, b) là xác suất reset về vị trí cực đại của người đi bộ ở thời điểm n. Khi đó ta xét bước ngẫu nhiên có luật tiến hóa như sau: nếu Xn−1 < Mn−1 thì (Xn,Mn) =  (Xn−1 + 1,Mn−1), với xác suất (1− rn)/2, (Xn−1 − 1,Mn−1), với xác suất (1− rn)/2, (Mn−1,Mn−1), với xác suất rn và nếu Xn−1 = Mn−1 thì (Xn,Mn) = (Mn−1 + 1,Mn−1 + 1), với xác suất 1/2,(Mn−1 − 1,Mn−1), với xác suất 1/2. 34 35 Lưu ý rằng a = 0 là trường hợp trí nhớ cố định mà ta nghiên cứu trong chương 2. Trong mô hình bước ngẫu nhiên trí nhớ suy giảm theo thời gian này, kết quả chính của chúng ta là chứng minh hiện tượng chuyển pha theo a thông qua định lý sau đây: Định lý 3.0.1. [Định lý về dáng điệu tiệm cận của E[Xn] và E[Mn]] lim n→∞ E[Xn] ϕa(n) = FX(r, a) (3.0.1) và lim n→∞ E[Mn] ψa(n) = FM(r, a), (3.0.2) trong đó ϕa(n) =  n1− a 2 khi 0 < a < 1, √ n khi a = 1, n 3 2−a khi 1 < a < 32 , log n khi a = 32 , 1 khi a > 32 và ψa(n) = n max{1−a2 , 1 2} và FX(a, r) =  √ 2r 2− a, khi 0 < a < 1, 2r2 √ 2 pi B(3/2, r), khi a = 1, λ2(a, r)− λ3(a, r) + λ4(a, r) khi a > 1 và FM(a, r) =  √ 2r 2− a, khi 0 < a < 1, (2r2 + r) √ 2 pi B(3/2, r), khi a = 1, λ1(a, r) + λ5(a, r), khi a > 1, 36 với λ1(a, r), λ2(a, r), . . . , λ5(a, r) được định nghĩa trong Bổ đề 3.2.8. Trước hết chúng ta thấy rằng, khi ở pha dưới 0 < a < 1, dáng điệu tiệm cận các kì vọng củaMn vàXn là cùng cỡ và cùng hàm tỷ lệ. Tại điểm chuyển pha a = 1, tuy chúng cùng cỡ nhưng lại khác hàm tỷ lệ. Còn tại pha trên a > 1, cỡ của E[Xn] nhỏ hơn hẳn cỡ của E[Mn]. Hơn thế nữa, chúng ta dễ dàng suy ra dáng điệu tiệm cận của các hàm tỷ lệ theo a và r như sau: FM(a, r) ∼  √ r 2 ∼ v(r) khi a = 0, r → 0,√ r 2 ∼ v(r) khi a→ 0, r → 0,√ 2 pi khi a = 1, r → 0,√ 2 pi khi a→ 1+, r → 0,√ 2r khi a = 1, r →∞, √ 2r khi a→ 1−, r →∞. (3.0.3) và FX(a, r) = 0 khi a = 1, r → 0,0 khi a→ 1+, r → 0, (3.0.4) FX(a, r) ∼  √ r 2 ∼ v(r) khi a = 0, r → 0,√ r 2 ∼ v(r) khi a→ 0, r → 0,√ 2r khi a = 1, r →∞, √ 2r khi a→ 1−, r →∞. (3.0.5) 3.1 Một hiệu chỉnh của (Xn)n≥0 Trong bước ngẫu nhiên (Xn)n≥0, các điểm reset phụ thuộc vào giá trị tương quan giữa (Xn,Mn). Bây giờ ta sẽ hiệu chỉnh mô hình trên để thu được một mô hình đơn giản hơn, ở đó các điểm reset xuất hiện độc lập. Cụ thể, ta xét 37 bước ngẫu nhiên (Xˆn)n≥0 bắt đầu từ 0 (hay là Xˆ0 = 0), và có xác suất chuyển cho bởi (Xˆn, Mˆn) =  (Xˆn−1 + 1,max{Mˆn−1, Xˆn−1 + 1}) với x.s 1−rn2 , (Xˆn−1 − 1, Mˆn−1) với x.s 1−rn2 , (Mˆn−1, Mˆn−1) với x.s rn, ở đó, với k ≥ 0 Mˆk = max{Xˆi, i = 0, . . . , k}. Điểm khác biệt duy nhất giữa hai quá trình đó là khi ở thời điểm reset n nào đó, quá trình X cần xác nhận rằng Xn−1 < Mn−1 thì mới reset, trong khi đó quá trình Xˆ sẽ reset mà không quan tâm Xˆn−1 < Mˆn−1 hay không. Điều này giúp cho các tính toán trên Xˆ đơn giản hơn. Kết quả dưới đây, chỉ ra rằng sai khác giữa hai quá trình có thể được kiểm soát qua số lượng điểm reset. Bổ đề 3.1.1. [Bổ đề coupling] Gọi (Zt)t≥0 là bước đi ngẫu nhiên đơn giản bắt đầu từ 0. Gọi J là tập con ngẫu nhiên của N = {1, 2, . . .}, độc lập với (Zt)t≥0, và có luật cho bởi P(j ∈ J ) = rj. Khi đó, ta có thể xây dựng hai quá trình (Xi)i≥0 và (Xˆi)i≥0 từ (Zt)t≥0 và J , sao cho max 0≤i≤n {|Mi − Mˆi|, |Xi − Xˆi|} ≤ |J ∩ [0, n]|, (3.1.6) với mọi n ≥ 0, và |A| là kí hiệu cho lực lượng của tập A. Chứng minh. Xác suất chuyển X và Xˆ nói rằng, giữa các thời điểm reset hai quá trình này chuyển động như một bước đi ngẫu nhiên đơn giản. Ngoài ra, với mỗi thời điểm s, ta có (Zt+s − Zs)t≥0 là một bước ngẫu nhiên đơn giản bắt đầu từ 0, và độc lập với (Zu)u≤s. Vậy ta xây dựng X, Xˆ như sau. • Gọi J = {t1, t2, . . .}. 38 • Với 0 ≤ t ≤ t1 − 1, ta xét Xt = Xˆt = Zt. Tại điểm reset t1, ta đặt Xˆt1 = Mˆt1−1 = max0≤t≤t1−1 Zt. VớiX , ta cần xét kĩ hơn. NếuXt1−1 < Mt1−1 thì Xt1 = Mt1−1 = max0≤t≤t1−1 Zt. Ngược lại, nếu Xt1−1 = Mt1−1 thì Xt1 = Zt1. • Với i ≥ 1, ta đặtXˆti = Xˆti−1 + max{Zs − Zti−1, ti−1 ≤ s ≤ ti − 1},Xˆt = Xˆti + Zt − Zti, với ti + 1 ≤ t ≤ ti+1 − 1. Trong khi đó, luật xác định của X phức tạp hơn một chút. (i) Nếu Xti−1 = Mti−1 thì ta đặt Xt = Xti−1 + Zt − Zti−1, với ti ≤ t ≤ ti+1 − 1. (ii) Nếu Xti−1 < Mti−1 thì Xti = Xti−1 + maxti−1≤s≤ti−1{Zs − Zti−1} + I(Xti−1 = Xti−1−1 − 1,maxti−1≤s≤ti−1{Zs − Zti−1} = 0), Xt = Xti + Zt − Zti, với ti + 1 ≤ t ≤ ti+1 − 1. Như vậy, nếu cho trước tập các điểm reset J , thì Xˆ được xây dựng từ Z như sau: với các khoảng thời gian t ∈ (ti, ti+1), Xˆ là tịnh tiến của Z từ Zti tới Xˆti, và tại các điểm reset Xˆti là tổng dồn của các giá trị cực đại maxtj−1≤s≤tj−1{Zs−Ztj−1} với j = 1, . . . , i. Trong khi đó, nếuXti−1 = Mti−1 thì trong khoảng t ∈ [ti, ti+1), X đơn giản là tịnh tiến của Z từ Zti−1 tới Xti−1. Ngược lại, nếu Xti−1 < Mti−1, ta tịnh tiến Z từ Zti tới Xti. Ở công thức xác định Xti sẽ có một trường hợp đó là nếu Xti−1 = Xti−1−1 − 1 (tức là Xti−1−1 = Mti−1, do đó X không reset tại đây, và sau đó X đi xuống 1 bước, Xti−1 = Xti−1−1 − 1), và maxti−1≤s≤ti−1{Zs − Zti−1} = 0, thì giá trị cực đại của X trong khoảng ti−1 ≤ s ≤ ti − 1 sẽ là Xti−1 nhỏ hơn 1 đơn vị so với 39 Xti−1−1 = Mti−1−1. Vì vậy, ta cần reset tới vị trí của Xti−1−1 = Mti−1−1 = Xti−1 + 1, và do đó ta có hàm chỉ tiêu trong xác định của Xti. Ta nhận xét rằng với t ∈ (ti, ti+1) ta luôn có Xt = Xti + Zt − Zti, Xˆt = Xˆti + Zt − Zti. (3.1.7) Thật vậy, biểu thức cho Xˆ được suy ra trực tiếp từ định nghĩa. Với X , trường hợp Xti−1 < Mti−1 thì công thức trên chính là định nghĩa của Xt. Với trường hợp Xti−1 = Mti−1, ta thấy Xt = Xti−1 + Zt − Zti−1 = Xti + Zt − Zti, bởi vìXti = Xti−1 +Zti−Zti−1. Bởi nhận xét (3.1.7), để chứng minh (3.1.6), ta cần chỉ ra với mọi i ≥ 1, |Xti − Xˆti| ≤ i. Muốn vậy, ta chỉ cần chứng minh với i ≥ 1, |(Xti−Xˆti)−(Xti−1−Xˆti−1)| = |(Xti−Xti−1)−(Xˆti−Xˆti−1)| ≤ 1. (3.1.8) Trước hết, ta có Xˆti − Xˆti−1 = max ti−1≤s≤ti−1 {Zs − Zti−1}. (3.1.9) Nếu Xti−1 = Mti−1 thì Zti−1 − Zti−1 = maxti−1≤s≤ti−1{Zs − Zti−1} và hơn nữa, Xti = Xti−1 + Zti − Zti−1 = Xti−1 + Zti−1 − Zti−1 + Zti − Zti−1 = Xti−1 + max ti−1≤s≤ti−1 {Zs − Zti−1}+ Zti − Zti−1. Do đó, |(Xti −Xti−1)− (Xˆti − Xˆti−1)| = |Zti − Zti−1| = 1. Nếu Xti−1 < Mti−1 thì bởi (ii), 0 ≤ (Xti −Xti−1)− max ti−1≤s≤ti−1 {Zs − Zti−1} ≤ 1. Kết hợp với (3.1.9) ta thu được (3.1.8). Như vậy, trong mọi trường hợp thì (3.1.8) đúng, và chứng minh được hoàn thành. 40 Hình 3.1: Minh họa hai quá trình X và Xˆ được xây dựng từ bước đi ngẫu nhiên đơn giản Z (đoạn màu xanh da trời) và tập J với hai thời điểm reset t1, t2. Ban đầu,X, Xˆ và Z đều chuyển động giống nhau cho tới thời điểm t1 − 1. Ở điểm reset t1, hai quá trình X và Xˆ cùng reset tới vị trí cực đại và sau đó chuyển động tịnh tiến (từ Z) giống nhau cho tới thời điểm t2−1 (đoạn màu đỏ). Tại điểm reset t2, Xˆ reset lại vị trí cực đại và sau đó chuyển động tịnh tiến từ Z (đoạn màu xanh lá mạ), còn X vẫn tiếp tục chuyển động tính tiến từ Z (đoạn màu tím). 3.2 Dáng điệu tiệm cận của E[Xn] và E[Mn] Hiện tượng chuyển pha là một hiện tượng phổ biến trong các quá trình vật lý. Ví dụ sự chuyển trạng thái của vật chất theo nhiệt độ, áp suất hoặc sự thay đổi của tính chất thẩm thấu theo mật độ cấu trúc của một vật liệu,. . . Mục tiêu chính của phần này là chỉ ra hiện tượng chuyển pha trong mô hình bước đi ngẫu nhiên có trí nhớ giảm dần. Cụ thể, chúng ta sẽ chỉ ra rằng dáng điệu tiệm cận kì vọng củaMn và của Xn sẽ thay đổi theo giá trị của a. Đầu tiên, ta viết các phần tử của J bởi J = {t1, t2, . . .} Đặt kn = max{i ≥ 1 : ti ≤ n}, t0 = 0. Với mỗi i, k ≥ 0, ta đặt m (i) k = max 0≤s≤k {Zti+s − Zti}. 41 Khi đó, kì vọng củam(i)k không phụ thuộc i, do đó ta có thể đặt g(k) = E[m(i)k−1] = E[ max 0≤s≤k−1 Zs]. (3.2.10) Bổ đề 3.2.1. [31] Ta có lim k→∞ g(k)√ k = √ 2 pi . Ta quan sát rằng EXˆtkn = E [ kn−1∑ i=0 max ti≤j<ti+1 {Zj − Zti} ] = E [ kn−1∑ i=0 m (i) ti+1−ti−1 ] = ∞∑ i=0 E [ m (i) ti+1−ti−1I(ti+1 ≤ n) ] = ∞∑ i=0 E [ E [ m (i) ti+1−ti−1I(ti+1 ≤ n) | ti, ti+1 ]] = ∞∑ i=0 E[g(ti+1 − ti)]I(ti+1 ≤ n)] = E[g(t1)I(t1 ≤ n)] + ∞∑ i=1 E[g(ti+1 − ti)I(0 < ti < ti+1 ≤ n)]. (3.2.11) Chúng ta định nghĩa hàm h : N → R như sau. Trước hết h(1) = 0 và với j ≥ 2, h(j) = j−1∑ k=1 g(k)Pj,k, (3.2.12) trong đó Pj,k = rj−k k−1∏ l=1 (1− rj−l). (3.2.13) Khi đó, ta chú ý rằng với i ≥ 1, E [ g(ti+1 − ti) | ti+1 = j ] = j−1∑ k=1 g(k)P(ti = j − k | ti+1 = j) 42 = j−1∑ k=1 g(k)Pj,k = h(j). Hơn nữa điều kiện i ≥ 1 tương đương với ti > 0, và do đó biểu thức trên kéo theo h(ti+1) = E[g(ti+1 − ti)I(ti > 0) | ti+1]. (3.2.14) Vì vậy, E[g(ti+1 − ti)I(0 < ti < ti+1 ≤ n)] = E [ E[g(ti+1 − ti)I(0 < ti < ti+1) | ti+1]I(ti+1 ≤ n) ] = E [ h(ti+1)I(ti+1 ≤ n) ] . Như vậy, ta có E[Xˆtkn ] = E[g(t1)I(t1 ≤ n)] + ∞∑ i=1 E[h(ti+1)I(ti+1 ≤ n)] = E[g(t1)I(t1 ≤ n)] + E [ ∞∑ i=2 h(ti)I(ti ≤ n) ] = E[g(t1)I(t1 ≤ n)] + E [ kn∑ i=2 h(ti)I(kn ≥ 2) ] = E[g(t1)I(t1 ≤ n)] + E [ kn∑ i=1 h(ti)I(kn ≥ 1) ] − E[h(t1)I(kn ≥ 1)] = E[g(t1)I(t1 ≤ n)]− E[h(t1)I(t1 ≤ n)] + E [ kn∑ i=1 h(ti)I(kn ≥ 1) ] . Hơn nữa, E [ kn∑ i=1 h(ti)I(kn ≥ 1) ] = E [ ∑ j∈J∩[1,n] h(j) ] = n∑ j=1 E[h(j)I(j ∈ J )] = n∑ j=1 h(j)rj. 43 Kết hợp hai phương trình trên, ta thu được E[Xˆtkn ] = E[g(t1)I(t1 ≤ n)]− E[h(t1)I(t1 ≤ n)] + n∑ j=1 h(j)rj. (3.2.15) Bởi định nghĩa của Mˆn, chúng ta có Mˆn = max tkn≤j≤n Xˆtkn + Zj − Ztkn = Xˆtkn +m(kn)n−tkn . (3.2.16) Do đó, E[Mˆn] = E[Xˆtkn ] + E[g(n+ 1− tkn)]. (3.2.17) Chú ý rằng E(g(n− tkn)) = n∑ k=1 g(k)P(n+ 1− tkn = k) + g(n+ 1)P(t1 > n) = n∑ k=1 g(k)Pn+1,k + g(n+ 1)P(t1 > n) = h(n+ 1) + g(n+ 1)P(t1 > n). (3.2.18) Vì vậy, E[Mˆn] = E[Xˆtkn ] + h(n+ 1) + g(n+ 1)P(t1 > n). (3.2.19) Mặt khác, vì Xˆn = Xˆtkn + Zn − Ztkn , E[Xˆn] = E[Xˆtkn ]. (3.2.20) Chúng ta tổng hợp các kết quả trên trong bổ đề dưới đây. Bổ đề 3.2.2. Giả sử J = {t1, t2, . . .} là tập ngẫu nhiên như trong Bổ đề 3.1.1. Khi đó, E[Xˆn] = E[g(t1)I(t1 ≤ n)]− E[h(t1)I(t1 ≤ n)] + n∑ j=1 h(j)rj, E[Mˆn] = E[Xˆn] + h(n+ 1) + g(n+ 1)P(t1 > n), với g và h là các hàm cho bởi (3.2.10) và (3.2.12). 44 Từ bổ đề trên, ta thấy rằng để thu được E[Mˆn] và E[Xˆn] ta cần nghiên cứu hàm h(·). Trong các phần tiếp theo, chúng ta sẽ chỉ ra rằng dáng điệu tiệm cận của dãy trên thay đổi từng pha (theo giá trị của a). Do đó, dáng điệu của E[Mˆn] và E[Xˆn] cũng sẽ thay đổi. 3.2.1 Pha dưới 0 < a < 1 Chúng ta sẽ chứng minh rằng h(j) sẽ tập trung độ lớn trung quanh ja với j đủ lớn bởi bổ đề sau: Bổ đề 3.2.3. Ta có lim j→∞ h(j) ja/2 = 1√ 2r . (3.2.21) Chứng minh. Để chứng minh bổ đề này, ta sẽ chỉ ra lim j→∞ hc(j) ja/2 = 1√ 2r , (3.2.22) với hc(j) = ja log2 j∑ k=ja/ log2 j g(k)Pj,k, và khi j →∞, ja/ log2 j∑ k=1 g(k)Pj,k = o(j a/2/ log j), (3.2.23) và j−1∑ k=ja log2 j g(k)Pj,k = o(1). (3.2.24) Chúng ta bắt đầu với (3.2.22). Khi ja/ log2 j ≤ k ≤ ja log2 j và j lớn thì rj−l = r(j − l)−a = rj−a(1 + o(1)) với mọi l = 1, . . . , k. Khi đó, sử dụng xấp xỉ log(1− x) = −x(1 + o(1)), ta có Pj,k = rj−k k−1∏ l=1 (1− rj−l) = rj−k exp ( k−1∑ l=1 log(1− rj−l) ) 45 = rj−k exp ( −(1 + o(1)) k−1∑ l=1 rj−l ) = (1 + o(1))rj−a exp (−(r + o(1))kj−a) . Từ đó sử dụng Bổ đề 3.2.1 nói rằng g(k) = √ 2+o(1) pi √ k, ta suy ra, khi j →∞, hc(j) = (1 + o(1)) √ 2 pi r ja ja log2 j∑ k=ja/ log2 j √ k exp (−(r + o(1))k/ja) . = (1 + o(1)) √ 2 pi r ja ∫ ja log2 j ja/ log2 j √ x exp (−(r + o(1))x/ja) dx = (1 + o(1)) √ 2 pir ja/2 ∫ r log2 j r/ log2 j √ y exp(−(1 + o(1))y)dy = (1 + o(1)) √ 2 pir ja/2 ∫ ∞ 0 √ y exp(−y)dy = 1 + o(1