Wednesday, 12 April 2017

Indirect Proof

Indirect Proof

An indirect proof is the same as proving by contradiction, which means that the negation of a true statement is also true. Indirect proof is often used when the given geometric statement is NOT true. Start the proof by assuming the statement IS true. Then reason correctly from the given information until a contradiction of a known postulate, theorem, or given fact is reached. For example,

Given:  is not a right angle.
Prove: .
Indirect Proof:
Assume .
If , then by definition of a right angle, is a right angle. However, this contradicts the given statement. Because the assumption leads to a contradiction, the assumption must be false. Therefore, 


.Question: Question 1 (35 points) Consider the symmetric rand...

Question 1 (35 points) Consider the symmetric random walk tXt t 0 on the integers S Z 10,t1, t2, i.e., the transition probabilities are given by pi,i+1 pii 1/2, for i E Z i-1 Let N 0 be a given integer. Suppose that the walk starts at i, where i E 10, 1,.. N Let Mi be the expected number of steps needed to reach either 0 or N, given that the walk starts i (a) (20pts). By considering an appropriate recurrence relation, determine Mi for 0, 1 (b) (15pts). Suppose that the walk starts at 0. Consider the hitting time To mintt 1 Xt 0). We have shown in class that Pr(To +oo) 1, as state 0 is recurrent. Now, using the result in (a), show that ETol +oo. (In other words, although the walk will return to 0 eventually, the average number of steps it takes is infinite! Question 2 (40 points) Consider an urn with N balls, some of which are white and some are black. At each stage, a fair coin is flipped. If heads appears, then a ball is chosen at random from the urn and is replaced by a white ball. On the other hand, if tails appears, then a ball is chosen at random from the urn and is replaced by a black ball. Let Xn be the number of white balls in the urn after the n-th stage. Then, the process tXn n 0,1,... defines an irreducible Markov chain (a) (10pts). Specify the state space and transition probabilities of this chain (b) (15pts). Show that the Markov chain in (a) is aperiodic (c) (15pts). Determine the stationary distribution of the chain

Show transcribed image text

By at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)