I'm revising for exams in June and my university, very irritatingly, doesn't provide mark schemes for past questions. I'm stuck a few parts into a question and am not totally confident of my preceding answers. So, I've included everything up to the part I'm totally stuck on - hopefully there aren't too many issues! I've put this bits where I'm confused in italics.
Question: A dentist leaves out a box of N stickers for children to take home. When a child finds $k \geq 1$ stickers in the box, he/she takes a random number of stickers that is uniformly distributed on {1,2,...,k}.
Suppose the box is never refilled.
i) Let $X_{n}$ be the number of stickers in the box when the $n$-th child arrives and $Y_{n}$ be the number of stickers taken by the $n$-th child. Explain why $(X_{n})$ is a Markov chain and $(Y_{n})$ is not.
Answer: $(X_{n})$ is a Markov chain since for any $N \geq 0$, $i_{1},i_{2},...,i_{n+1} \in {1,2,..., k}$ we have that
$\mathbb{P}(X_{n+1}=i_{n+1}|X_{n}=i_{n},X_{n-1}=i_{n-1},..., X_{1}=i_{1})=\mathbb{P}(X_{n+1}=i_{n+1}|X_{n}=i_{n})$.
$(Y_{n})$ is not since if we now let $k=10$ then
$\mathbb{P}(Y_{4}=1|Y_{3}=3,Y_{2}=4,Y_{1}=2)=1 \neq \frac{1}{5} = \mathbb{P}(Y_{4}=1|Y_{3}=3,Y_{2}=1,Y_{1}=1)$.
Is this enough? Do I need to prove the first bit for $(X_{n})$ or can I just state it?
ii) Describe the state space and write down the transition matrix for $(X_{n})$.
Answer: The state space is ${0,1,...k}$ where k is the number of stickers the dentist starts with. Not sure about this answer, "describe" seems to want more? But what?
And the transition matrix is \begin{pmatrix} 1& 0 & . & . & . & . & . &0 \\ 1& 0 & . & . & . & . & . &0 \\ \frac{1}{2}& \frac{1}{2} & 0 & . & . & . & . & 0\\ \frac{1}{3}& \frac{1}{3} & \frac{1}{3} & 0 & . & . & . & 0\\ .& & & . & . & & & .\\ .& & & & . & . & & .\\ .& & & & & . & . & .\\ \frac{1}{k}& . & . & . & . & . & \frac{1}{k} & 0 \end{pmatrix}
iii) Which states of the Markov chain $(X_{n})$ are recurrent, transient and absorbing?
Any $A \subset \left \{0,1,...,k \right \}: 0 \in A$ is both recurrent and absorbing. Any $B \subset \left \{0,1,...,k\right \}: 0 \notin B$ is transient.
Not sure about this. Clearly 0 is the only absorbing point, but I'm unsure as to whether the way I've stated my answer is how they wanted it?
iv) Suppose the dentist starts with $N=4$ stickers. Compute the expected number of children who end up with at least one sticker.
Answer: $1 \times \mathbb{P}(X_{2}=0) +2 \times (\mathbb{P}(X_{2}=2)\mathbb{P}(X_{3}=0)+\mathbb{P}(X_{2}=3)\mathbb{P}(X_{3}=0)+\mathbb{P}(X_{2}=1)\mathbb{P}(X_{3}=0))+ 4 \times (\mathbb{P}(X_{2}=3)\mathbb{P}(X_{3}=2)\mathbb{P}(X_{4}=1))=1 \times \frac{1}{4} + 2 \times (\frac{1}{4} \times \frac{1}{2} + \frac{1}{4} \times \frac{1}{3} + \frac{1}{4} \times 1) + 4 \times (\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2})=\frac{4}{3}$
(Fairly confident in this one)
v) Compute the expectation of $Y_{2}$, the number of stickers taken by the second child, as a function of the initial number $N$.
Okay, I think I've got a bit further with this one, but not sure how/if to simplify it:
$\mathbb{E}(Y_{2})= \sum_{r=0}^{N}\sum_{k=0}^{N}r\mathbb{P}(Y_{2}=r|Y_{1}=k)\mathbb{P}(Y_{1}=k)=\frac{1}{N}(1+\sum_{r=1}^{N-1}\sum_{k=r}^{N-1}(r \times \frac{1}{k})$
Thanks for your help in advance.
Note that the question defines $N$ as the initial number of stickers and $k$ is used as a variable describing the number of remaining stickers. In your answer, you use several times $k$ for what the question calls $N$. Of course notation is arbitrary, but it is better to be consistent: use the same notation as is used in the question.
i) For the first bit ($X_n$), I don't know what is expected in your exams, but you might want to add a short explanation that this follows from the assumptions in the question: each kid indeed selects randomly and thus what the kid does depends only on the current state (to be pedantic, this is not explicitly/formally stated in the question, but I'm pretty confident that this assumption is intended). The part for $Y_n$ is fine.
ii) Correct. The description of the state space seems fine, I don't believe anything else is needed.
iii) The subset notation seems strange. You might have understood everything, but this makes me wonder whether you are actually thinking about properties of some sets of states instead of the individual states. Easier to just say that 0 is recurrent & absorbing while $1,2,\ldots,N$ are transient. You might also want to add a short explanation about why this is the case.
iv) You have forgotten the case of 3 kids ending up with stickers! Furthermore, your notation is a bit off: e.g., when you write $P(X_2=3)P(X_3=0)$, you mean $P(X_2=3)P(X_3=0 \mid X_2 = 3)$. $P(X_3 = 0)$ would mean the total probability that $X_3 = 0$, taking into account all possible values of $X_1,X_2$. Some explanation for why, e.g. P(2 kids end up with stickers) is obtained the way you do it, might also be required in an exam solution.
v) I would do this by starting with the so-called tower law $E(Y_2) = E(E(Y_2 \mid Y_1))$, finding the conditional expectation as a function of $Y_1 = y_1$ and then taking the average over possible selections of the first kid.