1. Sample space Ω = "All possible out comes".
Each outcome i in Ω , has a probability P(i) >= 0;
Constraint : Sum(i in Ω) {P(i)} = 1.
2. Choosing a random pivot in outer QuickSort Call:
Ω ={1, 2, ... , n } and P(i) = 1/n for all i in Ω.
3. An event is a subset S of Ω.
The probability of an event S is Sum(i in S) { P(i) }.
4. The event "the chosen pivot gives a 25-75 split of better" = {(n/4 + 1) th smallest element, ..., (3n/4)th smallest element} , so its Probability = 1/2
5. A random variable X is a real-valued function defined on Ω. (i.e. size of subarray passed to 1st recursive call)
6. Let X be a random variable, the expectation E[X] of X = average value of X = Sum(i in Ω){ X(i) P(i)}
7. The expectation of the size of the subarray passed to the first recursive call in QuickSort is :
1/n X 0 + 1/n X 1 + 1/n X 2 ... + 1/n X (n-1) = (n-1)/2
8. Let X1, X2 , ... , Xn be random variable defined on Ω. Then :
E[Sum(Xj)] = Sum(E[Xj])
9. Proof of Linearity of Expectation:
Sum(j = 0~n) { E(Xj) } = Sum(j=0~n) { Sum(i in Ω) {Xj(i) P (i) } }
= Sum(i in Ω) { Sum(j=0~n) {Xj(i) P (i) } }
= Sum(i in Ω) { P (i) Sum(j=0~n) {Xj(i)} }
= E( Sum(j=0~n) {Xj} )
10. Problem: need to assign n jobs to n servers.
Proposed Solution: assign each job to a random server.
Question: what is expected number of jobs assigned to a server.
Sample Space = All n^n assignments of jobs to servers ,each equally likely.
Let Y = total number of jobs assinged to the 1st server.
Let Xj = 1 if jth job assined to 1st server, 0 otherwise.
Y = Sum (j=1~n) {Xj} , So E[Y] = Sum (j=1~n) {E[Xj]} = Sum(j=1~n){P[Xj=1]} = n X 1/n = 1.
11. Let X, Y be events on Ω, P(X|Y) = P(X and Y) / P(Y) ( the probability of X given Y ---- Conditional Probability)
12. Events X and Y are independent iif P(X and Y) = P(X)P(Y)
P(X and Y) = P(X)P(Y) <==> P(X|Y) = P(X) <==> P(Y|X) = P(Y)
13. Random variable X and Y defined on Ω, X and Y are independent iff for all a, b , event "X=a" and event "Y=b" are independent. <==> P(X=a and Y=b) = P(X=a) P(Y=b)
14. if A, B are independent , then E[A B] = E[A] E[B] , proof :
E[A B] = Sum ( for all a, b) { a b P(X=a and Y=b)} = Sum ( for all a, b ) { a b P(X=a) P(Y=b) }
= Sum ( for all a ) {a P(X=a)} Sum (for all b) {b P(Y=b)}
= E[X] E[Y]
15. Let X1, X2 is randomly valued 0 or 1 , and X3= X1 xor X2.
So X1 and X3 are independent. But X1X3 and X2 are not independent : E[X1X2X3] <> E[X1X2]E[X3]
相关推荐
The appendix offers a concise probability review, a short introduction to convex optimization, tools for concentration bounds, and several basic properties of matrices and norms used in the book.The ...
8.3.1 Probability Review 142 8.3.2 Sample Features 143 8.3.3 Statistical Pattern Recognition Technique 149 8.4 Cascade of Haar Classifiers 152 8.4.1 Features 154 8.4.2 Training 156 8.4.3 Classifiers ...
部分内容中提到“Probability Review”,这表明手册会复习概率论相关的基础知识。包括函数和矩、概率分布(伯努利分布、均匀分布、指数分布)、方差、正态近似以及条件概率和期望值等。这些是精算分析中不可或缺的...
### 概率论在机器学习中的基础概念 概率论作为数学的一个分支,主要研究不确定性的量化分析,在机器学习领域占据核心地位。机器学习算法的设计往往依赖于数据的概率假设。本文档将详细介绍概率论的一些基本概念及其...
Background and Probability Review Continuous Random Variables Expected Values and Variance The Monte Carlo Estimator Sampling Random Variables The Inversion Method Example: Power Distribution ...
matlab代码影响如何谈谈概率回顾3 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 当我们处理多个随机变量时,例如患者的心率,胆固醇水平,血压,他们是否生病等等...
matlab代码左移如何谈谈概率回顾2 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 在我们的第一次概率回顾中,我们讨论了概率空间的概念,因此现在我们可以继续进行...
matlab代码影响如何讨论概率复习-1 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 为了继续学习机器学习,您需要熟悉三种类型的数学,即概率,线性代数和优化。...
1.8 Review Questions 1.9 Summary 2 Sets, Relations and Functions 2.1 Introduction 2.2 Set Theory 2.2.1 Set Theoretical Operations 2.2.2 Properties of Set Theoretical Operations 2.2.3 Russell’s ...
Note2:Probability Theory Review for Machine Learning 21 Note3:Convex Optimization Overview 34 Note4:Convex Optimization Overview (cnt’d) 46 Note5:Hidden Markov Models Fundamentals 61 Note6: ...
French and Russian probabilitists transformed the classical calculus of probability into a rigorous and pure mathematical theory. The result of Cramér's work is a masterly exposition of the ...
Section notes 2 (pdf) Probability Theory Review Files for the Matlab tutorial: sigmoid.m, logistic_grad_ascent.m, matlab_session.m Section notes 4 (ps) (pdf) Convex Optimization Overview, Part I ...
This notes review basic concepts in probability theory and will allow you to understand fundamental principles in probabilistic modelling.
r Review 1 Joint Power Allocation and Route Selection for Outage Minimization in Multihop Cognitive Radio Networks with Energy Harvesting Avik Banerjee, Student Member, IEEE, Anal Paul, Student Member...
这是本经典的多用户信息论教材 英文版 强烈推荐 This survey reviews fundamental concepts of multi-user information theory....includes a review of basic probability and information theory.
Meta-analysis and systematic review Meta-analysis Systematic Review Week 2: Describing your data The spectrum of data types Definitions Descriptive statistics Inferential statistics Population ...