expected win for an indexed objects game

Question

We have some $n$ objects indexed with $1$ to $n$.We pick randomly objects one by one without replacement. For every drawn object we get 1$, the game ends if the drawn object has a smaller index than the previous drawn one. (ex: if obj. labeled 3 was drawn after obj. labeled 5 game ends)

Let $ X_k= \begin{cases} 1, & \text{if at least $k$\$ are won} \\ 0, & \text{otherwise} \end{cases} $

Q: what the PMF of $X_k$ and what is the expected amount of $ at the end ?

$X_k$ didn't seem easy to calculate at first I took another event.

Let $ Y_k= \begin{cases} 1, & \text{if exactly $k$\$ are won} \\ 0, & \text{otherwise} \end{cases} $

I took a small case where $k=2,n=4$ to see the pattern:

$P(Y_3=1)=\large\frac{{4 \choose 2}}{\frac{4!}{(4-2)!}}$ generalized it to $P(Y_k=1)=\large\frac{{n \choose k}}{\frac{n!}{(n-k)!}}=\frac{1}{k!}$

with $\large{4 \choose 2}$ I just list all pos. comb. $obj_iobj_j$ where $i<j$

given that the above is correct then $X_k=\sum^n_{i=k}{Y_i}$ but when I calculate the expected win I get $e$ which is most likely wrong.

Answer 1

When you draw $k$ objects you win $k$ dollars if you draw them in increasing order, which is one of the $k!$ possible orders, so $X_k=\frac 1{k!}$. Aside from the last one, then $Y_k=\frac 1{k!}-\frac 1{(k+1)!}=\frac k{(k+1)!}$ The special case is $Y_n=\frac 1{n!}$ because you stop without needing to decrease. The expected win is then $$\sum_{i=1}^{n-1}\frac{i^2}{(i+1)!}+\frac n{n!}$$ Alpha gives me a mess for the sum involving incomplete Gamma functions. The limit for large $n$ is $e-1$

Answer 2

The objects are $1,2,\dots , n$ in the sequel.

Note that it is combinatorically not enough to count the "increasing chains of $k$ symbols", since one has then to go at least once down after the last step. There may be for instance no chance to go down... Or a small chance. (From the context it is not clear what happens in the case of the extraction $1<2<\dots<n$, which never goes down, i suppose the game ends as a win for $Y_n$.)

So the probability of $A_k=\{Y_k=1\}$ for a $k<n$ is exactly the one to extract a path $0<s_1<s_2<\dots<s_k$, and after this, one more $s_{k+1}<s_k$, so let us use the notation $S$ for the role of $s_k$:

$$ \Bbb P(A_k)= \frac 1{(n-0)\cdot(n-1)\dots(n-k)} \sum_{S\ge k}\binom {S-1}{k-1}\cdot (S-k)\ . $$ The condition $S\ge k$ can be replaced with $S>k$. For $n=5$ we then compute: $$ \begin{aligned} \Bbb P(A_1) &= \frac 1{5\cdot 4}\left[ \binom 10\cdot 1+ \binom 20\cdot 2+ \binom 30\cdot 3+ \binom 40\cdot 4 \right]=\frac 1{5\cdot 4}(1+2+3+4)=\frac 12\ , \\ \Bbb P(A_2) &= \frac 1{5\cdot 4\cdot 3}\left[ \binom 21\cdot 1+ \binom 31\cdot 2+ \binom 41\cdot 3 \right]=\frac 1{5\cdot 4\cdot 3}(2+6+12) =\frac {20}{5\cdot 4\cdot 3}\ , \\ \Bbb P(A_3) &= \frac 1{5\cdot 4\cdot 3\cdot 2}\left[ \binom 32\cdot 1+ \binom 42\cdot 2 \right]=\frac 1{5\cdot 4\cdot 3\cdot 2}(3+12)=\frac {15}{5\cdot 4\cdot 3\cdot 2}\ ,\\ \\ \Bbb P(A_4) &= \frac 1{5\cdot 4\cdot 3\cdot 2\cdot 1}\left[ \binom 43\cdot 1 \right]=\frac {4}{5\cdot 4\cdot 3\cdot 2\cdot 1}\ , \\ \Bbb P(A_5) &= \frac {1}{5\cdot 4\cdot 3\cdot 2\cdot 1}\ . \end{aligned} $$ This strategy to count is complicated, but i inserted it since it is relatively close to the posted strategy. One other way to count is as follows. Let us consider again a path $$ 0<s_1<s_2<\dots <\boxed{s_k}>s_{k+1}\ . $$ then the subset $\{s_1,s_2,\dots,s_k,s_{k+1}\}$ corresponds to $k$ possible choices of a path as above, here, $s_k$ is the maximal element of the set, $s_{k+1}$ is one of the remaining $k$ elements, and the rest are determined by their order to be placed on the first places of the path. So we can write again, $k<n$: $$ \Bbb P(A_k)=\frac 1{(n-0)(n-1)\dots(n-k)}\cdot \frac 1k\binom n{k+1}\ . $$