1 Problem A certain person goes for a run each morning. When he leaves the house for his run, he is equally likely to go out either the front or the back door and similarly when he returns, he is equally likely to go to either the front or the back door. The runner owns 3 pairs of running shoes which he takes off after the run at whichever door he happens to be. If there are no shoes at the door from which he leaves to go running, he runs barefoot. We are interested in determining the proportion of time that he runs barefoot. 1. Set this problem up as a discrete time Markov chain. Give the states and the one-step transition probability matrix. 2. Determine the proportion of days that he runs barefoot. 2 Problem In a Binary Symmetric (Communication) Channel (BSC) data is sent data is sent using bits 0 and 1. When the source and the destination are far apart, there are repeaters that decode the bit and transmit generate a signal. However due to noise, there decoding error, i.e., there a probability a that a bit 0 will be decoded as (and hence transmitted) as 1. Similarly, is the probability that a bit 1 will be decoded as (and hence transmitted as) 1. Let Xo be the bit's initial parity and and let X, be the bits parity after the nth repeater. 1. Construct the one-step transition matrix for this Markov Chain. 2. Suppose the input stream to this communication channel consists of 80% Os and 20% 1s. Determine the proportion of Os and 1s after the first repeater. 3. Under the same input values as in (b) determine the proportions of Os and 1s exiting the 5th relay. 3 Problem A hash table is a very important data structure in computer science. It is used for fast information retrieval. It stores data as a pair, where the value is indexed by the key. Note that keys must ne unique. Consider the example of storing persons name using the social security number (ssn) as the key. For each ssn x, a hash function h is used, where h(x) is the location to store the name of x. Once we have created a table, to look up the name for ssn x, we can recomputes h(x) and then look up what is stored in that location. In Python, dictionaries are based on hash tables. Typically, the hash function h is deterministic; we do not want to get different results every time we compute h(x). But h is often chosen to be pseudo-random. For this problem, we will assume that h is truly random. Suppose there are k people, with each person's name stored in a random location (independently), represented by an integer between 1 and n, k < n. It may happen that one location has more than one name stored there, if two different people ssns x and y end up with the same random location for their name to be stored. 1. What is the expected number of locations with no name stored? 2. What is the expected number with exactly one name? 3. What is the expected number with more than one name?