Expectation of Stopping Time of Martingale Problems
This paper aims at solving "the expected time until a given pattern occurs" problems.
Problems:
- An ant starts at \(x=0\) has probability \(p\) moving forward and \(1-p\) moving backward. Find expected number of steps until the ant reaches position \(x = i, i > 0.\)
- An ant starts at \(x=0\) has probability \(p\) moving forward and \(1-p\) moving backward. Find expected number of steps until the ant reaches position \(x = -a\) or \(x = b.\)
- Three players \(X, Y, Z\) holding \(x, y, z\) coins separately. Each time, two players are chosen randomly and the first chosen gives 1 coin to the second chosen. When someone has no coin, the player is kicked off and the other two player continues. Find the expected number of rounds until one player has all \(x+y+z\) coins.
- In a party we have \(n\) players each having a hat. Their hats are mixed together. Each round, each person selects one hat randomly. If one gets his own hat, he leaves. Otherwise, he stays for next round. Find the expected number of rounds until everyone has his own hat.
- \(n\) players are passing balls to each other. The \(i\)-th person has \(a_i\) balls. Every round, a ball is randomly selected. Suppose that \(i\)-th player holds this ball. Then he randomly passes the ball to another player. Find the expected number of rounds until one player holds all balls. CodeForces 1349D. Slime and Biscuits
- There are many balls with \(n\) different color. There are \(a_i\) number of balls with color \(i.\) Every round, an ordered pair of balls \(A, B\) is selected randomly. Then ball \(B\) is painted with color of ball \(A.\) Find the expected number of rounds until all balls are in the same color. CodeForces 850F. Rainbow Balls
- \(n\) people play a leader game. Initially, nobody is leaded by anybody. Every round, an order pair of people not leaded by others \(A, B\) is selected randomly. Then \(x\) is leaded by \(y.\) Find the expected number of rounds until there is only one person not leaded by others. In another sense, there exists someone leads everyone else.
Solutions:
- Let \(X_j\) be the random variable at \(j\) step. If it takes \(N\) steps to reach position \(i,\) we have \[\sum_{j=1}^N X_j = i.\] Since \(E(X_j) = 2p-1,\) by Wald's equation [[数学杂记/随机过程/Stochastic Process 4 -- Martingale#^85aa97|Stochastic Process 4 -- Martingale]] we have \[E(N)E(X_j) = i.\] Then we have \(E(N) = \frac{i}{2p-1}.\)
- Things are almost the same as problem 1. Now we denote an event as it takes \(N\) steps to reach position \(-a\) or \(b.\) We have\[\sum_{j=1}^N X_j = -a, b.\]To apply Wald's equation, we need to know \(E(\sum_{j=1}^N X_j).\) Here we solve this by finding the probability of reaching \(-a\) and \(b.\) We need a martingale \(Z_n = (\frac{1-p}{p})^{S_n},\) here \(S_n = \sum_{j=1}^n X_j.\) By optional stopping theorem, we have \(E(Z_N) = E(Z_0) = 1\) as we define \(Z_0 = 1.\) Then we get\[1 = P_a(\frac{1-p}{p})^{-a} + (1 - P_a)(\frac{1-p}{p})^{b}.\]Then \(E(N) = \frac{P_a(-a)+(1-P_a)b}{2p-1}.\) Especially, when \(p = 1/2, E(N) = ab.\)
- We assume that when there are only two players left, they are allowed to have negative coins. Denote \(X_n, Y_n, Z_n\) the number of coins that each player have at \(n\) round. We have \(X_0 = x, Y_0 = y, Z_0 = z.\) Next we show that \(M_n = X_nY_n + Y_nZ_n + Z_nX_n + n\) is a martingale. Then by optional stopping theorem we have \(E(M_n) = E(M_0) = xy+yz+zx.\) To show it is a martingale, we need to prove that \(E(M_{n+1} | X_n, Y_n, Z_n) = M_n.\) We discuss it in two ways. First way the by step \(n,\) a player has left(assume \(X\) leaves the game). Then \(E(Y_{n+1}Z_{n+1} | X_n, Y_n, Z_n) = [(y-1)(z+1) + (y+1)(z-1)]/2 = yz-1.\) Second way, by step \(n,\) no player has left. Then \(E(Y_{n+1}Z_{n+1} | X_n, Y_n, Z_n) = [y(z+1)+y(z-1)+(y+1)z+(y-1)z + (y-1)(z+1) + (y+1)(z-1)]/6 = yz - 1/3.\)
- We denote \(R\) the number of rounds until everyone finds a match, \(X_i\) the number of matches on \(i\) round. We construct a zero mean martingale\[Z_k = \sum_{i=1}^k (X_i - E(X_i \mid X_{j}, j = 1,..,i-1)) = \sum_{i=1}^k(X_i - 1).\]Here we use the fact that any number of individuals are to randomly choose from among their own hats, the expected number of matched is 1. What we want is to find \(E(R)\) such that \(\sum_{i=1}^R X_i = n.\) As we have \(E(Z_R) = E(Z_0) = 0.\) Now we get\[0 = E(\sum_{i=1}^R X_i - R) = E(\sum_{i=1}^R X_i) - E(R) = n - E(R).\]
- TODO
cite:
Stochastic Processes - Spring 2008, University of Houston
Stochastic Process, Second Edition, Sheldon M. Ross