Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a system of linear equations as follows.

$$M(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{2}{n} N(p-1) + \frac{p-1}{n}M(p-1)$$ $$N(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{p}{n}N(p-1)$$ $$M(1) = 1+\frac{n-2}{n}M(n-1) + \frac{2}{n}N(0)$$ $$N(0) = 1+\frac{n-1}{n}M(n-1)$$

$M(p)$ is defined for $1 \leq p \leq n-1$. $N(p)$ is defined for $0 \leq p \leq n-2$. What is $M(n-1)$?

share|improve this question
1  
where did you get this? –  Will Jagy Jan 3 '13 at 20:06
1  
Expectations of hitting times for Markov chains? –  Did Jan 3 '13 at 20:08
1  
If we are given $N(0)$ and $n$ we can solve the last for $M(n-1)=\frac n{n-1}(N(0)-1)$. Please look over the equations to get the recurrence right. Normally you wouldn't have $M(n-1)$ on the right and $M(p)$ would just depend upon $M(p-1)$ and $N(p)$ or $N(p-1)$ –  Ross Millikan Jan 3 '13 at 20:11
    
@RossMillikan For a fixed $n$ you get $2(n-1)$ equations in $2(n-1)$ unknowns I think so it seems to be at least theoretically solvable. –  user55085 Jan 3 '13 at 22:05
1  
This reformulation of the problem might be useful: We're looking for two particular elements of a set with n elements. In each time step we uniformly randomly draw one element with replacement. If we draw the same irrelevant element twice before finding both of our elements, we have to start over. What's the expected time before we find the two elements? –  joriki Feb 24 '13 at 13:01
show 3 more comments

2 Answers

up vote 4 down vote accepted
+50

We shall prove that

$$M(n-1)=\frac{n(n-2)f(n)+n^2}{2(n-f(n))}$$

where

$$f(n)=\sum\limits_{i=1}^{n}{\frac{n!}{(n-i)!n^i}} \approx \sqrt{\frac{\pi n}{2}}-\frac{1}{3}+\frac{1}{12}\sqrt{\frac{\pi}{12n}}-\frac{4}{135n}$$

Refer to Wikipedia (same link as @joriki). Also refer to http://algo.inria.fr/flajolet/Publications/FlGrKiPr95.pdf

This would imply that $$M(n-1) \sim \frac{n(n-2)f(n)+n^2}{2n}=\frac{n-2}{2}f(n)+\frac{n}{2} \sim \sqrt{\frac{\pi n^3}{8}}$$

Edit: We can get better asymptotics as follows: (Note that $f(n)$ is asymptotically less than $n$)

\begin{align} & M(n-1) \\ & =\frac{n(n-2)f(n)+n^2}{2(n-f(n))}\\ & =\frac{(n-2)f(n)+n^2}{2(1-\frac{f(n)}{n})}\\ & =(\frac{n-2}{2}f(n)+\frac{n}{2})\sum_{i=0}^{\infty}{\left(\frac{f(n)}{n}\right)^i} \\ & =\frac{n}{2}f(n)+\frac{f(n)^2}{2}+\frac{f(n)^3}{2n}+\frac{f(n)^4}{2n^2}-f(n)-\frac{f(n)^2}{n}+\frac{n}{2}+\frac{f(n)}{2}+\frac{f(n)^2}{2n}+O(n^{-\frac{1}{2}}) \\ & =\sqrt{\frac{\pi}{8}}n^{\frac{3}{2}}+(\frac{1}{3}+\frac{\pi}{4})n+\frac{\sqrt{\pi}}{144}(-60\sqrt{2}+\sqrt{3}+18\sqrt{2}\pi)n^{\frac{1}{2}}+(\frac{28}{135}+\frac{\pi}{144}(\sqrt{6}-72)+\frac{\pi^2}{8})\\ &+O(n^{-\frac{1}{2}}) \end{align}

Proof: We first get an explicit expression for $M(n-1)$, using lots of algebraic manipulation from the system of equations.

Define $S(p)=1+\frac{n-p-1}{n}M(n-1), T(p)=S(p)+\frac{2}{n}N(p-1)$.

The equations then become:

$$M(p)=T(p)+\frac{p-1}{n}M(p-1), N(p)=S(p)+\frac{p}{n}N(p-1), M(1)=T(1), N(0)=S(0)$$

It is now straightforward to prove by induction that:

$$M(p)=\sum_{i=0}^{p-1}{\frac{p(p-1) \ldots (p-i)}{pn^i}T(p-i)}, N(p)=\sum_{i=0}^{p}{\frac{(p+1)p \ldots (p+1-i)}{(p+1)n^i}S(p-i)}$$

Thus

\begin{align} M(n-1) & =\sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}T(n-1-i)} \\ & =\sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}(S(n-1-i)+\frac{2}{n}N(n-2-i))} \\ \end{align}

For convenience we shall break the sum into 2 parts.

1st part: \begin{align} & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}S(n-1-i)} \\ = & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}(1+\frac{i}{n}M(n-1))} \\ = & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}}+\sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)i}{(n-1)n^{i+1}}M(n-1)} \end{align}

