Skip to main content
3 of 3
deleted 4 characters in body
RaphaelB4
  • 4.4k
  • 12
  • 25

Just a remark : with your weights (0,...,n) you have an simple formula to calculate the expectation. $$v_1(1b_1b_2\cdots b_n)=1+v_1(b_1\cdots b_n) $$ $$v_1(0b_1b_2\cdots b_n)=\frac{1}{n+2}+\frac{n+3}{n+2}v_1(b_1 \cdots b_n) $$ Proof : Let us call $Y$ the value obtained by the first player with a sequence $b_1 \cdots b_n$. Now consider the same sequence where we add a digit at the beginning. We note $\tilde{Y}$ the new value of the first player.

If it is a $1$, the first player will erase the $0$ stack and we are reduce to the previous problem but with stack $k+1$ instead of $k$. and then $\tilde{Y}=Y+1$. And therefore

$$v_1(1b_1b_2\cdots b_n)=\mathbb{E}(\tilde{Y})=\mathbb{E}(Y)+1= v_1(b_1\cdots b_n)+1 $$

If it is a 0, then the second player erase randomly one stack $X$. We are reduce to the previous problem but with stack $k$ if $k<X$ and $k+1$ if $k\geq X$ instead of $k$. The rest of the game follow identically but at the end $\tilde{Y}=Y$ if $X> Y$ or $\tilde{Y}=Y +1$ if $Y\geq X$. Therefore $$\mathbb{E}(\tilde{Y})=\sum_{i=0}^{n}i\times\mathbb{P}(Y=i)\mathbb{P}(X>i)+(i+1)\times\mathbb{P}(Y=i)\mathbb{P}(X\leq i) $$ $\mathbb{P}(X\leq i)=\frac{i+1}{n+2}$and we have

$$\mathbb{E}(\tilde{Y})=\sum_{i=0}^{n}i\times\mathbb{P}(Y=i)+\mathbb{P}(Y=i)\frac{i+1}{n+2}$$ and then $$\mathbb{E}(\tilde{Y})=\frac{n+3}{n+2}\mathbb{E}(Y)+\frac{1}{n+2}$$ which can be written as $$\mathbb{E}(\tilde{Y}+1)=(\frac{n+3}{n+2})\mathbb{E}(Y+1)$$ Exemple : $$v(01101)+1=\frac{7}{6}\times(1+1+\frac{4}{3}\times 2)=\frac{98}{18} $$ so $v(01101)=\frac{40}{9}$ (as numerically calculated by Claude).

RaphaelB4
  • 4.4k
  • 12
  • 25