DISCRETE MATH FOR CS
DISCRETE MATH FOR CS CS 3653
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Ms. Bridie Kohler on Sunday November 1, 2015. The Class Notes belongs to CS 3653 at Oklahoma State University taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/232838/cs-3653-oklahoma-state-university in ComputerScienence at Oklahoma State University.
Reviews for DISCRETE MATH FOR CS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/01/15
Lecture 5 Probabilities Fundamental Concepts Axiomatic Definition Conditional Probability Bayes Rule Some examples 39 Fact There exist so many cases where we are not capable of making a deterministic assertion regarding a phenomena because its contributing parameters causes cannot be measured or determined precisely So we have to stick with nondeterministic assertions In other words the reality forces us to employ probabilistic models leading to nondeterministic statements since we are not able to compute measure all the forces contributing to an effect or even we may not know them at all CS 3653 Fall 2002 Lecture 51 T Menhaj Uncertainty randomness in real world nothing in nature is indeed deterministic however it has been assumed that physical phenomena obey xed and deterministic laws and are expected to happen consistently all times We say that a statement is nondeterministic probabilistic if it expresses some kind of likelihood or it is the outcome of clearly de ned yet randomly occurring events Probability concerns the likelihood of stochastic non deterministic events the uncertainty dealt with probability generally is related to the concept of randomness occurrence of phenomena and events For example Sex ofa baby is 5050 to be a boy or a girl but the fact is statistics shows that there is a 51 49 chance that the baby be a girl CS 3653 Fall 2002 Lecture 52 T Menhaj Probability conveys information about relative frequencies gives some degree of certainty Because of using probability intuitively not axiomatic the theory of probability understood as something out of reach of ordinary people ie some special person like mathematicians can use it Because of lack of knowledge it is of no use for a more exact analysis 1 So it is no good for real world problems Both are wrong Important notes Must realize that not every experiment can be treated as deterministic Everyone has an intuitive idea about randomness and accepted probability as a common sense note that a common sense is not indeed common We cannot establish a theory based on common sense CS 3653 Fall 2002 Lecture 53 T Menhaj What is meant by Random Signal It is a time waveform that one can characterize only in some probabilistic manner Cannot be predicted It can be desired or undesired signal 0 Random Input Signals Involve a certain amount of uncertainty unpredictability Speech and music signals inputs to communication systems Random digits applied to Computers The bits in a computer bit stream observed to uctuate randomly with time between 0amp1 states thereby creating a random signal An airplane ying in turbulent air Example of a random chance experiment is rolling a die At each performance 6 outcomes are possible 12 or 6 7 CS 3653 Fall 2002 Lecture 54 T Menhaj surely the highly unlikely outcome of the coin standing on the edge is not included De nitions 0 Trials Single performance of a chance random experiment Outcomes Various observable characteristics that are of interest in the performance of an experiment Event It is a set collection of outcomes a Certain event It is Set S consisting of all outcomes b Elementary event It is an event consisting of a single outcome Note At a single trial we observe one and only one outcome Important to note that at a trial an event occurs if it contains the observed outcome So because a certain event contains every outcome it occurs at every trial Some Examples CS 3653 Fall 2002 Lecture 55 T Menhaj lConsider a deck of cards numbered 1 to 10 The outcomes of this card experiment taking a card from the deck at random are the 11 faces f lf2 f 10 The event odd consists of outcomes flf3f5f9 The certain event consists of all 10 outcomes A trial is taking of the card once Suppose that in a particular trial fl shows In this case we see the outcome f 1 however many events occur Question How many 9 9 There are 1n total 2 Daily highway accidents specify a random experiment 3 Monitor all calls originating from a station between 900am amp 1000am 3 The age of death of a person speci es an experiment with as many outcomes 4 Sex of a new born baby Definitions of probability 1 Axiomatic definitions Model Concept CS 3653 Fall 2002 Lecture 56 T Menhaj 2 Classical equally likely 3 Relative frequency empirical 4 Subjective measure of belief intuition Note Use 1 as the basis of probability theory 23 and 4 do not provide a satisfactory basis for a theory of probability however they are often useful to assign probabilities to the outcomes of a random experiment Classical If an experiment has n outcomes and m of them are favorable to an event E they are elements of B then m pE Example 51 Roll two dice Find the probability p that the sum of the faces shows 5 May analyze it in terms of the following models 1 n 11 possible sums 23 12 Of these only the outcome 5 is favorable to the event CS 3653 Fall 2002 Lecture 57 T Menhaj E 5 hence m 1 May conclude that P mn 111 2 n 21 pairs ll 66 not distinguishing between the rst and the second die n 654321 21 The favorite outcomes are now m 2 namely the pairs 14 23 Now we may conclude that p mn 221 3 By distinguishing between the rst and the second die n 36 pairs of outcomes and m the favorable outcomes are now the 4 pairs 14 41 23 32 and may have p 43 619 Note Three different solutions for the same problem which one is correct We may say that the third is correct because the true number of outcomes is 36 Actually one may use all 3 models to describe this experiment We must keep in mind that from the classical definition the CS 3653 Fall 2002 Lecture 58 T Menhaj third leads to the correct solution because its outcomes are equally likely while the other two models cannot be used to determine the value of probability based on this de nition Needs Some re nement Notes 1 circular de nition the concept to be de ned used in the de nition 2 Not dependent on experiment accepted as a logical necessity It calculates the probability a priori not related to the reasoning from the observed facts Good for a limited class of problems of no use in applications involving many outcomes requiring some measure of no of outcomes length area 2 Subjective involves total ignorance and using principle of insuf cient information for reasoning CS 3653 Fall 2002 Lecture 59 T Menhaj Assign to all n choices of an experiment the same probability of ln Consider coin experiment pheadsptails12 Note Both classical and subjective led to the same formula What is the big difference The rst uses past experiments and symmetrical equally likely considerations not subject to change while the latter is based on the total ignorance about the outcomes of experiment subject to change with new evidence Probability as a Relative Frequency It says that if in 11 trials an event A occurs m times then its probability PA is approximately m 11 provided that n is sufficiently large the ratio m n is nearly constant as 11 increases Note The interpretation of probability as a relative frequency comes from the use of common sense experience and observations It is fundamental in the study of averages establishing the link between the model CS 3653 Fall 2002 Lecture 510 T Menhaj