Hi all, we complicated a simple problem in Probability in the previous post. Here again, we do the same thing.
The setup is this. Consider the unit interval $(0, 1)$. We start at the origin and choose $n$ random points in the interval that lies to the right. We now choose the $k$th point nearest to the origin and move there. We again choose $n$ points in the interval that lies to the right and keep moving to the right until we get inside an interval $[0, x)$ for a given $x$.
Let $\mathbb{E}_{n,k}(x)$ be the expected number of times we have to generate the numbers (or in other words, the moves we have to make). So as you may have guessed, this post about finding this number.
Okay, the procedure pretty much follows what we saw the previous time. It gets all messy and I'm not even sure how to present it. So I'm directly giving the result.
Let $P_{n,k}(z)$ denote the characteristic equation. We have,
$P_{n,k}(z)=\displaystyle\frac{z^\underline{n}}{n!}-(-1)^{n-k}\sum_{j=0}^{n-k}(-1)^j\binom{n-1-j}{k-1}\frac{z^\underline{j}}{j!}$
where $z^\underline{n}$ is the falling factorial.
Let $\eta_1,\eta_2,\cdots,\eta_n$ be the $n$ roots of the equation $P_{n,k}(z)=0$. Then we have,
$\begin{align}
\mathbb{E}_{n,k}(x)=\displaystyle\frac{H_n-\log{x}}{H_n-H_{n-k}}&+\frac{x^n}{n!}\sum_{r=1}^n\frac{x^{-\eta_r}\eta_r^\underline{n}}{\eta_rP'_{n,k}(z)}\\
&-\displaystyle\frac{x^nn^{n-1}}{n!(H_n-H_{n-k})}\sum_{r=1}^n\sum_{i=0}^{n-1}\sum_{j=0}^i\frac{(n-i)x^{-\eta_r}\eta_r^\underline{n}\eta_r^{j-1}a_{i-j}}{n^{i}P'_{n,k}(\eta_r)}
\end{align}$
where $a_m=[z^{n-m}]P_{n,k}(z)$ and $H_n$ is the $n$th Harmonic number.
Using this, we can see that
$\mathbb{E}_{n,1}(x)=1-n\log{x}$
$\mathbb{E}_{n,2}(x)=1+\displaystyle\frac{n(n-1)}{(2n-1)^2}(x^{2n-1}-1)-\frac{n(n-1)\log{x}}{2n-1}$
Considering the number of identities involving the falling factorials, there seems to enough room for simplifying the above formula but am not able to see things clearly. I think adding an animation would make it more easy to see what the 'procedure' means and am on it. I'll update it as soon as possible.
Until then
Yours Aye
Me
The setup is this. Consider the unit interval $(0, 1)$. We start at the origin and choose $n$ random points in the interval that lies to the right. We now choose the $k$th point nearest to the origin and move there. We again choose $n$ points in the interval that lies to the right and keep moving to the right until we get inside an interval $[0, x)$ for a given $x$.
Let $\mathbb{E}_{n,k}(x)$ be the expected number of times we have to generate the numbers (or in other words, the moves we have to make). So as you may have guessed, this post about finding this number.
Okay, the procedure pretty much follows what we saw the previous time. It gets all messy and I'm not even sure how to present it. So I'm directly giving the result.
Let $P_{n,k}(z)$ denote the characteristic equation. We have,
$P_{n,k}(z)=\displaystyle\frac{z^\underline{n}}{n!}-(-1)^{n-k}\sum_{j=0}^{n-k}(-1)^j\binom{n-1-j}{k-1}\frac{z^\underline{j}}{j!}$
where $z^\underline{n}$ is the falling factorial.
Let $\eta_1,\eta_2,\cdots,\eta_n$ be the $n$ roots of the equation $P_{n,k}(z)=0$. Then we have,
$\begin{align}
\mathbb{E}_{n,k}(x)=\displaystyle\frac{H_n-\log{x}}{H_n-H_{n-k}}&+\frac{x^n}{n!}\sum_{r=1}^n\frac{x^{-\eta_r}\eta_r^\underline{n}}{\eta_rP'_{n,k}(z)}\\
&-\displaystyle\frac{x^nn^{n-1}}{n!(H_n-H_{n-k})}\sum_{r=1}^n\sum_{i=0}^{n-1}\sum_{j=0}^i\frac{(n-i)x^{-\eta_r}\eta_r^\underline{n}\eta_r^{j-1}a_{i-j}}{n^{i}P'_{n,k}(\eta_r)}
\end{align}$
where $a_m=[z^{n-m}]P_{n,k}(z)$ and $H_n$ is the $n$th Harmonic number.
Using this, we can see that
$\mathbb{E}_{n,1}(x)=1-n\log{x}$
$\mathbb{E}_{n,2}(x)=1+\displaystyle\frac{n(n-1)}{(2n-1)^2}(x^{2n-1}-1)-\frac{n(n-1)\log{x}}{2n-1}$
Considering the number of identities involving the falling factorials, there seems to enough room for simplifying the above formula but am not able to see things clearly. I think adding an animation would make it more easy to see what the 'procedure' means and am on it. I'll update it as soon as possible.
Until then
Yours Aye
Me
No comments:
Post a Comment