Báo cáo tài liệu vi phạm
Giới thiệu
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Luận Văn - Báo Cáo
Báo cáo khoa học
Báo cáo toán học: "The lower tail of the random minimum spanning tree"
Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The lower tail of the random minimum spanning tree"
Bích Liên
78
4
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The lower tail of the random minimum spanning tree. | The lower tail of the random minimum spanning tree Abraham D. Flaxman Microsoft Research Redmond WA USA abie@microsoft.com Submitted Sep 11 2006 Accepted Dec 15 2006 Published Jan 17 2007 Mathematics Subject Classifications 05C80 60C05 Abstract Consider a complete graph Kn where the edges have costs given by independent random variables each distributed uniformly between 0 and 1. The cost of the minimum spanning tree in this graph is a random variable which has been the subject of much study. This note considers the large deviation probability of this random variable. Previous work has shown that the log-probability of deviation by is Q n and that for the log-probability of Z exceeding 3 this bound is correct logPr Z 3 0 n . The purpose of this note is to provide a simple proof that the scaling of the lower tail is also linear logPr Z 3 0 n . 1 Introduction If the edge costs of the complete graph Kn are independent random variables each uniformly distributed between 0 and 1 then the cost of a minimum spanning tree is a random variable which has expectation asymptotically equal to 3 V1 i-3 6 . Furthermore after an appropriate rescaling this random variable converges in distribution to a Gaussian distribution with an explicitly known variance of about 1.6857 8 . This note considers the large deviation probability of this random variable denoted Zn. In 9 as an example application of Talagrand s Inequality McDiarmid shows that Zn satisfies an exponential tail inequality of the form Pr Zn - 3 1 e-C-n. See also 4 for an alternative approach with additional details . Simple considerations show that for the log-probability of Zn exceeding 3 this bound is correct which is to say that logPr Zn 3 0 n . For example the probability that every edge incident to vertex 1 has cost at least 1 2 is 1 2 n-1 and conditioned on this event whp Zn 1 o 1 3 1 2 . THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N3 1 The behavior of the lower tail is not as simple to identify. A casual .
TÀI LIỆU LIÊN QUAN
Báo cáo toán học: " Quantitation of glucose uptake in tumors by dynamic FDG-PET has less glucose bias and lower variability when adjusted for partial saturation of glucose transport"
Báo cáo toán học: " Lower striatal dopamine D2/3 receptor availability in obese compared with non-obese subjects"
Báo cáo toán hoc:"A New Lower Bound on the Density of Vertex Identifying Codes for the Infinit"
Báo cáo toán học: "Lower Semicontinuity of the KKT Point Set in Quadratic Programs Under Linear Perturbations"
Báo cáo toán học: "A generalization of generalized Paley graphs and new lower bounds for R(3, q)"
Báo cáo toán học: "Upper and lower bounds for Fv (4, 4; 5)"
Báo cáo toán học: "A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets"
Báo cáo toán học: "Lower bounds for identifying codes in some infinite grids"
Báo cáo toán học: "Sharp lower bound for the total number of matchings of tricyclic graphs"
Báo cáo toán học: "Lower Bounds for the Average Genus of a CF-graph"
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.