1
$\begingroup$

Three gamblers each start with $a$, $b$ and $c$ chips, respectively. In each round of the game, a gambler is selected uniformly at random to give up one chip, and one of the remaining two gamblers is selected uniformly at random to receive that chip. The game ends when there are only two players remaining with chips, that is, one player goes bankrupt. Let $X_n$, $Y_n$ and $Z_n$ be the respective number of chips the three players have after round $n$, so $(X_0, Y_0, Z_0) = (a, b, c)$.

Here, we have $M_n = X_nY_nZ_n + \frac{1}{3}n(a + b + c)$ being a martingale, and we can define $N := \inf\{n : X_nY_nZ_n = 0\}$ to be a stopping time of $M_n$. I want to show that the game terminates almost surely, i.e. $\mathrm{E}[N] < \infty$. I'm not sure how I can go about doing that.

In my attempt, I observe that I can (somewhat) extend this to a two-player gambler's ruin by "lengthening" the game to where the game ends when one gambler gets all the chips, and the game will still terminate almost surely. However, it's not exactly the same as two-player, so I'm not sure how to proceed.

Any help would be appreciated.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Note that in general, "the game terminates almost surely" and "$E[N] < \infty$" are not equivalent. In this case, though, you have a finite Markov chain with one absorbing state (bankruptcy) which is accessible from every other state. Then the hitting time of that state must have finite expected value. One way to see it is to change the game so that when one player goes bankrupt, the game starts over; then you have an irreducible finite-state Markov chain, which must be positive recurrent. $\endgroup$
    – Nate Eldredge
    Commented Oct 21, 2019 at 15:59
  • 2
    $\begingroup$ Alternatively, note that $M_{n \wedge N}$ is a martingale, and that $M_{n \wedge N} \ge \frac{1}{3}(n \wedge N) (a+b+c)$. Hence $\frac{1}{3}(a+b+c) E[n \wedge N] \le E[M_{n \wedge N}] = E[M_0] = abc$. By monotone convergence $E[n \wedge N] \to E[N]$, so we conclude $\frac{1}{3}(a+b+c) E[N] \le abc$ and in particular $E[N] < \infty$. $\endgroup$
    – Nate Eldredge
    Commented Oct 21, 2019 at 16:10
  • 1
    $\begingroup$ I'm sure you saw that already, but in fact once you know that $N<\infty$ a.s. by either method, the same martingale argument gives you $abc=\frac{a+b+c}3E[n\wedge N]+E[P_{n\wedge N}]$, where $P_k$ is the product $X_kY_kZ_k$. So the expectation of $N$ is actually precisely $3abc/(a+b+c)$. $\endgroup$
    – Pierre PC
    Commented Oct 30, 2019 at 15:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .