Luận án tiến sĩ Toán học: Một số dạng hàng đợi và các nguyên lý xử lý

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:174

Thêm vào BST

Báo xấu

27
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của luận án nhằm nghiên cứu các tính chất của các quá trình trạng thái tại nút mạng và mạng hàng đợi; Xác định các tham số hiệu năng của mạng; Xác định dòng job luân chuyển trong mạng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Toán học: Một số dạng hàng đợi và các nguyên lý xử lý

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ----------------------------------- NGUYỄN TRUNG DŨNG MỘT SỐ DẠNG HÀNG ĐỢI VÀ CÁC NGUYÊN LÝ XỬ LÝ LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ---------------------------------- NGUYỄN TRUNG DŨNG MỘT SỐ DẠNG HÀNG ĐỢI VÀ CÁC NGUYÊN LÝ XỬ LÝ Chuyên ngành: Cơ sở toán học cho tin học Mã số : 9460110 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS.NCVCC Nguyễn Hồng Hải 2. TS Trần Quang Vinh Hà Nội - 2018
i LỜI CAM ĐOAN Tôi xin cam đoan các công trình nghiên cứu trong luận án này là của cá nhân tôi. Các kết quả được nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác. Các dữ liệu tham khảo được trích dẫn đầy đủ. Tác giả Nguyễn Trung Dũng
ii LỜI CÁM ƠN Luận án được nghiên cứu thực hiện tại Viện Công nghệ thông tin - Viện Khoa học Công nghệ Quân sự/BQP và Bộ tư lệnh 86/BQP, dưới sự hướng dẫn khoa học của TS.Nguyễn Hồng Hải và TS.Trần Quang Vinh. Lời đầu tiên nghiên cứu sinh xin bày tỏ lòng biết sâu sắc tới thầy giáo Nguyễn Hồng Hải và thầy giáo Trần Quang Vinh, những người thầy đã giúp đỡ và đưa nghiên cứu sinh đến lĩnh vực nghiên cứu này. Các thầy đã tận tình giảng dạy, hướng dẫn, động viên, khuyến khích và chỉ dẫn giúp nghiên cứu sinh tiếp cận và đạt được thành công trong học tập, nghiên cứu và hoàn thành bản luận án này. Nghiên cứu sinh xin bày tỏ lòng biết ơn tới Đảng ủy, chỉ huy Viện Công nghệ thông tin - Viện KH-CN Quân sự; Đảng ủy, chỉ huy BTL 86; các cán bộ Phòng Đào tạo - Viện KH-CN Quân sự; cán bộ phòng Toán ứng dụng - Viện Công nghệ thông tin - Viện KH-CN Quân sự; cán bộ phòng Phần mềm và CSDL – BTL 86 đã nhiệt tình ủng hộ, động viên kịp thời và hết lòng giúp đỡ nghiên cứu sinh trong suốt quá trình học tập và nghiên cứu tại đơn vị. Cuối cùng nghiên cứu sinh xin chân thành cảm ơn toàn thể gia đình, những người luôn ở bên cạnh và dành cho nghiên cứu sinh những tình cảm và chia sẻ động viên giúp đỡ tinh thần những lúc khó khăn trong cuộc sống, cũng như trong quá trình học tập và nghiên cứu. Tác giả Nguyễn Trung Dũng
iii MỤC LỤC Trang DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... V DANH MỤC CÁC BẢNG ................................................................................... VIII DANH MỤC CÁC HÌNH VẼ ................................................................................ IX CHƯƠNG 1. MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LÝ THUYẾT HÀNG ĐỢI VÀ MẠNG HÀNG ĐỢI ............................................................................................. 5 1.1. Một số khái niệm xác suất có liên quan ............................................... 6 1.1.1. Biến ngẫu nhiên ............................................................................................ 6 1.1.2. Hàm phân phối xác suất của biến ngẫu nhiên ........................................... 6 1.1.3. Các đặc trưng của biến ngẫu nhiên ............................................................. 7 1.1.4. Một số đại lượng ngẫu nhiên quan trọng (thường dùng).......................... 8 1.2. Quá trình Markov................................................................................ 10 1.2.1. Các định nghĩa và một số tính chất ban đầu ................................... 10 1.2.2. Xích Markov thời gian rời rạc ........................................................ 11 1.3. Lý thuyết hàng đợi và mạng hàng đợi ............................................... 14 1.3.1. Hàng đợi ......................................................................................................14 1.3.2. Mạng hàng đợi ............................................................................................18 1.4. Tình hình nghiên cứu trong nước và ngoài nước về mạng hàng đợi .. 27 CHƯƠNG 2. MẠNG ĐA LỚP TỔNG QUÁT - THUẬT TOÁN PHÂN RÃ VÀ TỔNG HỢP .........................................................................................................41 2.1. Phân rã mạng hàng đợi tổng quát thành các mạng thành phần..... 42 2.2. Tổng hợp mạng hàng đợi tổng quát theo các mạng thành phần .... 46 2.2.1. Luân chuyển job trong mạng hàng đợi tổng quát G/G/J trong bối cảnh job luân chuyển giữa các mạng thành phần ........................................................47 2.2.2. Xét trường hợp riêng – trong mạng chập không có sự luân chuyển dòng job giữa các mạng thành phần..............................................................................65 2.3. Về một mô hình mạng hàng đợi cụ thể .............................................. 68 2.3.1. Tập các mạng thành phần ..........................................................................69 2.3.2. Dòng job luân chuyển trong mạng hàng đợi tại bước n (n≥1) ...............70 2.4. Xây dựng chương trình tính toán lưu lượng dòng job luân chuyển
iv trong mạng hàng đợi .............................................................................. 72 2.4.1. Nêu bài toán ................................................................................................73 2.4.3. Sơ đồ khối thuật toán tổng hợp mạng hàng đợi.......................................75 2.4.4. Bộ số liệu thử nghiệm ................................................................................76 2.4.5. Kết quả tính toán lưu lượng dòng job luân chuyển trong mạng ............76 CHƯƠNG 3. ĐÁNH GIÁ QUÁ TRÌNH TRẠNG THÁI CỦA MẠNG HÀNG ĐỢI DẠNG TỔNG QUÁT ........................................................................86 3.1. Trạng thái và phương trình chuyển trạng thái của mạng ............... 88 3.1.1. Các định nghĩa, ký hiệu .............................................................................89 3.1.2. Phương trình chuyển trạng thái của nút mạng .........................................90 3.1.3. Phân phối xác suất chuyển trạng thái của nút mạng ...............................92 3.2. Phân phối và tính chất của quá trình trạng thái .............................. 94 3.2.1. Phân phối xác suất của trạng thái tại nút mạng sau một bước ...............94 3.2.2. Phân phối xác suất của trạng thái tại các nút mạng sau k bước............96 3.2.3. Điều kiện để quá trình trạng thái nút mạng và mạng hàng đợi là Markov 97 3.3. Ứng dụng để tính các đặc trưng của mạng hàng đợi ..................... 107 3.3.1. Trung bình số job có trong nút mạng .....................................................107 3.3.2. Thông lượng của nút mạng......................................................................107 3.3.3. Xác suất vượt ngưỡng tại nút mạng........................................................107 3.3.4. Trung bình số job có trong mạng hàng đợi ............................................108 3.3.5. Thông lượng của mạng hàng đợi ............................................................108 3.3.6. Một phương pháp phân chia dòng job vào mạng hàng đợi ..................108 KẾT LUẬN ...............................................................................................................114 DANH MỤC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ..........................116 TÀI LIỆU THAM KHẢO .....................................................................................117 Phụ lục 1. Ma trận xác suất định tuyến của các mạng thành phần và ma trận xác suất chuyển job tại nút mạng giữa các mạng thành phần………………..P1 Phụ lục 2. Chương trình phần mềm tính toán lưu lượng dòng job luân chuyển trong mạng hàng đợi tổng quát……………………………………………..P12
v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 1. Danh mục các ký hiệu j ( n ) : A(1) Số job thuộc loại 1 từ bên ngoài vào nút j trong khoảng thời gian [ n−1 , n ] . j ( n ) : A(2) Số job thuộc loại 2 từ bên ngoài vào nút j trong khoảng thời gian [ n−1 , n ] . Ai(,hj,l ) ( t ) : Biến cố job chuyển từ nút i sang nút j trong mạng thành phần ( h, l ) tại thời điểm t . Ai , j ( t ) : Biến cố job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t . aic ( n ) : Lưu lượng dòng job đến nút i của mạng thành phần c tại bước n . ai (n) : Véc tơ chỉ lưu lượng dòng job đến nút i trong mạng hàng đợi c tại bước n . bic ( n ) : Lưu lượng dòng job tại nút i trong mạng thành phần c tại bước n . bi (n) : Véc tơ chỉ lưu lượng dòng job tại nút i trong mạng hàng đợi tại bước n . di ( n ) : Lưu lượng dòng job từ nút i ra khỏi mạng hàng đợi tại bước n . Ej : Không gian trạng thái của nút j . L: Tập tất cả các mạng thành phần của mạng hàng đợi. Li : Tập các mạng thành phần có chứa nút i . Nj : Kích thước của hàng đợi tại nút j của mạng. P(t ) : Ma trận xác suất định tuyến của mạng chập tại thời điểm t . P c ( n) : Ma trận xác suất định tuyến của mạng thành phần c tại bước n . pi , j (t ) : Xác suất định tuyến job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t .
vi pic, j (n) : Xác suất định tuyến job chuyển từ nút i sang nút j trong mạng thành phần c tại bước n . Qi ( n ) : Ma trận xác suất chuyển trạng thái của quá trình trạng thái tại nút j tại thời điểm  n . Si ( n ) : Ma trận xác suất chuyển job trong nút i giữa các mạng thành phần tại bước n . Sic,d (n) : Xác suất chuyển job trong nút i từ mạng thành phần c sang mạng thành phần d tại bước n . Si ( n ) : Ma trận xác suất chuyển job trong nút i tại bước n . sic (n) : Xác suất chuyển job từ nút i trong mạng thành phần c ra ngoài mạng hàng đợi c tại bước n . si (n) : Véc tơ xác suất chuyển job từ nút i ra ngoài mạng hàng đợi c tại bước n . vic ( n ) : Lưu lượng dòng job từ bên ngoài vào trong mạng thành phần c tại nút i tại bước n . vi (n) : Véc tơ chỉ lưu lượng dòng job từ ngoài mạng hàng đợi vào nút i trong mạng hàng đợi tại bước n . X ( n ) : Trạng thái mạng hàng đợi tại thời điểm  n . X j ( n ) : Số job có trong nút j tại thời điểm  n và được gọi là trạng thái nút j tại thời điểm  n . ij ( n ) : Số job từ nút i chuyển sang nút j tại thời điểm  n . 2. Danh mục các chữ viết tắt DP: Ưu tiên phục vụ theo cơ chế động (Dynamic Priorities). FCFS: Job vào trước được phục vụ trước (First-Come-First-Served). FIFO: Job vào trước ra trước (First-In-First-Out) GPSS: Hệ thống mô phỏng các sự kiện rời rạc, được Geoffrey Gordon
vii (IBM), phát triển chính từ những năm 1960 (General Purpose Simulation System). HTTP: Giao thức truyền tải siêu văn bản (HyperText Transfer Protocol). IS: Số lượng server vô hạn (Infinite Server) JMT: Công cụ dùng để mô phỏng mạng hàng đợi sử dụng ngôn ngữ lập trình Java (Java Modelling Tools). Job: Công việc, Khách hàng (Job). LCFS: Job vào sau được phục vụ trước (Last-Come-First-Served). OSI: Mô hình tham chiếu cho việc kết nối các hệ thống mở (Reference model for Open Systems Interconnection). RR: Thời gian phục vụ job của hàng đợi được phân chia thành các đoạn thời gian và nếu tại cuối một đoạn thời gian mà job chưa được phục vụ xong, khi đó job sẽ quay về hàng chờ để được phục vụ tiếp (Round Robin). SIRO: Job được lựa chọn phục vụ ngẫu nhiên (Service-In-Random- Order).
viii DANH MỤC CÁC BẢNG Trang Bảng 2.1. Chỉ số hóa các mạng thành phần………………………………....69 Bảng 2.2. Lưu lượng dòng job luân chuyển trong mạng hàng đợi tổng quát....76 Bảng 2.3. Lưu lượng dòng job luân chuyển trong các mạng thành phần……..77 Bảng 2.4. Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại các nút.....79
ix DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Cấu trúc hàng đợi……………………...………………………….15 Hình 2.1. Dòng job luân chuyển trong mạng tổng quát……………………..44 Hình 2.2. Dòng job luân chuyển trong mạng thành phần……………………46 Hình 2.3. Sơ đồ khối thuật toán tổng hợp mạng hàng đợi…………………...75 Hình 2.4. Biểu đồ lưu lượng dòng job trong mạng hàng đợi và ra khỏi mạng hàng đợi sau một bước tại nút 1……………………………………………..77 Hình 2.5. Biểu đồ lưu lượng dòng job trong mạng thành phần (1,1) và ra khỏi mạng (1,1) sau một bước…………………………………………………….79 Hình 2.6. Biểu đồ lưu lượng dòng job có trong mạng thành phần (1,1) và ra khỏi mạng (1,1) sau một bước tại nút 1……………………………………...84 Hình 3.1. Mô hình mạng hàng đợi dạng tổng quát G/G/J…………………...87 Hình 3.2. Lược đồ chuyển trạng thái của hàng đợi M/M/1/∞-FCFS………...92 Hình 3.3. Lược đồ chuyển trạng thái của quá trình trạng thái tại nút mạng…94
1 MỞ ĐẦU Cùng với sự phát triển của khoa học kỹ thuật, nhiều mạng hàng đợi đã ra đời và được ứng dụng trong thực tế đời sống xã hội như hệ thống mạng viễn thông, hệ thống mạng máy tính, hệ thống dây chuyền sản xuất… Việc nghiên cứu, đánh giá hiệu năng hoạt động của các hệ thống này là một trong những bài toán quan trọng và phức tạp. Để nghiên cứu, đánh giá hiệu năng hoạt động của hệ thống, chúng ta có thể áp dụng nhiều công cụ toán học khác nhau và một trong công cụ toán học quan trọng có thể sử dụng là lý thuyết hàng đợi và lý thuyết mạng hàng đợi. Nghiên cứu về mạng hàng đợi, hai trong số các lớp bài toán vừa có ý nghĩa khoa học vừa có ý nghĩa thực tiễn đã và đang được nhiều tác giả trên thế giới quan tâm là lớp bài toán nghiên cứu quá trình trạng thái của các nút mạng, quá trình trạng thái của mạng hàng đợi và lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi. Các kết quả nghiên cứu của các tác giả trong và ngoài nước từ trước đến nay nhằm xác định phân phối xác suất của trạng thái mạng hàng đợi và các tham số hiệu năng khác của mạng… chỉ đạt được với mạng hàng đợi thỏa mãn điều kiện như dòng vào là dòng Poisson, thời gian phục vụ của các nút mạng các biến ngẫu nhiên có phân phối mũ, mạng hàng đợi hoạt động ở trạng thái cân bằng. Đối với mạng hàng đợi với giả thiết dòng vào tổng quát, thời gian phục vụ của các nút mạng là các biến ngẫu nhiên có phân phối bất kỳ, các tác giả mới dừng lại ở việc xác định phân phối xác suất gần đúng của trạng thái mạng hàng đợi trong một số điều kiện nhất định. Có nhiều vấn đề kể cả từ thực tiễn cũng như từ lý thuyết đòi hỏi phải xét những mô hình mạng hàng đợi với những giả thiết rộng rãi hơn được đặt lên các cấu trúc của mạng hàng đợi như: giả thiết về dòng job từ bên ngoài vào mạng
2 phục vụ; giả thiết về thời gian phục vụ, giả thiết về cơ chế ưu tiên phục vụ; giả thiết về cơ chế xây dựng ma trận xác suất định tuyến trong mạng hàng đợi… * Xuất phát từ những vấn đề trên, luận án “Một số dạng hàng đợi và các nguyên lý xử lý” đặt ra mục tiêu: Nghiên cứu các tính chất của các quá trình trạng thái tại nút mạng và mạng hàng đợi; Xác định các tham số hiệu năng của mạng; Xác định dòng job luân chuyển trong mạng. * Đối tượng nghiên cứu: Đối tượng nghiên cứu của luận án là mạng hàng đợi dạng tổng quát. * Nội dung nghiên cứu chính: - Nghiên cứu một số hàng đợi và mạng hàng đợi trong các công trình nghiên cứu đã được các tác giả trên thế giới công bố. Dựa trên các công trình nghiên cứu của các tác giả trên thế giới từ đó phát hiện các vấn đề mở trong các mô hình mạng hàng đợi đã được công bố. - Đề xuất mô hình mạng hàng đợi và giải quyết một số lớp bài toán có liên quan mô hình mạng hàng đợi đã đề xuất. Tập trung vào hai lớp bài toán: Lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi và lớp bài toán liên quan đến các quá trình trạng thái tại các nút mạng và của mạng hàng đợi. * Ý nghĩa khoa học và thực tiễn: Trong các mạng hiện nay như mạng viễn thông, mạng máy tính, dây chuyền sản xuất…thì bài toán đánh giá hoạt động của mạng thông qua việc xác định các tham số hiệu năng của mạng như phân phối xác suất của trạng thái mạng, thông lượng mạng, trung bình số job có trong mạng, trung bình thời gian phục vụ job, xác suất tắc nghẽn mạng…là bài toán phức tạp và lời giải của bài toán này sẽ phụ thuộc vào nhiều tham số và một số tham số quan trọng đó là lưu lượng dòng job vào mạng, dung lượng của mạng, năng lực
3 phục vụ của mạng, cơ chế luân chuyển job trong mạng, cơ chế dòng vào, cơ chế ưu tiên phục vụ. Việc nghiên cứu mối quan hệ giữa các tham số nêu trên để tìm ra các đặc trưng của mạng cũng như tìm ra phương án điều chỉnh thích hợp nhằm đảm bảo chất lượng phục vụ của mạng và tối ưu hóa việc sử dụng tài nguyên của mạng là vấn đề luôn được đặt ra và cần phải giải quyết một cách hợp lý. Có một số phương pháp đã được sử dụng để xác định mối quan hệ của các đại lượng nói trên, trong đó phương pháp mô hình hóa phân tích theo lý thuyết hàng đợi là phương pháp tổng quát nhất. Trong phương pháp mô hình hóa phân tích, lưu lượng dòng job vào mạng được mô tả dưới dạng các quá trình ngẫu nhiên, năng lực phục vụ của các nút mạng được mô tả bởi các biến ngẫu nhiên, cơ chế luân chuyển job trong mạng được mô tả bởi ma trận xác suất định tuyến và dựa vào lý thuyết hàng đợi để tính toán các đặc trưng của mạng. Đặc biệt, trong mạng đa dịch vụ như mạng viễn thông, mạng máy tính với các yêu cầu khác nhau về chất lượng phục vụ, cơ chế dòng vào, cơ chế ưu tiên phục vụ thì sử dụng lý thuyết hàng đợi là một trong số cách tiếp cận có hiệu quả để giải quyết vấn đề. Bên cạnh các dạng hàng đợi đã được mô hình hóa và áp dụng trong thực tế đời sống xã hội còn có nhiều dạng mô hình mạng hàng đợi đã được các nhà khoa học nghiên cứu đã và đang là những dạng mô hình mạng hàng đợi mang tính định hướng. Với ý nghĩa đó, luận án tập trung nghiên cứu về dòng job luân chuyển trong mạng và nghiên cứu các quá trình trạng thái của mạng hàng đợi, từ đó tính toán một số đặc trưng hiệu năng của mạng. * Phương pháp nghiên cứu: Sử dụng các phương pháp của lý thuyết hàng đợi và mạng hàng đợi, kết hợp với một số phương pháp của lý thuyết xác suất và thống kê toán học để
4 nghiên cứu và giải quyết một số bài toán quan trọng trong mô hình mạng hàng đợi tổng quát. * Bố cục luận án: Ngoài phần mở đầu; kết luận; các công trình khoa học đã công bố; tài liệu tham khảo; phụ lục; nội dung của luận án được trình bày trong ba chương: Chương 1. Một số vấn đề cơ bản về lý thuyết hàng đợi và mạng hàng đợi. Chương 2. Mạng đa lớp tổng quát – Thuật toán phân rã và tổng hợp. Chương 3. Đánh giá quá trình trạng thái của mạng hàng đợi tổng quát. Nội dung của luận án sử dụng các kết quả đã được công bố trong các bài báo của tác giả Luận án thuộc danh mục công trình khoa học đã công bố (trang 116). Một số kết quả nghiên cứu đã được in trong kỷ yếu của đại hội toán học Việt Nam lần thứ 8 và đã được trình bày trong tiểu ban Xác suất và thống kê toán học của đại hội toán học Việt Nam lần thứ 8 diễn ra từ ngày 10- 14/08/2013 tại thành phố Nha trang, tỉnh Khánh Hòa.
5 CHƯƠNG 1 MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LÝ THUYẾT HÀNG ĐỢI VÀ MẠNG HÀNG ĐỢI Hoạt động của mạng hàng đợi phụ thuộc vào rất nhiều tham số đầu vào, trong đó có một số tham số đầu vào quan trọng như dòng job từ bên ngoài vào mạng hàng đợi, cơ chế luân chuyển job trong mạng, năng lực phục vụ và cơ chế ưu tiên phục vụ job tại các nút của mạng. Dòng job từ bên ngoài vào mạng là các quá trình ngẫu nhiên, năng lực của các nút mạng được mô tả bởi các biến ngẫu nhiên thể hiện thời gian phục vụ, cơ chế luân chuyển job trong mạng được mô tả bởi ma trận xác suất định tuyến. Hơn nữa, khi đánh giá hoạt động của mạng hàng đợi, chúng ta phải xác định nhiều tham số hiệu năng của mạng như phân phối xác suất của trạng thái nút mạng và trạng thái mạng hàng đợi, trung bình số job có trong nút mạng và có trong mạng, xác suất tắc nghẽn mạng, thông lượng của mạng…Như vậy để nghiên cứu về mạng hàng đợi, chúng ta phải nghiên cứu các vấn đề có liên quan đến lý thuyết xác suất, lý thuyết các quá trình ngẫu nhiên, lý thuyết hàng đợi và lý thuyết mạng hàng đợi. Nội dung chính của chương 1 trình bày về một số khái niệm xác suất, quá trình Markov; lý thuyết hàng đợi, mạng hàng đợi được dùng trong luận án; trình bày tình hình nghiên cứu của các tác giả trong và ngoài nước về mạng hàng đợi, phát hiện một số vấn đề mở trong các mô hình mạng hàng đợi đã được công bố từ đó xác định các nội dung nghiên cứu trong luận án. Cấu trúc chương 1 gồm bốn phần chính: 1. Một số khái niệm xác suất có liên quan. 2. Xích Markov thời gian rời rạc. 3. Lý thuyết hàng đợi và mạng hàng đợi. 4. Tình hình nghiên cứu trong nước và ngoài nước về mạng hàng đợi.
6 1.1. Một số khái niệm xác suất có liên quan Trong mục này luận án trình bày về một số khái niệm xác suất cơ bản có liên quan đến luận án ([5], [10], [44]). 1.1.1. Biến ngẫu nhiên Xét không gian xác suất (,,P) và không gian đo ( ,) với  là - trường Borel trên đường thẳng thực . Định nghĩa 1.1 Mỗi ánh xạ đo được X: (,)→( ,) được gọi là một đại lượng ngẫu nhiên một chiều (hoặc đôi khi người ta còn gọi là một biến ngẫu nhiên). Để ký hiệu biến ngẫu nhiên, người ta có thể viết X() (với  ) hoặc viết X. 1.1.2. Hàm phân phối xác suất của biến ngẫu nhiên Định nghĩa 1.2 Xét biến ngẫu nhiên X, với x  hàm số F(x) = [X < x]. được gọi là hàm phân phối của biến ngẫu nhiên X. Để ký hiệu hàm phân phối của biến ngẫu nhiên X, người ta thường viết FX(x) và để đơn giản người ta viết F(x). Hàm phân phối F(x) có các tính chất sau: (i) 0 < F(x)
7 F ( x) =  pi , xi  x trong đó pi =[X= xi] với i=1,2,... Nếu tồn tại hàm f : → 0, + ) sao cho: x F ( x) =  f ( t )dt , − x . thì biến ngẫu nhiên X có phân phối liên tục tuyệt đối và f là hàm mật độ phân phối xác suất của X. 1.1.3. Các đặc trưng của biến ngẫu nhiên Giả sử X= X() là biến ngẫu nhiên. Định nghĩa 1.3 Nếu tồn tại đại lượng : E ( X ) =  xi pi nếu X là biến ngẫu nhiên rời rạc. i + E(X ) =  xf ( x ) dx nếu X là biến ngẫu nhiên liên tục, − thì đại lượng đó được gọi là kỳ vọng toán học của biến ngẫu nhiên X. Với kỳ vọng của X có hàm phân phối F ( x) , đôi khi người ta viết E ( X ) =  xdF ( x ) . Định nghĩa 1.4 Nếu tồn tại đại lượng DX = E ( X − E ( X ) ) 2 , thì đại lượng đó được gọi là phương sai của biến ngẫu nhiên X. Đối với phương sai của biến ngẫu nhiên X đôi khi người ta còn ký hiệu là VarX . Người ta cũng có công thức tính phương sai khác là DX = EX2 − ( E ( X ) ) 2 .
8 Định nghĩa 1.5 Xét k  + , đại lượng + EXk được gọi là moment bậc k (cấp k). + E ( X − E ( X ) ) được gọi là moment trung tâm bậc k (cấp k). k + E X k được gọi là moment tuyệt đối bậc k. + E X − EX k được gọi là moment trung tâm tuyệt đối bậc k. Nếu các đại lượng đó tồn tại. 1.1.4. Một số đại lượng ngẫu nhiên quan trọng (thường dùng) - Phân phối nhị thức: Biến ngẫu nhiên X được gọi là có phân phối nhị thức với các tham số n, p ( n  + , p  ( 0,1) ) nếu X có miền giá trị S = {0, 1,…, n} và X = k  = Ckn pk (1 − p )n −k , k  S. (1.1) Khi đó X được gọi là có phân phối nhị thức với các tham số n, p hay nói gọn, X có phân phối B(n, p) (còn viết X ~ B(n, p)). Đặc biệt nếu X ~ B(1, p) thì X được gọi là có phân phối Bernoulli. - Phân phối Poisson: Biến ngẫu nhiên X được gọi là có phân phối Poisson với tham số  (> 0) và được ký hiệu là X ~ P() nếu X có miền giá trị S =  = {0, 1, 2,…} và  k e− X = k = , k = 0, 1… (1.2) k! - Phân phối đều: Biến ngẫu nhiên X được gọi là có phân phối đều và được ký hiệu là X~U(a; b) nếu hàm mật độ của nó có dạng  1  nÕu a  x  b, f (x) = b − a . (1.3) 0  nÕu x   a;b 