Combinatoric task about flock of sheep
Providing that all orders of sheep speeds are equally likely and no pair of sheep have the same speed, the $n$th sheep (counting from the front) is the slowest of its group if and only if all $n-1$ sheep in front of it are all faster than it is, which has probability $\dfrac{1}{n}$
Each group has precisely one slowest sheep, so with $30$ sheep the expected number of groups is $$\displaystyle \sum_{n=1}^{30} \dfrac1n \approx 3.995$$
The answers already provided to this and to the equivalent post about cars in queue
deal with the expected number of groups, and that is what the post asks.
Since the problem is quite interesting, I got curious about the underlying PDF but I did not succeed to find a satisfactory
hint about (admittedly, I might have overlooked something) .
However I tried and develop a different approach
which shows which is the probability distribution behind it.
Consider to "quantize" the speed into $n$ classes.
Then we can represent the $q$ sheeps in queue at time $0$ onto a diagram speed vs. position as in the sketch.
It is clear that the first ship will block all the following ones
with higher or equal speed.
That means all those before the first (n. $4$ in the sketch)
that has a speed lower than n. $1$.
That in her turn will block the following ones with same or higher speed, etc.
Note that we are individuating the resulting groups as the blocks that along the time get
separated by an even larger distance. So in the sketch n. $1$ and n. $3$ are in the same group.
Now the total possible ways of arranging the diagram is $T(n,q)=n^q$.
The number of ways to arrange a group, with leader speed $v$ and $m$ members, is:
$$
G(v,m) = \left( {n - v + 1} \right)^{\,m-1}
$$
Therefore the number of ways $N_{1}(n,q)$ to arrange the sheeps
in such a way that they finally make up only one group will be:
$$
\begin{gathered}
N_{\,1} (n,q) = \sum\limits_{1\, \leqslant \,\,v_{\,1} \, \leqslant \,n} {\left( {n - v_{\,1} + 1} \right)^{\,q - 1} } = \sum\limits_{1\, \leqslant \,\,k\, \leqslant \,n} {k^{\,q - 1} } = \hfill \\
= \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,q - 1} \right)} {\left\langle \begin{gathered}
q - 1 \\
j \\
\end{gathered} \right\rangle \left( \begin{gathered}
n + 1 + j \\
q \\
\end{gathered} \right)} = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,q - 1} \right)} {\;j!\;\left\{ \begin{gathered}
q - 1 \\
j \\
\end{gathered} \right\}\left( \begin{gathered}
n + 1 \\
j + 1 \\
\end{gathered} \right)} = \hfill \\
= \frac{1}
{q}\sum\limits_{0\, \leqslant \,j\, \leqslant \,q - 1} {\left( \begin{gathered}
q \\
j \\
\end{gathered} \right)\;B_j \;\left( {n + 1} \right)^{\,q - j} } \quad \left| {\;1 \leqslant \text{integer }q,n} \right. \hfill \\
\end{gathered}
$$
where $ \left\langle {} \right\rangle $ indicate the Eulerian N., $\left\{ {} \right\}$ the Stirling N. 2nd kind, and $B_j$ the Bernoulli N.
Then the number of ways to arrange them as to finally have two groups is
$$
\begin{gathered}
N_{\,2} (n,q) = \sum\limits_{\left\{ \begin{subarray}{l}
1\, \leqslant \,v_{\,2} \, < \,v_{\,1} \, \leqslant \,n \\
m_{\,2} \, + \,m_{\,1} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right.
\end{subarray} \right.} {\left( {n - v_{\,1} + 1} \right)^{\,m_{\,1} - 1} \left( {n - v_{\,2} + 1} \right)^{\,m_{\,2} - 1} } = \hfill \\
= \sum\limits_{\left\{ \begin{subarray}{l}
1\, \leqslant \,k_{\,1} \, < \,k_{\,2} \, \leqslant \,n\, \\
m_{\,2} \, + \,m_{\,1} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right.
\end{subarray} \right.} {k_{\,1} ^{\,m_{\,1} - 1} \;k_{\,2} ^{\,m_{\,2} - 1} } \hfill \\
\end{gathered}
$$
to which corresponds a probability
$$
P_{\,2} (n,q) = \frac{{N_{\,2} (n,q)}}
{{n^{\,q} }} = \frac{1}
{{n^{\,2} }}\sum\limits_{\left\{ \begin{subarray}{l}
1\, \leqslant \,k_{\,1} \, < \,k_{\,2} \, \leqslant \,n\, \\
m_{\,2} \, + \,m_{\,1} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right.
\end{subarray} \right.} {\left( {\frac{{k_{\,1} }}
{n}} \right)^{\,m_{\,1} - 1} \;\left( {\frac{{k_{\,2} }}
{n}} \right)^{\,m_{\,2} - 1} }
$$
and so forth.
I do not know whether the multiple summations can be reduced to a simpler form. (*)
However, if we increase speed granularity (i.e. $n$) till continuum then we can replace the summation over the $k's$ in the expression for the probability into integrals $$ \begin{gathered} P_{\,g} (q) = \sum\limits_{\begin{subarray}{l} \\ \\ \,m_{\,1} \, + \,m_{\,2} + \, \cdots \, + m_{\,g} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right. \end{subarray} } {\mathop {\int {} }\limits_{\begin{subarray}{l} \\ 0\, \leqslant \,x_{\,1} \, < \,x_{\,2} < \, \cdots \, < \,x_{\,g} \, \leqslant \,1 \end{subarray} } \prod\limits_{1\, \leqslant \,j\, \leqslant \,g\,} {x_{\,j} ^{\,m_{\,j} - 1} \;dx_{\,j} } } = \hfill \\ = \sum\limits_{\begin{subarray}{l} \\ \,m_{\,1} \, + \,m_{\,2} + \, \cdots \, + m_{\,g} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right. \end{subarray} } {\frac{1} {{m_{\,1} }}\;\mathop {\int {} }\limits_{0\, \leqslant \,\,x_{\,2} < \, \cdots \, < \,x_{\,g} \, \leqslant \,1} x_{\,2} ^{\,m_{\,1} + m_{\,2} - 1} \;dx_{\,2} \prod\limits_{3\, \leqslant \,j\, \leqslant \,l\,} {x_{\,j} ^{\,m_{\,j} - 1} \;dx_{\,j} } } = \hfill \\ = \sum\limits_{\begin{subarray}{l} \\ \,m_{\,1} \, + \,m_{\,2} + \, \cdots \, + m_{\,g} \, = \,q\;\;\left| {\;1\, \leqslant \,m_{\,k} \,} \right. \end{subarray} } {\frac{1} {{m_{\,1} }}\frac{1} {{m_{\,1} + m_{\,2} }}\, \cdots \,\frac{1} {{m_{\,1} + m_{\,2} + \, \cdots \, + m_{\,g} }}} \hfill \\ \end{gathered} $$ We can see that $P$ satisfies the following recursion $$ \bbox[lightyellow] { P_{\,g} (q) = \frac{1} {q}\;\sum\limits_{\left( {0\, \leqslant \,g - 1 \leqslant } \right)\,k\, \leqslant \,q - 1} {P_{\,g - 1} (k)} }$$
and for the initial conditions we can put that $0$ sheeps can only be arranged into a empty group and v.v. that an empty group can gather only $0$ sheeps. $$ \left\{ \begin{gathered} P_{\,g} (q) = 0\quad \left| {\;g < 0\; \vee \;p < 0} \right. \hfill \\ P_{\,g} (0) = \delta _{\,g,\,0} \hfill \\ P_{\,0} (q) = \delta _{\,q,\,0} \hfill \\ \end{gathered} \right. $$ Now, starting from a known identity about Stirling N. of the 1st kind, we have $$ \begin{gathered} \left[ \begin{gathered} n + 1 \\ m + 1 \\ \end{gathered} \right] = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left[ \begin{gathered} k \\ m \\ \end{gathered} \right]n^{\,\underline {\,n - k\,} } } = n!\sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left[ \begin{gathered} k \\ m \\ \end{gathered} \right]\frac{1} {{k!}}} \quad \Rightarrow \hfill \\ \Rightarrow \quad \left[ \begin{gathered} n \\ m \\ \end{gathered} \right] = \left( {n - 1} \right)!\sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\left[ \begin{gathered} k \\ m - 1 \\ \end{gathered} \right]\frac{1} {{k!}}} \quad \left| {\;1 \leqslant n,m} \right.\quad \Rightarrow \hfill \\ \Rightarrow \quad \left( {\frac{1} {{n!}}\left[ \begin{gathered} n \\ m \\ \end{gathered} \right]} \right) = \frac{1} {n}\;\sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\left( {\frac{1} {{k!}}\left[ \begin{gathered} k \\ m - 1 \\ \end{gathered} \right]} \right)} \hfill \\ \end{gathered} $$
Finally, having the same recursion and same initial conditions, we reach to: $$ \bbox[lightyellow] { P_{\,g} (q) = \frac{1} {{q!}}\left[ \begin{gathered} q \\ g \\ \end{gathered} \right] }$$ and then it is known (**) that $$ \bbox[lightyellow] { \overline g (q) = \sum\limits_{\left( {0\, \leqslant } \right)\,g\,\left( { \leqslant \,q} \right)} {\frac{g} {{q!}}\left[ \begin{gathered} q \\ g \\ \end{gathered} \right]} = H(q) }$$
-----------
Note (*)
I have later found a closed form for $N_{g}(n,q)$, which is presented in this related post.
----------
Note (**)
because we have in fact
$$
\begin{gathered}
\frac{{\left( {x + 1} \right)^{\,\overline {\,n\,} } }}
{{n!}} = \prod\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\frac{{x + 1 + k}}
{{1 + k}}} = \exp \left( {\sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\ln \left( {1 + \frac{x}
{{1 + k}}} \right)} } \right) = \sum\limits_{\left( {0\, \leqslant } \right)\,k} {\frac{1}
{{n!}}\left[ \begin{gathered}
n \\
k \\
\end{gathered} \right]\left( {x + 1} \right)^{\,k} } \hfill \\
\left( {x + 1} \right)\frac{d}
{{d\,x}}\frac{{\left( {x + 1} \right)^{\,\overline {\,n\,} } }}
{{n!}} = \exp \left( {\sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\ln } \left( {1 + \frac{x}
{{k + 1}}} \right)} \right)\sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\frac{{x + 1}}
{{x + k + 1}}} = \sum\limits_{\left( {0\, \leqslant } \right)\,k} {\frac{k}
{{n!}}\left[ \begin{gathered}
n \\
k \\
\end{gathered} \right]\left( {x + 1} \right)^{\,k} } \hfill \\
\left. {\left( {\left( {x + 1} \right)\frac{d}
{{d\,x}}\frac{{\left( {x + 1} \right)^{\,\overline {\,n\,} } }}
{{n!}} = \left( {x + 1} \right)\frac{d}
{{d\,x}}\frac{{\Gamma \left( {x + 1 + n} \right)}}
{{\Gamma \left( {x + 1} \right)\Gamma \left( {1 + n} \right)}}} \right)\;} \right|_{\;x\, = \,0} = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\frac{1}
{{k + 1}}} = \sum\limits_{\left( {0\, \leqslant } \right)\,k} {\frac{k}
{{n!}}\left[ \begin{gathered}
n \\
k \\
\end{gathered} \right]} \hfill \\
\end{gathered}
$$
Two parts:
-
- A visualization (see below) of the flock's evolution, on a time-position graphics displaying the aggregation process.
In this case, we are with 4 groups.
Moreover, this representation has been obtained by a simple programming "trick" that can interest some people (Matlab program below) who would like to adapt it for other purposes.
Matlab program
clear all;close all;hold on;box on; n=30;s=rand(1,n); a=100;b=60;axis([0,a,0,b]); fill([0,a,a,0],[b,b,0,0],'c'); for k=1:n fill([0,a,a,0],[b,b,k+a*s(k),k],'c'); end;
Comment: This program displays trapezoidal shapes by a kind of stacking, each newly "stacked" shape yielding a possible partial occluding of previously displayed shapes.
-
- A simple proof of the result given by Henry.
Let $G_k$ be the Random Variable equal to the number of groups for a flock of $k$ sheep.
Considering that a $n$th sheep is aggregated to a flock with $n−1$ sheep, we have
$$ \begin{cases}\text{either}&G_n=G_{n−1}+0 \ \\ \text{or}&G_n=G_{n−1}+1 \end{cases}$$
The latter occurs in the exceptional case where the speed of the newly added animal is smaller than all other speeds (this can clearly happen with probability $\tfrac{1}{n}$). Thus, the natural model in terms of random variables is:
$$\tag{1}G_n=G_{n−1}+B$$
where $B$ is a Bernoulli RV with parameter $\tfrac{1}{n}$.
Taking expectation on both sides of (1),
$$E(G_n)=E(G_{n-1})+\tfrac{1}{n}.$$
Using the fact that $G_1=1 \implies E(G_1)=1$ (a single sheep constitutes a group in itself), we finally deduce, by an immediate recurrence, that: $$E(G_n)=1+\tfrac{1}{2}+\tfrac{1}{3}+\cdots+\tfrac{1}{n}=H_n=\ln(n)+\gamma,$$
where $H_n$ the $n$th harmonic number and $\gamma \approx 0.577...$ is the Euler-Mascheroni constant.