Consider an urn with $w$ red and $w$ black balls. We repeatedly draw balls out of said urn without replacement. (For clearity we stre that after $2w$ draws the urn is empty.) We get $ 1\$ $ for every red ball and we have to pay $ 1\$ $ for every black ball; if we draw all balls we get nothing. Compute the maximum expected payoff via backward recursion and compute it explicitly for $n = 100$.
I recognise that this exercise is intended to be solved with help of the following theorem:
Consider a "game" (such as the one above) with $N$ draws and let $Z_n$ denote the amount of money the player recieves if he stops at time $n$. Then $U_0 := \max_T \mathbb{E}[Z_T]$, where $T$ runs over all stopping times $T \le N$, models the maximum expected payoff. More generally we model the information flow of the player by a finite filtration $\mathcal{F}$ and let$U_n := \max_{T_n} \mathbb{E}[Z_T \mid \mathcal{F}_n]$ for $0 \le n \le N$, where $T_n$ denotes the set of stopping times in $\{n, \ldots, N\}$.
We can determine $(U_n)_n$ via backwards recursion $U_N = Z_N$ and $$U_{n-1} = \max(Z_{n-1}, \mathbb{E}[U_n \mid \mathcal{F}_{n-1}])$$ for $1 \le n \le N$.
I think we should model the urn draws by the RVs $(X_n)_{1 \le n \le N}$ that map into $\{\pm 1\}$, but I do not get how to choose the probability of the $(X_n)_n$; the assumption that we do not put back the balls makes this difficult for me. Furthermore, I guess we should set $\mathcal{F}_0 = \{\Omega,\emptyset \}$, $\mathcal{F}_n = \sigma(X_1, \ldots, X_n)$ for $n \ge 1$ and $Z_n = \sum_{k=1}^n X_k$. Could you please tell me how to choose the pmf of the $(X_n)_n$?
