Hard Question in Stochastic processes - variance Martingales

Solution 1:

In addition to the hints, we need the following identities related to derangements:

(1) $\displaystyle\sum_{i=0}^{n}\frac{!i}{i!~(n-i)!}=1,~(n\ge0),$

(2) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)}{i!~(n-i)!}=1,~(n\ge1),$

(3) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)~(n-i-1)}{i!~(n-i)!}=1,~(n\ge2),$

where I have adopted the subfactorial notation. The proof of (1) is by considering among all the possible permutations of $n$ distinct items, what the probability $p^{(n)}_{i}$ is of a random permutation in which exactly $n-i$ items are in their original ordered positions. It's easy to see $p^{(n)}_{i}$ is exactly the term within the summation. For (2), note we can change the upper bound of summation to $n-1$, cancel the $n-i$ term in the numerator with the factorial in the denominator then apply (1) by replacing $n$ with $n-1$. Similar proof for (3). We can now rewrite these identities as:

(1') $\sum_{i=0}^{n}p^{(n)}_{i}=1,~(n\ge0),$

(2') $\sum_{i=0}^{n}p^{(n)}_{i}i=n-1,~(n\ge1),$

(3') $\sum_{i=0}^{n}p^{(n)}_{i}i^2=(n-1)^2+1,~(n\ge2),$

where we have used (1) and (2) to get (2') and (1), (2) and (3) to get (3').

(a) Follow your hints, we use first step analysis on $X_n$:

$\mathbb{E}\left[X_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i=X_n-1,$

where $n<T$, i.e., $X_n>=2$. Therefore $(X_n+n)1_{n<T}$ is a martingale and by applying the optional stopping theorem, we get $\mathbb{E}[T]=X_0=10$, as $X_T=0$ is the stopping condition.

(b) I believe the hint is to consider the variance of $X_n$. We apply first step analysis on $X^2_n$:

$\mathbb{E}\left[X^2_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i^2=(X_n-1)^2+1.$

We also have

$\mathbb{E}\left[Y_{n+1}\mid Y_n,X_n\right]=Y_n+X_n,$

where $Y_n$ is the total number of ales consumed after $n$th round. Therefore $(Y_n+X^2_n/2+X_n)1_{n<T}$ is a martingale and $\mathbb{E}[N]=\mathbb{E}[Y_T]=X^2_0/2+X_0=60$.