Smoker has two matchboxes
А smoker has two matchboxes in his pocket, each containing $n$
mathes. When he wants to smoke, he selects randomly one of the boxes,
and takes a match from it. At some point he finds out, that one of the
boxes is empty. What is the probability that in the other box there are
exactly $r$ matches left (for $r\in\{0,1,\ldots,n\}$). What about the
expected number of the matches in the other box.
If $X$ is the random variable "number of matches in the other box", then one directly finds that $$\text{P}(X=r)={2n-r \choose n-r}\frac{1}{2^{2n-r}}$$
Now we will evaluate $$\text{E}X=\sum_{r=0}^{n}r{2n-r \choose n-r}\frac{1}{2^{2n-r}}$$
The sum of all probabilities being $1$ means here that $$\sum_{r=0}^{n}{2n-r \choose n-r}\frac{1}{2^{2n-r}}=1 $$
Change the variables $r=n-d$ in the last and and we obtain $$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=1 \ \ \ \ \ \ \ (*)$$ Make the same change in the sum for the expectation $$\text{E}X=\sum_{d=0}^{n}(n-d){n+d \choose d}\frac{1}{2^{n+d}}=n-\sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}$$
It remains to calculate the last sum which could be rewritten in the form $$\frac{1}{2^n n!}\sum_{d=0}^{n}d\frac{(n+d)!}{2^{d}d!}$$ First of all rewrite $(*)$ in the form
$$\sum_{d=0}^{n}\frac{(n+d)!}{2^d d!}=2^n n!$$
Write the same for $n+1$
$$\sum_{d=0}^{n+1}\frac{(n+d+1)!}{2^d d!}=2^{n+1} (n+1)!$$ and manipulating it we obtain
$$\sum_{d=0}^{n}(n+d+1)\frac{(n+d)!}{2^d d!}+\frac{(2n+2)!}{2^{n+1}(n+1)!}=\sum_{d=0}^{n}d\frac{(n+d)!}{2^d d!}+(n+1)\sum_{d=0}^{n}\frac{(n+d)!}{2^d d!}+\frac{(2n+2)!}{2^{n+1}(n+1)!}=\\= \sum_{d=0}^{n}d\frac{(n+d)!}{2^d d!}+(n+1)2^n n!+\frac{(2n+2)!}{2^{n+1}(n+1)!}=2^{n+1} (n+1)!$$
From the last we find $$ \sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}=\frac{1}{2^n n!}\left(2^{n+1} (n+1)!-2^n (n+1)!-\frac{(2n+2)!}{2^{n+1}(n+1)!}\right)$$
hence $$\text{E}X=n-\frac{1}{2^n n!}\left(2^n (n+1)!-\frac{(2n+2)!}{2^{n+1}(n+1)!}\right)=n-(n+1)+\frac{(2n+2)!}{2^{2n+1}(n+1)!n!}=\\=-1+\frac{n+1}{4^n}{2n+1\choose n}$$
Using the Stirling approximation one finds that $$\text{E}X \sim \frac{ 2\sqrt{n}}{\sqrt{\pi}}$$
Comments. One can similarly find the variance of $X$ - just write out $(*)$ for $n+2$ so that squares of $d$ appear.
In essence the problem breaks down to evaluating $$ \sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}$$ Observe that this is quite easier if the sum was infinite - then this could be obtained from differentiating the series of $(1-s)^{-(n+1)}$ (up to some translation).
Another interesting piece of the problem is the identity $(*)$
$$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=1$$
From probabilistic point of view this is trivial. Is there any other way to evaluate it? This could lead to a different tackling of the previous sum (not using $(*)$). One more thing to note - if the sum in $(*)$ was infinite (it is easier to find as well) it is 2, and up to $n$ it is 1.
Something that could be related is Negative binomial distribution.
Addendum (11/17/2018) Probabilistic expanation of the identity $$ \sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=\frac{1}{2}\sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d}}.$$ (Based on ideas of Emilian Rogachev)
Consider we perform a walk on the integer points of the Cartesian plane, being allowed only moves up and right. If we count the probability of going through the line $x=n+1$ before we go through $y=n+1$ it is $$ \sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$ The probability that we will ever go through $x=n+1$ is $1$ and could be written as $$ \sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$ However, since everything is symmetric, we see that going through $x=n+1$ before $y=n+1$ is equiprobable with going through $y=n+1$ before $x=n+1$ and since both sum up to $1$, each of those probabilities is $1/2$. So $$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d+1}}=\frac{1}{2}\sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$
If $X$ is the random variable "number of matches in the other box", then one directly finds that $$\text{P}(X=r)={2n-r \choose n-r}\frac{1}{2^{2n-r}}$$
Now we will evaluate $$\text{E}X=\sum_{r=0}^{n}r{2n-r \choose n-r}\frac{1}{2^{2n-r}}$$
The sum of all probabilities being $1$ means here that $$\sum_{r=0}^{n}{2n-r \choose n-r}\frac{1}{2^{2n-r}}=1 $$
Change the variables $r=n-d$ in the last and and we obtain $$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=1 \ \ \ \ \ \ \ (*)$$ Make the same change in the sum for the expectation $$\text{E}X=\sum_{d=0}^{n}(n-d){n+d \choose d}\frac{1}{2^{n+d}}=n-\sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}$$
It remains to calculate the last sum which could be rewritten in the form $$\frac{1}{2^n n!}\sum_{d=0}^{n}d\frac{(n+d)!}{2^{d}d!}$$ First of all rewrite $(*)$ in the form
$$\sum_{d=0}^{n}\frac{(n+d)!}{2^d d!}=2^n n!$$
Write the same for $n+1$
$$\sum_{d=0}^{n+1}\frac{(n+d+1)!}{2^d d!}=2^{n+1} (n+1)!$$ and manipulating it we obtain
$$\sum_{d=0}^{n}(n+d+1)\frac{(n+d)!}{2^d d!}+\frac{(2n+2)!}{2^{n+1}(n+1)!}=\sum_{d=0}^{n}d\frac{(n+d)!}{2^d d!}+(n+1)\sum_{d=0}^{n}\frac{(n+d)!}{2^d d!}+\frac{(2n+2)!}{2^{n+1}(n+1)!}=\\= \sum_{d=0}^{n}d\frac{(n+d)!}{2^d d!}+(n+1)2^n n!+\frac{(2n+2)!}{2^{n+1}(n+1)!}=2^{n+1} (n+1)!$$
From the last we find $$ \sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}=\frac{1}{2^n n!}\left(2^{n+1} (n+1)!-2^n (n+1)!-\frac{(2n+2)!}{2^{n+1}(n+1)!}\right)$$
hence $$\text{E}X=n-\frac{1}{2^n n!}\left(2^n (n+1)!-\frac{(2n+2)!}{2^{n+1}(n+1)!}\right)=n-(n+1)+\frac{(2n+2)!}{2^{2n+1}(n+1)!n!}=\\=-1+\frac{n+1}{4^n}{2n+1\choose n}$$
Using the Stirling approximation one finds that $$\text{E}X \sim \frac{ 2\sqrt{n}}{\sqrt{\pi}}$$
Comments. One can similarly find the variance of $X$ - just write out $(*)$ for $n+2$ so that squares of $d$ appear.
In essence the problem breaks down to evaluating $$ \sum_{d=0}^{n}d{n+d \choose d}\frac{1}{2^{n+d}}$$ Observe that this is quite easier if the sum was infinite - then this could be obtained from differentiating the series of $(1-s)^{-(n+1)}$ (up to some translation).
Another interesting piece of the problem is the identity $(*)$
$$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=1$$
From probabilistic point of view this is trivial. Is there any other way to evaluate it? This could lead to a different tackling of the previous sum (not using $(*)$). One more thing to note - if the sum in $(*)$ was infinite (it is easier to find as well) it is 2, and up to $n$ it is 1.
Something that could be related is Negative binomial distribution.
Addendum (11/17/2018) Probabilistic expanation of the identity $$ \sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d}}=\frac{1}{2}\sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d}}.$$ (Based on ideas of Emilian Rogachev)
Consider we perform a walk on the integer points of the Cartesian plane, being allowed only moves up and right. If we count the probability of going through the line $x=n+1$ before we go through $y=n+1$ it is $$ \sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$ The probability that we will ever go through $x=n+1$ is $1$ and could be written as $$ \sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$ However, since everything is symmetric, we see that going through $x=n+1$ before $y=n+1$ is equiprobable with going through $y=n+1$ before $x=n+1$ and since both sum up to $1$, each of those probabilities is $1/2$. So $$\sum_{d=0}^{n}{n+d \choose d}\frac{1}{2^{n+d+1}}=\frac{1}{2}\sum_{d=0}^{\infty}{n+d \choose d}\frac{1}{2^{n+d+1}}.$$
Comments
Post a Comment