組合機率

組合機率，研究一類涉及有限多個但數量很大的基本事件的機率問題的方法。

基本介紹

• 中文名：組合機率
• 定義：研究一類涉及有限多個但數量很大的基本事件的機率問題的方法

發展

它是從研究組合、最佳化（見組合最最佳化）、運籌學和計算機科學中有限隨機結構的性質和用途而逐漸形成和發展起來的。當數據結構龐大時，人們更多地關心有關機率的漸近性質。組合機率方法始於1947年愛爾特希關於經典的拉姆齊問題的解，其特點是為了證明具有某種性質的組合結構存在，構造一個機率空間（見機率）並證明以嚴格正的機率任取一個樣本都具有該種性質，所用技巧主要是計算有關組合數的數學期望、方差和尾機率不等式估計等。隨機圖在隨機離散結構研究中起著重要作用，研究成果最為豐富。

愛爾特希和A.雷尼1960年建立了隨機圖的理論基礎，並發現隨機圖過程具有雙跳現象。組合機率與算法分析有著自然而密切的聯繫。

20世紀70年代發展起來的算法機率分析旨在準確描述算法的平均運行情況和隨機數據結構的分類，避免了最差案例的尷尬。

主要模型

用於算法分析的常見模型有隨機弦、隨機樹、隨機排列、隨機字和隨機配置。