Consider a process with an initial state $(A_0, B_0)$ and at each step $t+1$, considering $(A_t, B_t)$:

  • $(A_{t+1}, B_{t+1}) = (A_t + 1, B_t)$, with probability $A_t/(A_t + B_t)$
  • $(A_{t+1}, B_{t+1}) = (A_t, B_t + 1)$, otherwise (with probability $B_t/(A_t + B_t)$)

Using a martingale, what is the expected value of $A_t$ after $t$ steps as a function of $A_0$, $B_0$, and $t$?

Is it a good approach to envision a martingale to which we could apply the optional stopping theorem?

EDIT: We can write a recursion as (given that $A_t + B_t = A_0 + B_0 + t$):

$$E[A_{t+1}\mid A_t] = A_t\left(1 + \frac{1}{A_0 + B_0 + t}\right)$$

Which can be solved to yield (considering $E[A_0] = A_0$):

$$E[A_t] = A_0\left(1 + t\frac{X_0}{A_0 + B_0}\right)$$

The question is what function $f$: $Z_t = f(A_t)$ can be such that $Z_t$ is a martingale with respect to $A_t$?

  • $\begingroup$ Since $|A_t|\leqslant A_t+1$ and $|B_t|\leqslant B_t+1$, $A_t$ and $B_t$ are integrable, and $$ \mathbb E[(A_{t+1},B_{t+1})\mid (A_t,B_t)] = \left(1+\frac1{A_t+B_t}\right)(A_t,B_t) \geqslant (A_t,B_t). $$ Hence $\{(A_t,B_t)\}$ is a submartingale. $\endgroup$
    – Math1000
    Apr 8, 2018 at 18:15
  • $\begingroup$ Right, but how would you go about calculating $A_t$ given $A_0$, $B_0$ and $t$ from the defined submartingale $\{(A_t, B_t)\}$? $\endgroup$
    – onaheimi3
    Apr 9, 2018 at 14:53
  • $\begingroup$ @onaheimi3 I think your approach is reasonable. Typically a submartingale is not terribly useful for computing such things, because it only gives a one-sided bound; you're looking for a genuine martingale. $\endgroup$ Apr 10, 2018 at 15:15
  • $\begingroup$ @AaronMontgomery my current problem is finding the correct martingale, because the stopping condition would have to be after $t$ iterations $\endgroup$
    – onaheimi3
    Apr 11, 2018 at 17:32
  • $\begingroup$ @onaheimi3 Yes, that's certainly the hard part -- in general, I'd say that finding a clever martingale which trivializes the problem is the hard part of using the OST to say something interesting. I spent about 2 minutes trying to come up with the right martingale for this problem, and I couldn't immediately see it. $\endgroup$ Apr 11, 2018 at 17:59


You must log in to answer this question.