Discrete Mathematics for ECE 14:332:202 Spring 2004 Recitation 8: Intro to Probability: Combinatorics Introduction: Uncertainty in experiments and real-world processes requires engineers to understand the concepts of probability. This follows our discussion of sets, as we will apply set theory to our study of probability, and will begin to further describe the uncertainty involved in events within our sample space (universal set). Our sample space describes all possible outcomes of events that could take place in that experiment. Refer to the class notes for the example of a sample space involving two dice. The probability of a particular event, P[A], is a number between 0 and 1, and since the sample space describes all possible events, P[S] = 1. We use the term mutually exclusive to describe the case where two events are disjoint (A intersect B = 0). Independence describes the case where knowledge of the outcome of one event does not affect the probability of another. We will explore this more in a later recitation When we are describing discrete (countable) events, we can graphically describe the probabilities of all mutually exclusive events using a Probability Mass Function (PMF). In a single dice rolling experiment, X, our events may be the numbers on the dice, so our event probabilities could be exhaustively described by P(X=1), P(X=2), P(X=3), P(X=4), P(X=5), P(X=6). If our dice were unweighted, our PMF would appear as the figure on the left, each outcome is as equally likely to occur. With a weighted dice, some numbers may be more likely to occur, as is on the right. In both cases, the sum of the probabilities of each even in the sample space is 1. These graphs were obtained using the bar function. A useful way to gather statistics and display them in a PMF sort of form is through a histogram, using the hist function. A number of important concepts and formulas fall under the topic of Combinatorics, or counting methods. These describe some basic methods of arranging objects, and are well described in Ch. 8 of your text. Exercises: 1. Implement the fair (unweighted) die by creating a function roll(n) that will return a value 1 – n with equal probability. You can do this by manipulating the rand function, which returns a fractional number between 0 and 1, according to a uniform distribution. Now that you can simulate a 6-sided dice roll, test to see if your function generates a fair roll by “rolling” it 1000 times, and superimposing on your theoretical PMF your actual results (make sure you have scaled correctly). Do this in a script called rec8a.m 2. Let’s explore permutations by creating an experiment which is a random permutation of the integers 1:5. (this can be accomplished using the randperm function). What is the probability that the exact ordering [1 2 3 4 5] will occur? Test this by running your experiment 1000 times, and seeing how close your statistical measurement is to the theoretical probability. What is the probability the first three numbers will be [3 1 2]. Test this similarly. Do this in a script called rec8b.mAdditional Exercises: To demonstrate the concept of combinations, we will use the standard card deck, no jokers. Create a function [cards,deck] = draw(n,deck) that will return a struct representing the drawn cards, where n is the number of cards to be drawn, and deck is a struct representing the deck of cards. The returned deck will have removed the cards that were drawn. An element can be deleted from the struct by setting it equal to an empty vector, for example deck(5) = [] will delete the 5th element from the struct. A struct data type in MATLAB allows different properties of a variable to be stored. We can define our deck as a struct by the following function newdeck.m. function deck = newdeck suits = {‘hearts’;’clubs’;’diamonds’;’spades’}; values = {2;3;4;5;6;7;8;9;10;’J’;’Q’;’K’;’A’}; count = 1; for i = 1:length(suits) for j = 1:length(values) deck(count).suit = suits{i}; deck(count).value = values{j}; count = count + 1; end end You can see that a struct (deck in this case) is specified by the name of the variable, the element number, and the property names for that element number. For example: >> deck deck = 1x52 struct array with fields: suit value >> deck(1) ans = suit: {'hearts'} value: {[2]} >> deck(1).suit ans = 'hearts' To shuffle your deck: deck = deck(randperm(length(deck))) Calculate the following on paper: a. The probability a randomly drawn card will be a heart b. The probability a randomly drawn card will be a face card c. The number of 5 card poker hands d. Having drawn 5 cards, the probability of getting one pair or better Test a,b,d out by carrying out a number of experiments. interesting: http://www.mathwizz.com/statistics/help/help3.htm Extra Credit: Using your draw function create a MATLAB version of the game blackjack (no dealer, just drawing to reach 21). At each turn, display the probability of going bust if you draw, based on the cards left in the deck. Make sure you do not reshuffle the deck at each turn.Reference: BAR: To create PMFs, we use the bar function. For example, if our events are X = 1,2,3, and P(X=1) = 0.5, P(X=2) = P(X=3) = 0.25, we would create our PMF as follows x = [1 2 3]; y = [0.5 0.25 0.25]; figure; bar(x,y); HIST: Now, say we have rolled our die 1000 times to create exps, a 1x1000 vector of integers between 1 and 6. The MATLAB hist function will count the number of times the specified events (numbers) have occurred in our vector according to the following syntax. N = 1000; % say exps has been returned [n, bins] = hist(exps,[1 2 3 4 5 6]); bar(bins,n/N) HOLD ON: To superimpose graphs, you must make sure to type “hold on” in between plotting commands, so that the next graph is added to the previous one. Structures: A structured data type, or struct, allows us to store multiple property values for a variable without the messiness of cell arrays. For example, if we wanted a variable to describe a card from a deck, we could have its properties be its suit and value. We don’t have to declare a variable is a struct, we just start defining its fields by periods. For our card, we might define: card.suit = ‘hearts’; card.value = 6; We can have multiple elements in a struct (it can be more complex as well with substructs, but