Probability, Markov chain

Sarah

New member
A teacher leaves out a box of N stickers for children to take home as treats. Children form a queue and look at the box one by one. When a child finds k⩾1 stickers in the box, he or she takes a random number of stickers that is uniformly distributed on {1,2,…,k}.

1- What is the expectation of the number of stickers taken by the second child, as a function of the initial number of stickers N?

2- If E_N denotes the expected number of children who take at least one sticker from the box given that it initially contained N stickers. How can I compute a formula to represent E_N+1 in terms of E_1+⋯+E_N. Also, how E_N can be expressed in terms of k?

MarkFL

Staff member
Hello and welcome to MHB, Sarah!

In order for our helpers to provide you with the best help, we ask that you show what you have tried so far, or what your thoughts are on how to begin. This way, we can show you what you may be doing wrong, or provide you with a hint or suggestion on how to proceed.

chisigma

Well-known member
A teacher leaves out a box of N stickers for children to take home as treats. Children form a queue and look at the box one by one. When a child finds k⩾1 stickers in the box, he or she takes a random number of stickers that is uniformly distributed on {1,2,…,k}.
Very interesting problem!... in order to understand correcly however let's do an example: the first child finds N stichers... that meants that he/she takes a random number of stickers uniformly distributed on {1,2,...,N}?... and that meants that, if the first child selects k stichers, the number of stickers selected by the second child is uniformly distributed in {1,2,...,N-k}?...

Kind regards

$\chi$ $\sigma$

chisigma

Well-known member
A teacher leaves out a box of N stickers for children to take home as treats. Children form a queue and look at the box one by one. When a child finds k⩾1 stickers in the box, he or she takes a random number of stickers that is uniformly distributed on {1,2,…,k}.

1- What is the expectation of the number of stickers taken by the second child, as a function of the initial number of stickers N?
Under the assumption that what I written in post #3 is true, let's try to answer to the question 1. The mean value of object selected among k is...

$\displaystyle E\{n\} = \sum_{n=1}^{k} \frac{n}{k} = \frac{k\ (k+1)}{k\ 2} = \frac{k+1}{2}$ (1)

If $n_{1}$ is the number of objects selected by the first child, then the second child can choose among $N-n_{1}$ objects so the mean numbers of object choosen by ther second child is...

$\displaystyle E \{n_{2}\} = \frac{1}{2\ N}\ \sum_{n=1}^{n} (N-n+1) = \frac{1}{2\ N}\ \frac{N\ (N+1)}{2} = \frac{N+1}{4}$ (2)

Kind regards

$\chi$ $\sigma$

Sarah

New member
Thank you for your comment, but I think the distribution for the first child should be between [1,N]. I was thinking to go ahead with the following argument:

n1 is the number of objects taken by the first child and it is uniformly distributed in [1, N], but n2 is uniformly distributed in [1, N-n1]. so we have to evaluate:
E(n2)= E( E(n2|N-n1))