The Dwinelle Labyrinth
You have decided to take a humanities class this semester, a French class to be specific. Instead of a final exam, your professor has issued a final paper. You must turn in this paper before noon to the professor’s office on floor 3 in Dwinelle, and it’s currently 11:48 a.m.
Let Dwinelle be modeled by the following Markov chain. Instead of rushing to turn it in, we will spend valuable time computing whether or not we could have made it. Suppose walking between floors takes 1 minute.
(a) Will you make it in time if you choose a floor to transition to uniformly at random? (If Ti is the number of steps needed to get to F3 starting from Fi, where i ∈{0,1,2,3,4}, is E[T0] < 12?)
(b) Will you make it in time, if for every floor, you order all accessible floors and are twice as likely to take higher floors? (If you are considering 1, 2, or 3, you will take each with probabilities
1/7, 2/7, 4/7, respectively.)
2 Reflecting Random Walk
Alice starts at vertex 0 and wishes to get to vertex n. When she is at vertex 0 she has a probability of 1 of transitioning to vertex 1. For any other vertex i, there is a probability of 1/2 of transitioning to i+1 and a probability of 1/2 of transitioning to i−1.
(a) What is the expected number of steps Alice takes to reach vertex n? Write down the hittingtime equations, but do not solve them yet.
(b) Solve the hitting-time equations. [Hint: Let Ri denote the expected number of steps to reach vertex n starting from vertex i. As a suggestion, try writing R0 in terms of R1; then, use this to express R1 in terms of R2; and then use this to express R2 in terms of R3, and so on. See if you can notice a pattern.]
3 Predicament
Three men are on a boat with cigarettes, but they have no lighter. What do they do?
4 Which Envelope?
You have two envelopes in front of you containing cash. You know that one envelope contains twice as much money as the other envelope (the amount of money in an envelope is an integer). You are allowed to pick one envelope and see how much cash is inside, and then based on this information, you can decide to switch envelopes or stick with the envelope you already have.
Can you come up with a strategy which will allow you to pick the envelope with more money, with probability strictly greater than 1/2?