2nd part: \begin{align} & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}(\frac{2}{n}N(n-2-i))} \\ = & 2\sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^{i+1}}\sum_{j=0}^{n-2-i}{\frac{(n-1-i)(n-2-i) \ldots (n-1-i-j)}{(n-1-i)n^j}S(n-2-i-j)}} \\ = & 2\sum_{0 \leq i+j \leq n-2}{\frac{(n-1)(n-2) \ldots (n-1-(i+j))}{(n-1)n^{i+j+1}}S(n-2-(i+j))} \\ = & 2\sum_{k=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-k)}{(n-1)n^{k+1}}S(n-2-k)(k+1)} \\ = & 2\sum_{k=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-k)}{(n-1)n^{k+1}}(1+\frac{k+1}{n}M(n-1))(k+1)} \end{align}

Note that: \begin{align} & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}}+2\sum_{k=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-k)}{(n-1)n^{k+1}}(k+1)} \\ = & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}}+2\sum_{i=1}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)}{(n-1)n^i}i} \\ = & \sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-1-i)}{(n-1)n^i}}+2\sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)}{(n-1)n^i}i} \\ = & \sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)}{(n-1)n^i}((n-1-i)+2i)} \\ = & \sum_{i=0}^{n-1}{\frac{(n+i-1)n(n-1) \ldots (n-i)}{(n-1)n^{i+1}}} \end{align}

Also: \begin{align} & \sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)i}{(n-1)n^{i+1}}M(n-1)} \\ & +2\sum_{k=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-k)}{(n-1)n^{k+1}}(\frac{k+1}{n}M(n-1))(k+1)} \\ = & M(n-1)(\sum_{i=0}^{n-2}{\frac{(n-1)(n-2) \ldots (n-1-i)i}{(n-1)n^{i+1}}}+2\sum_{i=1}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)i^2}{(n-1)n^{i+1}}}) \\ = & M(n-1)(\sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-1-i)i}{(n-1)n^{i+1}}}+2\sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)i^2}{(n-1)n^{i+1}}}) \\ = & M(n-1)(\sum_{i=0}^{n-1}{\frac{(n-1)(n-2) \ldots (n-i)i}{(n-1)n^{i+1}}((n-1-i)+2i)}) \\ = & M(n-1)(\sum_{i=0}^{n-1}{\frac{(n+i-1)in(n-1) \ldots (n-i)}{(n-1)n^{i+2}}}) \end{align}

Thus we get: \begin{align} M(n-1)= &\sum_{i=0}^{n-1}{\frac{(n+i-1)n(n-1) \ldots (n-i)}{(n-1)n^{i+1}}} \\ &+M(n-1)(\sum_{i=0}^{n-1}{\frac{(n+i-1)in(n-1) \ldots (n-i)}{(n-1)n^{i+2}}}) \end{align}

This is equivalent to the expression I posted in the comments.

We now continue by converting to $f(n)$.

We have $(n+i-1)=(2n-2)-(n-1-i)$ for $i<n-1$ and $n+i-1=2n-2$ for $i=n-1$. Thus: \begin{align} & \sum_{i=0}^{n-1}{\frac{(n+i-1)n(n-1) \ldots (n-i)}{(n-1)n^{i+1}}} \\ = & 2\sum_{i=0}^{n-1}{\frac{n(n-1) \ldots (n-i)}{n^{i+1}}}-\sum_{i=0}^{n-2}{\frac{n(n-1) \ldots (n-1-i)}{(n-1)n^{i+1}}} \\ = & 2\sum_{i=1}^{n}{\frac{n(n-1) \ldots (n+1-i)}{n^{i}}}-\frac{n}{n-1}\sum_{i=2}^{n}{\frac{n(n-1) \ldots (n+1-i)}{n^{i}}} \\ = & 2\sum_{i=1}^{n}{\frac{n!}{(n-i)!n^i}}-\frac{n}{n-1}\sum_{i=2}^{n}{\frac{n!}{(n-i)!n^i}} \\ = & 2f(n)-\frac{n}{n-1}(f(n)-1) \\ = & \frac{(n-2)f(n)+n}{n-1} \end{align}

We have

\begin{align} (n+i-1)i& =(2n-2)i-(n-1-i)i \\ & =(2n-2)((n-1)-(n-1-i))-(n-1-i)((n-2)-(n-2-i)) \\ & =2(n-1)^2-(3n-4)(n-1-i)+(n-1-i)(n-2-i) \end{align}

for $i<n-2$, and $(n+1-i)i=2(n-1)^2-(3n-4)(n-1-i)$ when $i=n-2$ and $(n+1-i)i=2(n-1)^2$ when $i=n-1$. Thus:

