4
$\begingroup$

I have the following problem (perhaps it could be seen as a variant of the geometric distribution):

I'd like to know the expected number of trials needed to get the (single) special ticket among n tickets. Tickets are drawn without replacement.

The distribution of a generalized version of this problem is here: https://math.stackexchange.com/a/436247

The given distribution is: $p_i \prod_{k=1}^{i-1}(1 - p_k)$, where $p_i$ is the probability of success at i-th trial. This looks like a generalized version of the geometric random variable.

In my specific case, $p_i = \frac{1}{n-i+1}$, because on each trial, the number of tickets to draw reduces by 1.

It might seem trivial, but I'm having trouble to calculate the mean of "my" distribution, which would give the expected number of trials until success... This could be a well-known problem already, but I was not able to find a reference for it (I found it's "inverse" here: A Diminishing Geometric Distribution).

So, any help is appreciated.

EDIT: took out the sentence "until I'll certainly get the special ticket on the last trial" because one could infer that $p_n = 1$, implying $p_i = 0$ for $i < n$, which is not the case.

EDIT: took out the sentence "on the 1st trial the chance of selecting the special ticket is $1/n$, on 2nd it is $1/(n-1)$ and so on." because it can be misleading. See @Karn Watcharasupat's answer and comments below.

$\endgroup$
  • 1
    $\begingroup$ $p_n=1$ so it is for certain that you get your special ticket at the last trial. So $p_i=0$ for $i<n$ if there is only one trial at which you get your special ticket. Is that the case? Realize that in a normal setting $\frac1{n-1}$ is the probability to get the ticket at second trial under condition that you did not receive it at the first trial allready. The unconditional probability is $\frac1{n}$ for every trial. $\endgroup$ – drhab Nov 13 '17 at 12:44
  • $\begingroup$ I have not expressed myself precisely: $p_i$ is not $0$ for $i < n$... One could infer that because I said that "certainly I'll take the special ticket in the last trial"; but this will only happen if I fail the previous $n-1$ trials. I'll edit the question to better reflect this idea. Besides, my case is the conditional one (the probability of finding the ticket increases as I take out "ordinary" ones). $\endgroup$ – andertavares Nov 13 '17 at 13:05
  • $\begingroup$ Is it possible to select the special ticket on the first trial and on the second trial? $\endgroup$ – drhab Nov 13 '17 at 13:22
  • $\begingroup$ There's a single special ticket, without replacement. After we draw the special ticket, the experiment is over. So, I'd like to know how many trials, in expectation, are needed to draw the special ticket? $\endgroup$ – andertavares Nov 13 '17 at 13:42
  • $\begingroup$ Then we need $p_1+\cdots+p_n=1$, right? Can you give me any reason why $p_1\neq p_2$. $\endgroup$ – drhab Nov 13 '17 at 13:59
1
$\begingroup$

Let $N$ denote the number of trials needed.

Think of this as placing the selected ticket on one of numbered spots $1,2,\dots,n$ such that every spot has equal chances to be elected for that.

Let spot $i$ be the place of the $i$-th drawn ticket.

Then $\mathsf P(N=i)=\frac1{n}$ for $i=1,2,\dots,n$.

So the expectation is: $$\mathsf EN=\sum_{i=1}^nP(N=i)i=\frac1{n}(1+2+3+\cdots+n)=\frac12(n+1)$$

Also we have $P(N=i\mid N\geq i)=\frac1{n-i+1}$ but that is irrelevant.

$\endgroup$
1
$\begingroup$

Thanks to @drhab for pointing out my mistake.

So this is from what I understand... Let $X$ denotes the number of trial up to and including the trial where the special ticket is successfully obtained. \begin{align} & P(X=r)={{p}_{r-1}}\prod\limits_{i=1}^{i=r-1}{\left( 1-{{p}_{i}} \right)} \\ & =\frac{1}{n-r+1}\prod\limits_{i=1}^{i=r-1}{\left( 1-\frac{1}{n-i+1} \right)} \\ & =\frac{1}{n-r+1}\prod\limits_{i=1}^{i=r-1}{\left( \frac{n-i+1-1}{n-i+1} \right)} \\ & =\frac{1}{n-r+1}\prod\limits_{i=1}^{i=r-1}{\left( \frac{n-i}{n-i+1} \right)} \\ & =\frac{1}{n-r+1}\left( \frac{n-1}{n-1+1}\times \frac{n-2}{n-2+1}\times \frac{n-3}{n-3+1}\times \cdots \times \frac{n-r}{n-r+1} \right) \\ & =\frac{1}{n-r+1}\left( \frac{\require{enclose} \enclose{horizontalstrike}{n-1}}{n}\times \frac{\enclose{horizontalstrike}{n-2}}{\enclose{horizontalstrike}{n-1}}\times \frac{\enclose{horizontalstrike}{n-3}}{\enclose{horizontalstrike}{n-2}}\times \cdots \times \frac{n-(r-1)}{\enclose{horizontalstrike}{n-(r-1)+1}} \right) \\ & =\frac{n-r+1}{n\left( n-r+1 \right)} \\ & =\frac{1}{n} \end{align} Now, for the expectation $\operatorname{E}(X)$: \begin{align} & \operatorname{E}(X)=\sum\limits_{r=1}^{n}{rP(X=r)} \\ & =\sum\limits_{r=1}^{n}{\frac{r}{n}} \\ & = \frac{1}{n} \frac{n}{2} (n+1)\\ & =\frac{n+1}{2} \end{align}

$\endgroup$
  • $\begingroup$ Do we have $P(X=1)+\cdots+P(X=n)=1$ here? (as we should). I am afraid not. $\endgroup$ – drhab Nov 13 '17 at 14:03
  • $\begingroup$ @drhab It is not. Let me check something...I'm having a feeling that $P(X=r)=frac{1}{n}$ i.e. does not change at all regardless of the trial. $\endgroup$ – Karn Watcharasupat Nov 13 '17 at 14:11
  • $\begingroup$ I like both yours and @drhab's answers. I'll mark his as he pointed out the issue in yours, is that ok? $\endgroup$ – andertavares Nov 13 '17 at 16:52
  • 1
    $\begingroup$ @andertavares yep please mark his :) $\endgroup$ – Karn Watcharasupat Nov 14 '17 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.