Đăng ký Đăng nhập
Trang chủ Một số mô hình xếp hàng và ứng dụng...

Tài liệu Một số mô hình xếp hàng và ứng dụng

.PDF
77
655
73

Mô tả:

́ ĐẠI HỌC QUÔC GIA HÀ NỘI ̀ TRƢƠNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- NGUYỄN THỊ HÀ MỘT SỐ MÔ HÌNH XẾP HÀNG VÀ ỨNG DỤNG Chuyên ngành: Lý thuyết xác xuất và thống kê toán học Mã số: 604601106 LUẬN VĂN THẠC SĨ KHOA HỌC NGƢỜI HƢỚNG DẪN: Ts. Trần Mạnh Cƣờng Hà Nội - 2016 1 Mục Lục MỞ ĐẦU ....................................................................................................... Error! Bookmark not defined. CHƢƠNG 1 ................................................................................................... Error! Bookmark not defined. KIẾN THỨC CHUẨN BỊ .............................................................................. Error! Bookmark not defined. 1.1 Phân bố Poisson và phân bố mũ..................................................... Error! Bookmark not defined. 1.1.1 Phân bố Poisson ............................................................................ Error! Bookmark not defined. 1.1.2 Phân bố mũ: .................................................................................. Error! Bookmark not defined. 1.2. Xích Markov ....................................................................................... Error! Bookmark not defined. 1.2.1. Phân loại trạng thái xích Markov ................................................. Error! Bookmark not defined. 1.3. Quá trình Markov ................................................................................ Error! Bookmark not defined. 1.3.1. Trƣờng hợp không gian trạng thái hữu hạn.................................. Error! Bookmark not defined. 1.3.2. Trƣờng hợp không gian trạng thái vô hạn đếm đƣợc ................... Error! Bookmark not defined. CHƢƠNG 2: .................................................................................................. Error! Bookmark not defined. MỘT SỐ MÔ HÌNH XẾP HÀNG ................................................................. Error! Bookmark not defined. 2.1 Khái niệm và phân loại quá trình xếp hàng ......................................... Error! Bookmark not defined. 2.1.1 Khái niệm quá trình xếp hàng ....................................................... Error! Bookmark not defined. 2.1.2 Các yếu tố cơ bản của hàng đợi .................................................... Error! Bookmark not defined. a. Bố trí vật lí của hệ thống .................................................................... Error! Bookmark not defined. b. Nguyên tắc phục vụ............................................................................ Error! Bookmark not defined. c. Các phân phối xác suất của các dòng tín hiệu, dòng phục vụ ............ Error! Bookmark not defined. 2.1.3 Phân tích hàng đợi......................................................................... Error! Bookmark not defined. 2.1.4 Phân loại Kendall .......................................................................... Error! Bookmark not defined. 2.1.5 Mục tiêu của phân tích hàng đợi ................................................... Error! Bookmark not defined. 2.2 Một số mô hình xếp hàng cơ bản ......................................................... Error! Bookmark not defined. 2.2.1 Mô hình xếp hàng sinh – chết tổng quát ....................................... Error! Bookmark not defined. 2.2.2 Mô hình hàng đợi M/M/1.............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian khách hàng chờ đợi............................................................ Error! Bookmark not defined. c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. d. Quá trình dời đi .................................................................................. Error! Bookmark not defined. e. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.3. Mô hình hàng đợi M/M/s ............................................................. Error! Bookmark not defined. a. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. 2 b. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. c. Quá trình dời đi .................................................................................. Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.4. Mô hình hàng đợi hữu hạn M/M/s/K ........................................... Error! Bookmark not defined. a. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.5. Mô hình hàng đợi M/G/1 ............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.6. Mô hình hàng đợi G/M/1 ............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. c. Chu kỳ bận rộn ................................................................................... Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. CHƢƠNG 3: .................................................................................................. Error! Bookmark not defined. ỨNG DỤNG .................................................................................................. Error! Bookmark not defined. 3.1 Mô phỏng một số mô hình xếp hàng bằng Matlab............................... Error! Bookmark not defined. 3.1.1 Mô phỏng hàng đợi M/M/1 ........................................................... Error! Bookmark not defined. 3.2 Ứng dụng của mô hình xếp hàng trong bài toán ra quyết định. ........... Error! Bookmark not defined. a) Xét ba bài toán sau: ............................................................................ Error! Bookmark not defined. b) Hàm giá: ............................................................................................ Error! Bookmark not defined. KẾT LUẬN.................................................................................................... Error! Bookmark not defined. TÀI LIỆU THAM KHẢO ............................................................................. Error! Bookmark not defined. 3 MỞ ĐẦU Lý thuyết xếp hàng đã đƣợc nghiên cứu và ứng dụng rộng rãi trên thế giới trong nhiều lĩnh vực ngành nghề khác nhau nhƣ bƣu chính viễn thông, hàng không, đƣờng sắt, kiểm soát lƣu lƣợng giao thông, đánh giá hiệu năng hệ thống máy tính, y tế và chăm sóc sức khỏe, không lƣu, bán vé … Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài nguyên, phải chờ để đƣợc phục vụ và đôi khi bị từ chối phục vụ. Lý thuyết quá trình xếp hàng (queueing process) xác định và tìm các phƣơng án tối ƣu để hệ thống phục vụ là tốt nhất. Trong nửa đầu của thế kỷ 20 lý thuyết xếp hàng đã đƣợc ứng dụng để nghiên cứu thời đợi trong các hệ thống điện thoại. Ngày nay lý thuyết xếp hàng còn có nhiều ứng dụng trong các lĩnh vực khác nhau nhƣ trong mạng máy tính, trong việc quản lý xí nghiệp, quản lý giao thông và trong các hệ phục vụ khác … Ngoài ra lý thuyết xếp hàng cũng còn là cơ sở toán học để nghiên cứu và ứng dụng trong nhiều bài toán kinh tế nhƣ đầu tƣ, kiểm kê, rủi ro của bảo hiểm, thị trƣờng chứng khoán … Chuỗi Markov là quá trình xếp hàng với thời gian rời rạc đã đƣợc xem xét trong giáo trình xác suất thống kê. Quá trình sinh tử cũng là quá trình xếp hàng, trong đó sinh biểu thị sự đến và tử biểu thị sự rời hàng của hệ thống. Đối với lý thuyết xếp hàng ta quan tâm đến các số đo hiệu năng, đó là các giá trị trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống). Để tính các đại lƣợng này ta có thể sử dụng phƣơng pháp giải phƣơng trình tích phân dạng Wiener – Hopf hoặc phƣơng pháp khảo sát chuỗi Markov nhúng. Từ đó suy ra các công thức tính các phân bố ổn định cho các loại hàng M/M/k, M/M/k/N; Công thức tổng quát tính các giá trị trung bình này cho các hàng G/G/1 và công thức cụ thể cho các hàng đặc biệt M/M/1, M/D/1 và M/𝐸 𝑘 /1 … Luận văn này tìm hiểu về một số mô hình xếp hàng cơ bản và ứng dụng của nó. Nội dung của luận văn này gồm ba chƣơng. Chƣơng 1: Kiến thức chuẩn bị. Chƣơng này trình bày về một số phân bố xác suất liên quan nhƣ: Phân bố Poisson, phân bố mũ. Những định nghĩa, định lý về xích Markov, phân loại trạng thái xích Markov, quá trình Markov gồm trƣờng hợp không gian trạng thái hữu hạn và không gian trạng thái vô hạn đếm đƣợc. 4 Chƣơng 2: Một số mô hình xếp hàng. Trình bày về một số mô hình xếp hàng cơ bản gồm: Mô hình hệ thống xếp hàng Markov đơn giản gồm mô hình xếp hàng Birth- and – Death tổng quát, trình bày cụ thể mô hình hàng đợi M/M/1, M/M/s và mô hình hàng đợi hữu hạn M/M/s/K. Mô hình chuỗi Markov nhúng trình bày tổng quát về chuỗi Markov nhúng cụ thể là mô hình hàng đợi M/G/1 và G/M/1. Chƣơng 3: Ứng dụng Chƣơng này tìm hiểu về một vài ứng dụng đơn giản của mô hình xếp hàng bao gồm: Mô phỏng một số mô hình bằng Matlab và ứng dụng của mô hình xếp hàng trong bài toán ra quyết định. Dù đã có nhiều cố gắng nhƣng do thời gian và khả năng có hạn nên các vấn đề trong luận văn vẫn chƣa đƣợc trình bày sâu sắc và không thể tránh khỏi những sai sót. Em rất mong đƣợc sự góp ý xây dựng của thầy cô và các bạn. Em xin chân thành cảm ơn! 5 CHƢƠNG 1 KIẾN THỨC CHUẨN BỊ Trong chƣơng này em xin trình bày về một sốphân bốxác suất liên quan là phân bố Poisson, phân bố mũvà một số định nghĩa, định lý về xích Markov gồm hai trƣờng hợp là không gian trạng thái hữu hạn và không gian trạng thái vô hạn đếm đƣợc để chuẩn bị kiến thức cho các chƣơng tiếp theo của khóa luận. 1.1 Phân bố Poisson và phân bố mũ 1.1.1 Phân bố Poisson Định nghĩa.Biến ngẫu nhiên rời rạc X nhận các giá trị từ 0, 1, 2, … gọi là phân phối Poisson với tham số λ nếu: 𝑒 −𝜆 𝜆 𝑘 𝑃 𝑋= 𝑘 = 𝑘! 𝑘 = 0, 1, 2, …. Ký hiệu: X ~ Poisson(λ) Kỳ vọng: ∞ 𝐸 𝑥 = 𝑘=0 Phƣơng sai : D(X) = 𝐸 𝑋− 𝜇 2 𝜆 𝑘 𝑒 −𝜆 𝑘 = 𝑘! ∞ 𝑘=1 𝜆 𝑘 𝑒 −𝜆 𝑘−1 ! =λ Do đó, chúng ta có thể viết: X ~ Poisson (µ). Mô hình Poisson: Giả sử chúng ta quan tâm đến số lần xảy ra của một sự kiện A trong một khoảng thời gian hoặc không gian liên tục có chiều dài w; với điều kiện là số lần xảy ra trong những khoảng không giao nhau là độc lập nhau, và xác suất xuất hiện A nhiều hơn một lần trong khoảng đó là rất bé. Hơn nữa, “cƣờng độ” xuất hiện A là không thay đổi, tức là số lần xuất hiện trung bình của A trong một khoảng chỉ phụ thuộc vào độ dài của khoảng đó. Với các điều kiện trên, nếu gọi X là BNN chỉ số lần xuất hiện A trong một khoảng chiều dài w thì ngƣời ta chứng minh đƣợc rằng X tuân theo luật phân phối Poisson với tham số λ = mw, trong đó m là một hằng số dƣơng chỉ “cƣờng độ” xuất hiện của A. 6 Thí dụ, số cuộc điện thoại gọi đến trong một phút tại một trạm nào đó; sốlỗi trên một trang giấy trong một quyển sách dầy; số đơn đặt hàng gửi tới một cơ sở trong một tháng, … Biến ngẫu nhiên chỉ số lần xuất hiện nêu trên đã đƣợc nhà toán học Simeon D. Poisson nghiên cứu và hình thành phân phối Poisson. Ngoài ra, phân phối Poisson còn đƣợc dùng để tính xấp xỉ phân phối nhịthức B(n;p) khi n lớn và p khá gần 0 hoặc gần 1. Định lý Poisson. Giả sử trong một dãy n phép thử độc lập, một biến cố A xuất hiện với xác suất 𝑝 𝑛 trong mỗi phép thử. Nếu khi 𝑛 → ∞ mà 𝑝 𝑛 → 0 sao cho 𝑛. 𝑝 𝑛 = 𝜆 (λ là một hằng số dƣơng) thì với mọi 𝑘 ∈ {0,1,2, … , 𝑛}, chúng ta có: lim 𝑛 →∞ 𝐶 𝑛𝑘 𝑝 𝑛𝑘 1 − 𝑝𝑛 𝑛−𝑘 𝜆 𝑘 −𝜆 = 𝑒 𝑘! Hệ quả: Nếu 𝑋~𝐵(𝑛, 𝑝), với 𝑛 > 30 và (𝑛𝑝 < 5 𝑕𝑎𝑦 𝑛 1 − 𝑝 < 5) thì chúng ta có thể xem như 𝑋~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝑛𝑝) Định lí: Cho hai biến ngẫu nhiên X và Y độc lập. Nếu 𝑋~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝜇) và 𝑌~𝑃𝑖𝑜𝑠𝑠𝑜𝑛 (𝜆) thì biến ngẫu nhiên 𝑋 + 𝑌~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝜇 + 𝜆). 1.1.2 Phân bố mũ: Định nghĩa: Hàm mật độ xác suất của một phân phối mũ có dạng như sau: −𝜆𝑥 𝑓 𝑥, 𝜆 = 𝜆𝑒 0 , 𝑥≥0 , 𝑥<0 Trong đó λ là tham số của phân bố, thƣờng đƣợc gọi là tham số tỉ lệ. Phân bố đƣợc hỗ trợ dựa trên khoảng [0; ∞). Nếu một biến ngẫu nhiên X có phân phối này, ta viết: 𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆). Đặc tả: 7 Một cách khác để định nghĩa hàm mật độ xác suất của một phân phối mũ nhƣ sau: 1 −𝑥/𝜆 𝑓 𝑥, 𝜆 = 𝜆 𝑒 0 , 𝑥≥0 , 𝑥<0 Trong đó 𝜆 > 0 là một tham số của phân bố và có thể đƣợc coi là nghịch đảo của tham số tỉ lệ đƣợc định nghĩa ở trên. Trong đặc tả, λ là một tham số sống sót theo nghĩa: nếu một biến ngẫu nhiên X là khoảng thời gian mà một hệthống sinh học hoặc cơ học M cho trƣớc sống sót đƣợc và 𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆)thì 𝐸 𝑋 = 𝜆. Nghĩa là khoảng thời gian sống sót kì vọng của M là λ đơn vị thời gian. Tính chất: + Giá trị trung bình và phương sai: Giá trị trung bình hay giá trị kì vọng của một biến ngẫu nhiên phân phối mũ X với tham số tỉ lệ λ đƣợc cho bởi công thức: 𝐸 𝑋 = Phƣơng sai của X là: 1 𝜆 1 𝜆2 + Tính không nhớ: Một tính chất quan trọng của phân phối mũ là nó không nhớ. Nghĩa là nếu một biến ngẫu nhiên T có phân phối mũ xác suất điều kiện của nó phải thỏa mãn: 𝑃(𝑇 > 𝑠 + 𝑡/𝑇 > 𝑡) = 𝑃 𝑇 > 𝑠 , ∀ 𝑠, 𝑡 ≥ 0 1.2. Xích Markov Xét một hệ nào đó đƣợc quan sát tại các thời điểm rời rạc 0,1,2,... Giả sử các quan sát đó là X0, X1, ..., Xn, ... Khi đó ta có một dãy các đại lƣợng ngẫu nhiên (ĐLNN) (Xn) trong đó Xn là trạng thái của hệ tại thời điểm n. Giả thiết rằng mỗi Xn, n = 0,1,... là một ĐLNN rời rạc. Ký hiệu E là tập giá trị của các (Xn). Khi đó E là một tập hữu hạn hay đếm đƣợc, các phần tử của nó đƣợc ký hiệu là i, j, k... Ta gọi E là không gian trạng thái của dãy. 8 Định nghĩa 1.2.1.Ta nói rằng dãy các ĐLNN (Xn) là một xích Markov nếu với mọi n1< ... < nk< nk+1 và với mọi i1, i2, ..., ik+1∈ E, ta có: 𝑃 𝑋 𝑛 𝑘+1 = 𝑖 𝑘+1 /𝑋 𝑛 1 = 𝑖1 , 𝑋 𝑛 2 = 𝑖2 , … , 𝑋 𝑛 𝑘 = 𝑖 𝑘 = 𝑃 𝑋 𝑛 𝑘+1 = 𝑖 𝑘+1 /𝑋 𝑛 𝑘 = 𝑖 𝑘 . Ta coi thời điểm nk+1 là tƣơng lai, nk là hiện tại còn n1, ..., nk -1 là quá khứ. Nhƣ vậy, xác suất có điều kiện của một sự kiện B nào đó trong tƣơng lai nếu biết hiện tại và quá khứ của hệ cũng giống nhƣ xác suất có điều kiện của B nếu chỉ biết trạng thái hiện tại của hệ. Đó chính là tính Markov của hệ. Đôi khi tính Markov của hệ còn phát biểu dƣới dạng: Nếu biết trạng thái hiện tại của hệ thì quá khứ và tƣơng lai độc lập với nhau. Giả sử 𝑃 𝑋 𝑚 +𝑛 = 𝑗/𝑋 𝑚 = 𝑖 là xác suất để xích tại thời điểm m ở trạng thái i sau n bƣớc, tại thời điểm m + n chuyển sang trạng thái j. Đây là một con số nói chung phụ thuộc vào i, j, m, n. Nếu đại lƣợng này không phụ thuộc m ta nói xích là thuần nhất. Ký hiệu: 𝑃𝑖𝑗 = 𝑃 𝑋 𝑛 +1 = 𝑗 /𝑋 𝑛 = 1 , 𝑃𝑖𝑗 𝑛 = 𝑃 𝑋 𝑚 +𝑛 = 𝑗/𝑋 𝑚 = 𝑖 . Ta gọi (𝑃𝑖𝑗 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau một bƣớc hay xác suất chuyển còn (𝑃𝑖𝑗 𝑛 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau n bƣớc. Chú ý rằng: 𝑗 ∈𝐸 𝑗 ∈𝐸 𝑃𝑖𝑗 = 1, 𝑃𝑖𝑗 𝑛 = 1. Phân bố của X0 đƣợc gọi là phân bố ban đầu. Ta ký hiệu 𝑢 𝑖 = 𝑃(𝑋0 = 𝑖). Định lý 1.2.1.Phân bố đồng thời của (X0, X1, ..., Xn) được hoàn toàn xác định từ phân bố ban đầu và xác suất chuyển. Cụ thể ta có: 𝑃 𝑋0 = 𝑖0 , 𝑋1 = 𝑖1 , … , 𝑋 𝑛 = 𝑖 𝑛 = 𝑢 𝑖0 𝑃𝑖0 𝑖1 … 𝑃𝑖 𝑛 −1 𝑖 𝑛 . Nhƣ vậy phân bố đồng thời của 𝑋0 , … , 𝑋 𝑛 đƣợc xác định bởi phân bố ban đầu và xác suất chuyển. Định lý 1.2.2.(Phương trình C - K (Chapman-Kolmogorov)): 𝑃𝑖𝑗 (n + m) = 𝑘 ∈𝐸 9 𝑃𝑖𝑘 (n) 𝑃 𝑘𝑗 (m). Trong trƣờng hợp E có d phần tử, ta ký hiệu𝑃 = (𝑃𝑖𝑗 ), 𝑃(𝑛) = (𝑃ij(n))là các ma trận vuông cấp 𝑑 × 𝑑. P đƣợc gọi là ma trận xác suất chuyển, P(n) đƣợc gọi là ma trận xác suất chuyển sau n bƣớc. Khi đó từ phƣơng trình Chapman - Kolmogorov tƣơng đƣơng với: 𝑃(𝑛 + 𝑚) = 𝑃(𝑛)𝑃(𝑚). Vì P = P(1) nên bằng quy nạp ta dễ thấy: 𝑃(𝑛) = 𝑃 𝑛 . Gọi 𝑢 𝑖 𝑛 = 𝑃 𝑋 𝑛 = 𝑖 . Ký hiệu vecto 𝑈 𝑛 = (𝑢1 (𝑛), … , 𝑢 𝑑 𝑛 )là vector hàng d - chiều mô tả phân bố của 𝑋𝑛, 𝑈 = 𝑢 0 = (𝑢1 , 𝑢2 , … , 𝑢 𝑑 )là vector hàng d - chiều mô tả phân bố ban đầu (Phân bố của𝑋0 ). Định lý 1.2.3.Ta có: 𝑈 𝑚 + 𝑛 = 𝑈 𝑚 𝑃 𝑛. Định nghĩa 1.2.2.Phân bố ban đầu 𝑈 = (𝑢 𝑖 ), 𝑖 ∈ 𝐸 được gọi là phân bố dừng nếu ta có 𝑈(𝑛) = 𝑈 với mọi n tức là 𝑢 𝑖 𝑛 = 𝑢 𝑖 ∀𝑖 ∈ 𝐸 , ∀𝑛. Khi đó dãy (𝑋 𝑛 ) có cùng phân bố. Từ định lý 1.2.3 ta suy ra 𝑈 = (𝑢 𝑖 ) là phân bố dừng nếu và chỉ nếu: • 1. 𝑢 𝑖 ≥ 0 và 𝑖∈𝐸 𝑢 𝑖 = 1, • 2. 𝑢 𝑖 = 𝑖∈𝐸 𝑢 𝑖 𝑃𝑖𝑗 ∀𝑗 ∈ 𝐴. Định lý 1.2.4.Giả sử (𝑋 𝑛 ) là xích Markov với không gian trạng thái E = 1,2,... với ma trận xác suất chuyển 𝑃 = (𝑃𝑖𝑗 ) và ma trận xác suất chuyển sau n bước là𝑃 𝑛 = 𝑃𝑖𝑗 (𝑛). Ta nói rằng xích có phân bố giới hạn nếu với mọi i, j ∈ E tồn tại giới hạn: lim 𝑃𝑖𝑗 𝑛 = 𝜋 𝑗 𝑛→ ∞ Giới hạn này không phụ thuộc i ∈ E. khi đó: • 1. 𝑗 ∈𝐸 𝜋 𝑗 ≤ 1 và πj = 𝑖 ∈𝐸 𝜋 𝑖 𝑃𝑖𝑗 . • 2. Hoặc πj = 0 với mọi j ∈ E, hoặc 𝑗 ∈𝐸 𝜋 𝑗 = 1. 10 • 3. Nếu 𝑗 ∈𝐸 𝜋 𝑗 = 1 thì U = (π1, π2, ...) là phân bố dừng và phân bố dừng là duy nhất. Nếu πj = 0 với mọi j ∈ E thì phân bố dừng không tồn tại. Ý nghĩa của phân bố giới hạn là nhƣ sau: Gọi 𝑢 𝑖 (𝑛) = 𝑃(𝑋 𝑛 = 𝑖). Ký hiệu vector 𝑈(𝑛) = (𝑢1 (𝑛), 𝑢2 (𝑛), . . . )là vector hàng d - chiều mô tả phân bố của 𝑋 𝑛 . Ta có: P(Xn = j) = 𝑗 ∈𝐸 𝑃(X0 = i)𝑃𝑖𝑗 (n). lim 𝑛→ ∞ 𝑃 𝑋 𝑛 = 𝑗 = 𝑗 ∈𝐸 𝑃 𝑋0 = 𝑖 lim 𝑛→ ∞ 𝑃𝑖𝑗 (𝑛) Do đó: = 𝑗 ∈𝐸 𝑃 𝑋0 = 𝑖 𝜋 𝑗 = 𝜋 𝑗 . Định nghĩa 1.2.3.Giả sử (𝑋 𝑛 ) là xích Markov với không gian trạng thái E ={1, 2, ...} với ma trận xác suất chuyển 𝑃 = 𝑃𝑖𝑗 (𝑛)và ma trận xác suất chuyển sau n bước là 𝑃(𝑛) = 𝑃𝑖𝑗 (𝑛). Ta nói rằng xích có phân bố giới hạn nếu với mọi i, j ∈ E tồn tại giới hạn: lim 𝑛→ ∞ 𝑃𝑖𝑗 (n) = πj . Giới hạn này không phụ thuộc i ∈ E và 𝑗 ∈𝐸 𝜋 𝑗 = 1. Nói cách khác, vecto giới hạn 𝜋 = (𝜋1 , 𝜋2 , . . . ) lập thành một phân bố xác suất trên E. Vậy phân bố 𝑈(𝑛) của 𝑋 𝑛 hội tụ tới phân bố giới hạn π. Khi n khá lớn ta có (𝑋 𝑛 = 𝑗) ≈ 𝜋𝑗. Theo định lý 1.1.4 nếu phân bố giới hạn tồn tại thì phân bố dừng cũng tồn tại và duy nhất. Hơn nữa hai phân bố này trùng nhau. Tuy nhiên điều ngƣợc lại không đúng tức là có những xích Markov có tồn tại phân bố dừng nhƣng không tồn tại phân bố giới hạn. Định lý 1.2.5.Cho (𝑋 𝑛 ) là xích Markov với không gian trạng thái hữu hạn E = {1,2,...,d} với ma trận xác suất chuyển sau n bước là 𝑃(𝑛) = (𝑃𝑖𝑗 (n)).Khi đó có tồn tại phân bố giới hạn π = (π1, ..., πd ) với 𝜋 𝑗 > 0 ∀𝑗 ∈ 𝐸 khi và chỉ khi xích là chính quy theo nghĩa: Tồn tại 𝑛0 sao cho: 𝑃𝑖𝑗 𝑛0 > 0, ∀𝑖, 𝑗 ∈ 𝐸. 1.2.1. Phân loại trạng thái xích Markov 11 Định nghĩa 1.2.4.Ta nói rằng trạng thái i đến được trạng thái j và ký hiệu là 𝑖 → 𝑗 nếu tồn tại 𝑛 ≥ 0 sao cho 𝑃𝑖𝑗 (𝑛) > 0. (Ta quy ước 𝑃𝑖𝑖 0 = 1, 𝑃𝑖𝑗 (0) = 0 nếu(i ≠ j)). Hai trạng thái i và j được gọi là liên lạc được nếu 𝑖 → 𝑗và 𝑗 → 𝑖. Trong trường hợp đó ta viết 𝑖 ↔ 𝑗. Định nghĩa 1.2.5.Xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ là liên lạc được. Có nghĩa là theo cách phân lớp trên thì E không thể phân hoạch thành các lớp con nhỏ hơn. Định nghĩa 1.1.6.Ký hiệu 𝑓𝑖𝑖 𝑛 là xác suất để hệ xuất phát từ i lần đầu tiên quay lại i ở thời diểm n. Nghĩa là: 𝑓𝑖𝑖 (n) = P(Xn = i, 𝑋 𝑛−1 ≠ i, ..., 𝑋1 ≠ i|X0 = i) và ký hiệu: 𝑓𝑖𝑖 ∗ = ∞ 𝑛=1 𝑓𝑖𝑖 (𝑛). Định lý 1.2.6.Trạng thái i là hồi quy khi và chỉ khi: ∞ 𝑛=1 𝑃𝑖𝑖 (𝑛)= ∞. Định lý 1.2.7.Nếu i ↔ j và j hồi quy thì i hồi quy. Chứng minh: Theo giả thiết tồn tại 𝑚, 𝑛 sao cho𝑃𝑖𝑖 (n) > 0, 𝑃𝑗𝑖 (m) > 0. Với mỗi số nguyên dƣơng h từ phƣơng trình C-P suy ra: 𝑃𝑖𝑖 (n + h + m) ≥ 𝑃𝑖𝑗 (n)𝑃𝑗𝑗 (h)𝑃𝑗𝑖 (m). Vậy: ∞ 𝑕=1 𝑃𝑖𝑖 (n + h + m) ≥ 𝑃𝑗 (n)𝑃𝑗𝑖 (m) ∞ 𝑕=1 𝑃𝑗𝑗 (h) = ∞. Vậy i hồi quy. Định lý 1.2.8. Ký hiệu 𝑄 𝑖𝑖 là xác suất để hệ xuất phát từ i quay lại i vô số lần, 𝑄 𝑖𝑗 là xác suất để hệ xuất phát từ i đi qua j vô số lần. Khi đó: • (i) Nếu i hồi quy thì 𝑄 𝑖𝑖 = 1, nếu i không hồi quy thì 𝑄 𝑖𝑖 = 0. 12 • (ii) Nếu i hồi quy 𝑖 ↔ 𝑗thì𝑄 𝑖𝑗 = 1. Nói riêng, với xác suất một hệ xuất phát từ i sau một số hữu hạn bước sẽ đi qua j. Định lý 1.2.9.Cho (𝑋 𝑛 ) là xích tối giản không hồi quy. Khi đó với mọi i, j: ∞ 𝑛=1 𝑃𝑖𝑗 𝑛 < ∞. Nói riêng lim 𝑛→ ∞ 𝑃𝑖𝑗 = 0 và xích không tồn tại phân bố dừng. Định lý 1.2.10.Cho (𝑋 𝑛 ) là xích tối giản hồi quy không có chu kỳ. Khi đó với mọi i, j ta có: lim 𝑛→ ∞ 𝑃𝑖𝑗 (n) = 1 𝜇𝑗 ở đó: µ𝑗 = ∞ 𝑘=1 𝑘𝑓𝑗𝑗 (k). Định nghĩa 1.2.7.Trạng thái hồi quy i được gọi là trạng thái hồi quy dương nếu 𝜇 𝑖 < ∞ và được gọi là trạng thái hồi quy không nếu µ 𝑖 = ∞. Định lý 1.2.11.Giả sử 𝑖 → 𝑗. Nếu i hồi quy dương thì j hồi quy dương. Nếu i hồi quy không thì j hồi quy không. Định lý 1.2.12.Giả sử (𝑋 𝑛 ) là xích tối giản không có chu kỳ với không gian trạng thái đếm được E. Khi đó sẽ xảy ra một trong ba khả năng sau đây: • 1)Mọi trạng thái là không hồi quy. Khi đó với mọi i, j ta có: 𝑙𝑖𝑚 𝑛→ ∞ 𝑃𝑖𝑗 (n) = 0. Xích không có phân bố dừng. • 2) Mọi trạng thái là hồi quy không. Khi đó với mọi i, j ta có: 𝑙𝑖𝑚 𝑛→ ∞ 𝑃𝑖𝑗 = 0. Xích không có phân bố dừng. • 3) Mọi trạng thái là hồi quy dương. Khi đó với mọi i, j, ta có: 13 𝑙𝑖𝑚 𝑛→ ∞ 𝑃𝑖𝑗 = πj> 0 và𝜋 = (𝜋1 , 𝜋2 , . . . ) là phân bố giới hạn (và cũng là phân bố dừng) của xích. Định lý 1.2.13.Giả sử (𝑋 𝑛 ) là xích tối giản không có chu kỳ với không gian trạng thái hữu hạn E = {1, 2, ..., d}. Khi đó mọi trạng thái đều hồi quy dương và xích có phân bố giới hạn 𝜋 = (𝜋1 , 𝜋2 , . . . , 𝜋 𝑑 ). Phân bố này cũng là phân bố dừng duy nhất của xích. Định lý 1.2.14.Giả sử 𝑋 𝑛 là xích tối giản với không gian trạng thái E đếm được. Khi đó: • 1.Với mỗi 𝑖, 𝑗 ∈ 𝐸: 𝑛 𝑘=1 𝑙𝑖𝑚 𝑛→ ∞ 𝑛−1 1 𝑃𝑖𝑗 (𝑘) = . 𝜇𝑗 1 Nói cách khác dãy 𝑃𝑖𝑗 𝑛 hội tụ theo trung bình Cesaro tới πj = không phụ thuộc 𝜇𝑖 i. • 2.Dãy 𝜋 = (𝜋 𝑗 ) thoả mãn: a) ∞ 𝑗 =1 𝜋 𝑗 ≤ 1, b) 𝜋 𝑗 = ∞ 𝑖=1 𝜋 𝑖 𝑃𝑖𝑗 . Định lý 1.2.15.Cho (𝑋 𝑛 ) là xích Markov tối giản. Khi đó: • 1. Nếu E hữu hạn có d phần tử thì (𝜋1 , . . . , 𝜋 𝑑 ) là phân bố dừng duy nhất. • 2. Chỉ có các khả năng sau: a) Mọi trạng thái của E là không hồi quy b) Mọi trạng thái của E là hồi quy không c) Mọi trạng thái của E là hồi quy dương. • 3. Nếu E là vô hạn đếm được thì xích có phân bố dừng khi và chỉ khi mọi trạng thát của E là hồi quy dương. Trong trường hợp này phân bố dừng là duy nhất. 1.3. Quá trình Markov 14 Xét họ các ĐLNN rời rạc (𝑋 𝑡 ), t ≥ 0 với tập chỉ số t là các số thực không âm 𝑡 ∈ [0, ∞). Ký hiệu 𝐸 = 𝑋 𝑡 Ω là tập giá trị của 𝑋 𝑡 . Khi đó E là một tập hữu hạn hay đếm đƣợc, các phần tử của nó đƣợc ký hiệu 𝑙à 𝑖, 𝑗, 𝑘. . .. Ta gọi (𝑋 𝑡 ) là một quá trình ngẫu nhiên với không gian trạng thái E . Định nghĩa 1.3.1. Ta nói rằng (𝑋 𝑡 ) là một quá trình Markov nếu với mọi 𝑡1 < . . . < 𝑡 𝑘 < 𝑡và với mọi 𝑖1 , 𝑖2 , . . . 𝑖 𝑛 , 𝑖 ∈ 𝐸 ∶ P{Xt = i|𝑋 𝑡 1 = i1, 𝑋 𝑡 2 = i2..., 𝑋 𝑡 𝑘 = ik} = P{Xt = i|𝑋 𝑡 𝑘 = ik}. Nhƣ vậy, xác suất có điều kiện của một sự kiện B nào đó trong tƣơng lai nếu biết hiện tại và quá khứ của hệ cũng giống nhƣ xác suất có điều kiện của B nếu chỉ biết trạng thái hiện tại của hệ. Đó chính là tính Markov của hệ. Đôi khi tính Markov của hệ còn phát biểu dƣới dạng: "Nếu biết trạng thái hiện tại 𝑋𝑡 của hệ thì quá khứ 𝑋 𝑢 ,𝑢 < 𝑡 và tƣơng lai 𝑋 𝑠 , 𝑠 > 𝑡 là độc lập với nhau." Giả sử: P{𝑋 𝑡+𝑠 = j|Xs = i} là xác suất để xích tại thời điểm s ở trạng thái i sau một khoảng thời gian t, tại thời điểm t + h chuyển sang trạng thái j. Đây là một con số nói chung phụ thuộc vào i, j, t, s. Nếu đại lƣợng này không phụ thuộc s ta nói xích là thuần nhất. Ký hiệu: 𝑃𝑖𝑗 (t) = P{𝑋 𝑡+𝑠 = j|Xs = i}. Ta gọi 𝑃𝑖𝑗 𝑡 là xác suất chuyển của hệ từ trạng thái i sang trạng thái j sau một khoảng thời gian t . Ký hiệuP(t) = (𝑃𝑖𝑗 (t), i, j → E). P(t) là một ma trận hữu hạn hay vô hạn chiều. Chú ý rằng: • i)𝑃𝑖𝑗 (t) ≥ 0. • ii) 𝑗 ∈𝐸 𝑃𝑖𝑗 (𝑡)= 1. Phân bố của 𝑋0 đƣợc gọi là phân bố ban đầu. Ta ký hiệu 𝑢 𝑖 = 𝑃(𝑋0 = 𝑖). Định lý 1.3.1.Phân bố hữu hạn chiều của quá trình (𝑋 𝑡 ) được hoàn toàn xác định từ phân bố ban đầu và xác suất chuyển. Cụ thể với 𝑡1 < 𝑡2 < . . . < 𝑡 𝑛 phân bố đồng thời của (𝑋 𝑡 1 , ..., 𝑋 𝑡 𝑛 ) được tính theo công thức sau: 15 P(𝑋 𝑡 1 = i1, ..., 𝑋 𝑡 𝑛 = in) = = 𝑖 ∈𝐸 𝑢 𝑖 𝑃𝑖𝑖 1 𝑡1 𝑃𝑖1 𝑖2 𝑡2 − 𝑡1 … 𝑃𝑖 𝑛 −1 𝑖 𝑛 (𝑡 𝑛 − 𝑡 𝑛 −1 ). Định lý 1.3.2.( Phương trình Chap - Kolmogorov): 𝑃𝑖𝑗 (t + s) = 𝑘 ∈𝐸 𝑃𝑖𝑘 (𝑡)𝑃 𝑘𝑗 (𝑠) . 1.3.1. Trƣờng hợp không gian trạng thái hữu hạn Giả sử E = {1, 2,..., d}. Khi đó từ phƣơng trình C - K P(t), t > 0 là một họ các ma trận thoả mãn đẳng thức sau: 𝑃(𝑡 + 𝑠) = 𝑃(𝑡)𝑃(𝑠). Nói cách khác họ (P(t), t > 0) lập thành một nửa nhóm các ma trận. Từ nay về sau ta sẽ luôn giả thiết thêm rằng: 1.𝑃𝑖𝑗 (0) = δij. 2.lim 𝑛→ ∞ 𝑃𝑖𝑗 (𝑡)= δij. Ở đây 𝛿 𝑖𝑗 là ký hiệu Kronecke: δij = 1 0 𝑘𝑕𝑖 𝑖 = 𝑗 𝑘𝑕𝑖 𝑖 ≠ 𝑗 Định lý 1.3.3.Hàm ma trận P(t) là một hàm liên tục và tồn tại: 𝑃′ (0) = 𝑙𝑖𝑚 𝑕→ 0+ 𝑃 𝑡 −𝐼 𝑕 . Định lý 1.3.4.Cho quá trình Markov với nửa nhóm P(t), t > 0 các xác suất chuyển. Gọi A là ma trận cực vi của nửa nhóm. Khi đó ta có: 𝑃′ 𝑡 = 𝑃 𝑡 𝐴 , ↔ 𝑃𝑖𝑗 ′ = 𝑘 ≠𝑗 𝑃𝑖𝑘 𝑡 𝑎 𝑘𝑗 − 𝑃𝑖𝑗 𝑦 𝑎 𝑗 . (1.3.1) và 𝑃′ 𝑡 = 𝐴𝑃(𝑡) , ↔ 𝑃′ 𝑖𝑗 𝑡 = 𝑘 ≠𝑖 𝑃 𝑘𝑗 𝑎 𝑖𝑘 − 𝑃𝑖𝑗 (𝑦)𝑎 𝑖 . 16 (1.3.2) với𝑎 𝑖𝑗 là cƣờng độ chuyển từ trạng thái i sang trạng thái j và 𝑎 𝑖 là cƣờng độ thoát khỏi trạng thái i của hệ. Phƣơng trình (1.3.1) gọi là phƣơng trình thuận và phƣơng trình (1.3.2) gọi là phƣơng trình ngƣợc Kolmogorov. Định lý 1.3.5.Cho quá trình Markov tối giản (𝑋 𝑡 ) với không gian trạng thái E = 1, 2,..., d hữu hạn và ma trận xác suất chuyểnP(t) = 𝑃𝑖𝑗 (t). Khi đó với mỗi 𝑖, 𝑗 ∈ 𝐸 tồn tại giới hạn hữu hạn: 𝑙𝑖𝑚 𝑃𝑖𝑗 𝑡 = 𝜋 𝑗 𝑡→ ∞ chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó 𝜋 = (𝜋1 , 𝜋2 , . . . , 𝜋 𝑑 ) là phân bố xác suất duy nhất thoả mãn phương trình: 𝜋 = 𝜋𝑃(𝑡), ∀𝑡 > 0. 1.3.2. Trƣờng hợp không gian trạng thái vô hạn đếm đƣợc Định lý 1.3.6. (1)Với mọi i ≠ j, giới hạn: 𝑃𝑖𝑗 ′ (0) = lim 𝑡→ ∞ 𝑃𝑖𝑗 (𝑡) = 𝑎 𝑖𝑗 𝑡 luôn tồn tại hữu hạn. (2)Với mỗi i giới hạn: 𝑃′ 𝑖𝑖 (0) = lim 𝑡→ ∞ 𝑃 𝑖𝑗 𝑡 −1 𝑡 = 𝑎 𝑖𝑖 = − 𝑎 𝑖 tồn tại nhưng có thể bằng vô cùng. Định lý 1.3.7.Cho quá trình Markov với P(t) = (𝑃𝑖𝑗 (t))là họ các ma trận xác suất chuyển. Gọi A là ma trận cực vi của quá trình. Khi đó ta có: 𝑃′ (t) = P(t)A, ↔ 𝑃𝑖𝑗 ′ (t) = 𝑘 ≠𝑗 𝑃𝑖𝑘 𝑡 𝑎 𝑘𝑗 − 𝑃𝑖𝑗 (𝑦)𝑎 𝑗 . và 𝑃′ (t) = AP(t), 17 (1.3.3) ↔ 𝑃𝑖𝑗 ′ (t) = 𝑘 ≠𝑖 𝑎 𝑖𝑘 𝑃 𝑘𝑗 − 𝑃𝑖𝑗 (𝑦)𝑎 𝑖 . (1.3.4) với𝑎 𝑖𝑗 là cường độ chuyển từ trạng thái i sang trạng thái j và ai là cường độ thoát khỏi trạng thái i của hệ. Phương trình (1.3.3) gọi là phương trình thuận và phương trình (1.3.4) gọi là phương trình ngược Kolmogorov. Định lý 1.3.8.Cho quá trình Markov tối giản (𝑋 𝑡 ) với không gian trạng thái E = 1, 2,..., đếm được và ma trận xác suất chuyểnP(t) = 𝑃𝑖𝑗 (t). Khi đó, với mỗi 𝑖, 𝑗 ∈ 𝐸 tồn tại giới hạn hữu hạn: 𝑙𝑖𝑚 𝑡→ ∞ 𝑃𝑖𝑗 (𝑡)= πj chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó giới hạn 𝜋 = (𝜋1 , 𝜋2 , . . . , ) hoặc là tất cả bằng không: 𝜋𝑗 = 0 ∀𝑗 ∈ 𝐸 hoặc là tất cả dương và lập thành một phân bố xác suất. Phân bố đó được gọi là phân bố giới hạn của quá trình: π j> 0 ∀j ∈ E, 𝑗 𝜋 𝑗 = 1. CHƢƠNG 2: MỘT SỐ MÔ HÌNH XẾP HÀNG 2.1 Khái niệm và phân loại quá trình xếp hàng 18 2.1.1 Khái niệm quá trình xếp hàng Mô hình tổng quát của lý thuyết xếp hàng là khách hàng đến ở một thời điểm ngẫu nhiên nào đó và yêu cầu đƣợc phục vụ theo một loại nào đó. Giả thiết thời gian phục vụ có thể ngẫu nhiên. Đặt 𝑡 𝑛 là khoảng thời gian giữa hai lần đến của khách hàng thứ 𝑛 và thứ 𝑛 + 1. Ta giả định rằng tất cả các 𝑡 𝑛 (𝑛 ≥ 1) là độc lập có cùng phân bố. Vì vậy việc đến của khách hàng tạo thành một hàng kế tiếp nhau với tốc độ đến là 𝜆 = 1 . Ta 𝐸(𝑡 1 ) gọi quá trình 𝑡 𝑛 , 𝑛 = 1,2, … là quá trình đến. Khách hàng đến hệ thống yêu cầu các server của hệ thống phục vụ. Ta giả sử rằng khách hàng thứ 𝑛 cần một thời gian phục vụ là (𝑛 ≥ 1), tất cả các 𝑠 𝑛 độc lập và có cùng phân bố. Quá trình 𝑡 𝑛 ; 𝑛 = 1,2, … đƣợc gọi là quá trình phục vụ. Ta cũng giả thiết rằng các thời gian đến trung gian độc lập với thời gian phục vụ. Quá trình xếp hàng đƣợc phân loại dựa vào tiêu chí sau: 1) Phân bố của quá trình đến (input process) 𝑙 𝑞 (𝑡) 𝑡≥0 2) Phân bố của thời gian phục vụ (service distribution) 𝑠 𝑛 ; 𝑛 = 1,2, … 3) Nguyên tắc phục vụ: Các khách hàng đến đƣợc sắp xếp vào hàng đợi đến lƣợt đƣợc phục vụ. Để đơn giản ta giả thiết chỉ có một hàng. Tuy nhiên trong nhiều trƣờng hợp có thể mở rộng cho nhiều hàng cùng hoạt động song song. Nếu độ dài hàng có đặt ngƣỡng thì các đơn vị đến hàng khi hàng đầy vƣợt ngƣỡng sẽ bị loại. Các khách hàng đƣợc chọn để phục vụ theo nguyên tắc “đến trƣớc phục vụ trƣớc” (FIFO), nghĩa là phục vụ cho khách hàng nào đứng đầu hàng. 4) Cơ cấu phục vụ: Một phƣơng tiện phục vụ bao gồm một hay nhiều Server. Các Server có thể kết nối thành chuỗi vì thế mỗi yêu cầu phục vụ đƣợc phục vụ theo nhiều cách hoặc lần lƣợt hoặc song song. 2.1.2 Các yếu tố cơ bản của hàng đợi a. Bố trí vật lí của hệ thống Hệ thống hàng đợi có một số dạng bố trí vật lí (phisical layout)     Một kênh phục vụ, một loại dịch vụ (Single Channel – Single Server) Một kênh phục vụ, nhiều loại dịch vụ (Single Channel – Multi Server) Nhiều kênh phục vụ, một loại dịch vụ (Multi Channel – Single Server) Nhiều kênh phục vụ, một loại dịch vụ (Multi Channel – Multi Server) 19 Các kênh phục vụ đƣợc hiểu là những thiết bị kỹ thuật hoặc con ngƣời hoặc những tổ hợp các thiết bị kỹ thuật và con ngƣời đƣợc tổ chức quản lí một cách thích hợp nhằm phục vụ các yêu cầu / các tín hiệu đến hệ thống. Chẳng hạn, ở các trạm điện thoại tự động, kênh phục vụ là các đƣờng dây liên lạc cùng các thiết bị kĩ thuật khác phục vụ cho việc đàm thoại. b. Nguyên tắc phục vụ Nguyên tắc phục vụ (hay nội quy) của hệ thống là cách thức nhận các yêu cầu vào các kênh phục vụ. Nguyên tắc phục vụ cho biết trƣờng hợp nào thì yêu cầu đƣợc nhận vào phục vụ và cách thức phân bố các yêu cầu vào các kênh nhƣ thế nào. Đồng thời nguyên tắc phục vụ cũng cho biết trong trƣờng hợp nào yêu cầu bị từ chối hoặc phải chờ và giới hạn của thời gian chờ. Một số nguyên tắc phục vụ thƣờng đƣợc áp dụng trong các hệ thống hàng đợi là FIFO (First in first out), LIFO (Last in first out), FCFS (First come first server), có ƣu tiên, không ƣu tiên, … c. Các phân phối xác suất của các dòng tín hiệu, dòng phục vụ Số tín hiệu đến trong một khoảng thời gian cũng nhƣ thời gian phục vụ từng tín hiệu nói chung là những biến ngẫu nhiên, và do đó, chúng tuân theo các quy luật phân phối xác suất. Các quy luật phân phối xác suất này đƣợc thiết lập căn cứ vào số liệu thực nghiệm thu thập từ các quan sát, thí nghiệm, hay từ cơ sở dữ liệu sẵn có. Đối với dòng tín hiệu đầu vào, thông thƣờng chúng ta giả sử rằng số tín hiệu đến trong vòng một khoảng thời gian nào đó đƣợc ấn định trƣớc (1phút, 3 phút, 5 phút, 30 phút, …) tuân theo luật phân phối Poisson 𝑃(𝜆). Ở đây tham số λ đặc trƣng cho số tín hiệu đến (trung bình) trong khoảng thời gian trên. Ví dụ, số khách vào siêu thị (trung bình) là 100 ngƣời trong 1 giờ. Có nghĩa là, số khách vào siêu thị là biến ngẫu nhiên 𝑋 có phân phối Poisson với λ = 100. Hoặc, với số cuộc gọi (trung bình) đến tổng đài trong vòng 1 phút là 3 (tín hiệu) thì có 𝑋~𝑃(3). Một cách chính xác hơn, trong những trƣờng hợp trên, ta có dòng tín hiệu đến là dòng Poisson dừng (còn gọi là dòng tối giản) với các tính chất trên nhƣ sau: Tính không hậu quả: Một dòng tín hiệu có tính không hiệu quả nếu xác suất hiện một số tín hiệu nào đó trong một khoảng thời gian nhất định không phụ thuộc vào việc đã có bao nhiêu tín hiệu đã xuất hiện và xuất hiện nhƣ thế nào trƣớc khpangr thời gian đó. 20
- Xem thêm -

Tài liệu liên quan