`
leonzhx
  • 浏览: 793585 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Probability Review

阅读更多

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]

 

  • 大小: 11.4 KB
分享到:
评论

相关推荐

    Foundations of Machine Learning

    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 ...

    A Practical Introduction to Computer Vision with OpenCV

    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 ...

    Exam MLC 精算 11 edition part1

    部分内容中提到“Probability Review”,这表明手册会复习概率论相关的基础知识。包括函数和矩、概率分布(伯努利分布、均匀分布、指数分布)、方差、正态近似以及条件概率和期望值等。这些是精算分析中不可或缺的...

    Probability Theory Review for Machine Learning

    ### 概率论在机器学习中的基础概念 概率论作为数学的一个分支,主要研究不确定性的量化分析,在机器学习领域占据核心地位。机器学习算法的设计往往依赖于数据的概率假设。本文档将详细介绍概率论的一些基本概念及其...

    Physically Based Rendering from Theory to Implementation - part1

    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代码左移-How-to-Talk-Probability-Review-2:如何谈谈概率回顾2

    matlab代码左移如何谈谈概率回顾2 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 在我们的第一次概率回顾中,我们讨论了概率空间的概念,因此现在我们可以继续进行...

    matlab代码影响-How-to-Talk-Probability-Review-3:如何谈谈概率回顾3

    matlab代码影响如何谈谈概率回顾3 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 当我们处理多个随机变量时,例如患者的心率,胆固醇水平,血压,他们是否生病等等...

    matlab代码影响-How-to-Talk-Probability-Review-1:如何讨论概率复习-1

    matlab代码影响如何讨论概率复习-1 2020年12月23日 我感谢您的评论。 给我发电子邮件! 雇用我! :smiling_face_with_smiling_eyes: 为了继续学习机器学习,您需要熟悉三种类型的数学,即概率,线性代数和优化。...

    Mathematics in Computing

    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: ...

    Mathematical Methods of Statistics - Cramer 经典名著

    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 ...

    斯坦福大学-机器学习公开课课件.rar

    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 ...

    Introduction to Probabilistic Modelling

    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.

    Understanding Clinical Research: Behind the Statistics

    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 ...

Global site tag (gtag.js) - Google Analytics