526 Discrete-state Stochastic Processes
Homework 2
随机过程作业代写 The maximum number of points you can receive for this homework is 15. 1.(3 pts) Consider 8 × 8 chess board. A bishop can move any number of
The maximum number of points you can receive for this homework is 15.
1.(3 pts) 随机过程作业代写
Consider 8 × 8 chess board. A bishop can move any number of squares diagonally. Let (Xn) be the sequence of squares that results if we pick one of bishops legal moves at random.
a) Find the stationary distribution of (Xn) (you can represent the answer by drawing a chess board and writing numbers in the cells).
b) Find the expected number of moves to return to corner (1, 1) when we start there. (Hint: there is a formula that connects the desired quantity to stationary distribution, but it only holds for irreducible Markov chains!)
2.(2 pts)
A warehouse has a capacity to hold four items. If the warehouse is neither full nor empty, the number of items in the warehouse changes whenever a new item is produced or an item is sold. Suppose that (no matter when we look) the probability that the next event is “a new item is produced” is 2/3 and that the new event is “a sale” is 1/3. If there is currently one item in the warehouse, what is the probability that the warehouse will become full before it becomes empty.
3.(2 pts) 随机过程作业代写
A fair coin is tossed repeatedly. Let us denote heads by H and tails by T. What is the expected number of tosses until we observe HT T?
Hint: you may solve a system of linear equations, but there is an easier way, described in Example 1.48 in the textbook
4.(3 pts)
Consider the numbers {1, 2, . . . , 25} written around on a circle, one after the another (so that, in particular, 1 is adjacent to 2 and 25). Consider a Markov chain (Xn)n≥0 that, at each time, jumps with equal probability to one of the two adjacent numbers.
a) What is the expected number of steps that Xnwill take to return to its starting position?
b) What is the probability that Xnwill visit all the other states before returning to its starting position?
5.(3 pts) 随机过程作业代写
Survival game. Consider 3 players, A, B and C, taking turns shooting at each other. Any player can shoot at only one opponent at a time (and each of them has to make a shot whenever it is his/her turn). Each shot of A is successful with probability 1/3, each shot of B is successful with probability 1, and each shot of C is successful with probability 1/2 (with all the outcomes being independent). A goes first, then B, then C, then A, and so on, until one of them dies. Then, the remaining two will be shooting at each other, so that nobody ever makes two shots in a row: e.g. if A gets C shot, then B goes next. The game continues until only one player is left.
Assume that every player is trying to find a strategy that maximizes his/her probability of survival. Assume also that every player acts optimally and knows that the other players will act optimally too. Who should player A shoot at first? What is the probability of survival of A (assuming he/she acts optimally)?
Hint. 随机过程作业代写
A strategy is a sequence of decisions on who to shoot at at any given turn, given who is still left in the game. It is clear that, after B shoots for the first time, there will be at most two players left, and, hence, for the remaining players, there will be no need to make any choices. Therefore, it is convenient to solve the problem recursively, starting from the decision of B, and assuming that all players are alive by the time B shoots (otherwise, again, there are no decisions for B to make).
It is clear that, given a choice between A and C, B will shoot at C, because playing against A only will give B a higher probability of survival than playing against C only (i.e. 2/3 vs. 1/2). Knowing this, A needs to choose whether it is optimal to shoot at B or at C. Considering the possible outcomes produced by each of the two choices, you will notice that, in one case, the survival probability can be computed by hand, and, in the other case, it can be reduced to the computation of an exit probability of a simple Markov chain.
6.(2 pts) 随机过程作业代写
Use the reflection principle to find the number of paths for a simple random walk from S0= 2 to S15= 5 that do not hit the level at k = 6.