\begin{align} & \sum_{i=0}^{n-1}{\frac{(n+i-1)in(n-1) \ldots (n-i)}{(n-1)n^{i+2}}} \\ = & 2(n-1)\sum_{i=0}^{n-1}{\frac{n(n-1) \ldots (n-i)}{n^{i+2}}}-\frac{3n-4}{n-1}\sum_{i=0}^{n-2}{\frac{n(n-1) \ldots (n-1-i)}{n^{i+2}}} \\ & +\sum_{i=0}^{n-3}{\frac{n(n-1) \ldots (n-2-i)}{(n-1)n^{i+2}}} \\ =& \frac{2(n-1)}{n}\sum_{i=1}^{n}{\frac{n(n-1) \ldots (n+1-i)}{n^i}}-\frac{3n-4}{n-1}\sum_{i=2}^{n}{\frac{n(n-1) \ldots (n+1-i)}{n^i}} \\ & +\frac{n}{n-1}\sum_{i=3}^{n}{\frac{n(n-1) \ldots (n+1-i)}{n^i}} \\ =& \frac{2(n-1)}{n}\sum_{i=1}^{n}{\frac{n!}{(n-i)!n^i}}-\frac{3n-4}{n-1}\sum_{i=2}^{n}{\frac{n!}{(n-i)!n^i}}+\frac{n}{n-1}\sum_{i=3}^{n}{\frac{n!}{(n-i)!n^i}} \\ =& \frac{2(n-1)}{n}f(n)-\frac{3n-4}{n-1}(f(n)-1)+\frac{n}{n-1}(f(n)-1-\frac{n-1}{n}) \\ =& f(n)((2-\frac{2}{n}-(3-\frac{1}{n-1})+(1+\frac{1}{n-1}))+((3-\frac{1}{n-1})-(1+\frac{1}{n-1})-1) \\ =& \frac{2f(n)}{n(n-1)}+(1-\frac{2}{n-1}) \end{align}

Thus

$$M(n-1)=\frac{(n-2)f(n)+n}{n-1}+(\frac{2f(n)}{n(n-1)}+(1-\frac{2}{n-1}))M(n-1)$$

$$M(n-1)=\frac{\frac{(n-2)f(n)+n}{n-1}}{1-(\frac{2f(n)}{n(n-1)}+(1-\frac{2}{n-1}))}=\frac{n(n-2)f(n)+n^2}{2(n-f(n))}$$

share|improve this answer
add comment

As I noted in a comment, we can reformulate the problem as follows: We're looking for two particular elements of a set with n elements. In each time step we uniformly randomly draw one element with replacement. If we draw the same irrelevant element twice before finding both of our elements, we have to start over. What's the expected time before we find the two elements?

Incidentally, I suspect you would have gotten an answer long ago if you'd posed the question in that or a similar form (your comments seem to indicate that this is how you arrived at it) rather than cloaked in a mysterious system of linear equations.

The expected time to draw the same irrelevant element twice goes as $\sqrt n$, and the probability to find the two elements in this time goes to zero for $n\to\infty$, so asymptotically we almost always have to restart, so we don't need to conditionalize on all except the last search being known to restart.

Thus, asymptotically, the expected time to find the two elements is just the expected number of restarts times the expected time until a restart. The expected time until a restart goes as $\sqrt\frac{\pi n}2$ (see Wikipedia). The probability to find the two elements we're looking for before a restart after $t$ draws goes as $(t/n)^2$. Thus we need $\langle t^2\rangle$, the expected value of $t^2$. This is $\langle t\rangle^2+\operatorname{Var}(t)=\frac{\pi n}2+\operatorname{Var}(t)$. Unfortunately I don't know $\operatorname{Var}(t)$ or how to calculate it, and your results seem to indicate that it's not $o(n)$ so we can't neglect it. However, it's reasonable to assume that if it's not $o(n)$, then it goes as $n$, and in that case $\langle t^2\rangle$ would go as $\alpha n$ with some unknown constant $\alpha$.

So the probability of a successful run goes as $\frac\alpha n$, so the expected number of runs goes as $\frac n\alpha$, and the expected duration of each of them goes as $\sqrt{\frac{\pi n}2}$, so in total the expected time goes as $\sqrt{\frac{\pi n^3}{2\alpha^2}}$, which agrees with the functional dependence you found. From numerical results it seems that $\alpha=2$, which would mean that the expected time goes as $\sqrt{\frac{\pi n^3}8}\approx0.627n^{3/2}$, which agrees well with your plot but not so well with your coefficient $0.7$.

share|improve this answer
    
@Majid: From numerical results it seems that $\alpha=2$, which would lead to an expected time $\sqrt{\frac{\pi n^3}8}$, in agreement with the results that Ivan recently announced in a comment under the question; that's in agreement with your plot but not with your coefficient $0.7$ -- could that be incorrectly rounded from $\sqrt\frac\pi8\approx0.627$? –  joriki Feb 24 '13 at 15:47
    
I have edited my answer to include better asymptotics. We have $$M(n-1)=\sqrt{\frac{\pi}{8}}n^{\frac{3}{2}}+(\frac{1}{3}+\frac{\pi}{4})n+\frac{‌​\sqrt{\pi}}{144}(-60\sqrt{2}+\sqrt{3}+18\sqrt{2}\pi)n^{\frac{1}{2}}+(\frac{28}{13‌​5}+\frac{\pi}{144}(\sqrt{6}-72)+\frac{\pi^2}{8}) +O(n^{-\frac{1}{2}})$$ –  Ivan Loh Feb 25 '13 at 1:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.