13
$\begingroup$

When downloading large files, they are split up into many small parts, which are downloaded in random order. I was downloading a torrent file, which made me think of the following problem.

If I have downloaded $x$ of the $n$ pieces, what is the expected average length of a continuous stretch of downloaded parts? For example, if there were $100$ pieces, then each one could be downloaded or not. Some of the downloaded parts would be next to each other. These would form a chain. If I were to average the lengths of all the chains, what should I expect the answer to be?

$\endgroup$
  • $\begingroup$ A Monte-Carlo simulation might help get an idea of what this looks like for small $n$. There might be a pattern that helps derive the full result. I feel the definition is still slightly ambiguous. For $l(n,x)$ we clearly have $l(n,0)=0, l(n,n)=n$. Would you then define $l(n,1)=1$ as we are averaging over all of the 1 chains in every possible outcome? Then $l(3,2)$ is either $(2+1+2+2+1+2)/6 = 5/3$, which is averaged over outcomes, or $(2+1+1+2+2+1+1+2)/8=3/2$ over chains and outcomes. Could you provide a couple of examples for small $n$, to see exactly the problem you want to solve? $\endgroup$ – Benedict W. J. Irwin Jun 5 '18 at 8:23
  • $\begingroup$ The sum of the lengths of all chains, divided by the number of chains. $\endgroup$ – William Grannis Jun 5 '18 at 10:49
  • $\begingroup$ So you want expected average length. Put another way, given a scenario for which pieces are downloaded, we compute the average length of chains. Then, we take the mean of those averages across all scenarios. $l(3,2)$ would be $((1 + 1)/2 + 2/1 + 2/1)/3 = 5/3$. Is this what you mean? $\endgroup$ – Larry B. Jun 5 '18 at 19:12
  • $\begingroup$ Yes. That is precisely what I mean $\endgroup$ – William Grannis Jun 5 '18 at 19:13
  • 1
    $\begingroup$ @Larry B. Thank you for the bounty! I really tried my best. $\endgroup$ – John McClane Jun 12 '18 at 2:55
4
+100
$\begingroup$

Here is an exact calculation of the expected value. The word element below refers to a minimal piece of a file (chunk) determined by the torrent being downloaded. Thus, all streaks as well as expected values of their average are measured in chunks, not in bytes.

The key point here is determining the number of ways one can choose $m$ elements among a sequence of given $n$ elements such that the selection constitute exactly $k > 0$ streaks (stretches, chains, etc.) Denote this number by $T(n, m, k)$. For the binomial coefficients, the convention $(b<0 \lor b>a) \Rightarrow {a \choose b}=0$ is used below.

Theorem. $$T(n, m, k) = {n-m+1 \choose k} {m-1 \choose k-1}.$$

Proof. Take any combination being counted in $T(n, m, k)$. There may be exactly $\hat x_0 \ge 0$ non-chosen elements before the first streak, $x_i \ge 1$ non-chosen elements between the $i$th and the $(i+1)$th streaks for any $i=1,2,\dots,k-1$, and $\hat x_k \ge 0$ non-chosen elements after the last streak. The total number of non-chosen elements must be $n-m$. Bringing $x$'s to a uniform sequence, denote $x_0 = \hat x_0 + 1,$ $x_k = \hat x_k + 1$, after which their sum increases by $2$.

Also, there may be $y_i \ge 1$ chosen elements in $i$th streak for any $i=1,2,\dots,k$. Their total number must be $m$.

We have just built a one-to-one correspondence between the combinations we're counting and positive integer solutions of the system $$\begin{align} x_0 + x_1 + \dots + x_k &= n-m+2 \\ y_1 + \dots + y_k &= m. \end{align}$$ Note that equations in this system are independent of each other, so the total number of its solutions is the product of numbers of solutions of the two equations. Solving each equation separately is nothing else than counting compositions, hence the result. $\blacksquare$

Going back to the question, we need to calculate the expected value of the random variable $X = \frac m k$ for a given parameters $n, m$ (I will use $m$ instead of $x$ in the original question here), $1 \le m \le n$. As all of ${n \choose m}$ combinations are equiprobable, $$\mathbb E[X] = \frac {\displaystyle \sum_{k=1}^m {\textstyle \frac m k \, T(n,m,k)}} {{n \choose m}} = \frac {\displaystyle \sum_{k=1}^m {\textstyle \frac m k \, {n-m+1 \choose k} {m-1 \choose k-1}}} {{n \choose m}}.$$ By the way, the above denominator is nothing else than $\sum_{k=1}^m {T(n,m,k)}$. To calculate the numerator, first note that $\frac m k \, {m-1 \choose k-1} = {m \choose k} = {m \choose m-k}$, then use Vandermonde's identity: $$\displaystyle \sum_{k=1}^m {\textstyle \frac m k \, {n-m+1 \choose k} {m-1 \choose k-1}} = \sum_{k=1}^m {\textstyle {n-m+1 \choose k} {m \choose m-k}} = \sum_{k=0}^m {\textstyle {n-m+1 \choose k} {m \choose m-k}} - 1 = \textstyle {n+1 \choose m} - 1.$$ Hence,

$$\mathbb E[X] = \frac {{n+1 \choose m} - 1} {{n \choose m}} = \frac {n+1} {n-m+1} - \frac 1 {{n \choose m}}.$$

The last term quickly approaches $0$ when $n$ is large and $m$ moves away from $1$ and $n$.


I have also considered a supplementary question: calculation of $\mathbb E[X]$ in case when only $n$ is known. Instead of $m$, probability $p$ of downloading any particular piece (chunk) is given. Thus, $m$ is random (as well as $k$) now and has the binomial distribution $B(n, p)$. The only drawback is the possibility of $k=0$ (or $m=0$ which is the same) now, but this can be eliminated by calculating $\mathbb E\left[\frac m k \mid m>0\right]$ (i.e. we know for sure that something was already downloaded, but don't know how much). To such a problem statement the answer is

$$\mathbb E[X \mid m>0] = \frac {\displaystyle \sum_{m=1}^n {p^m q^{n-m} \sum_{k=1}^m {\tfrac m k \, T(n,m,k)}}} {1-q^n} = \frac {1 - \displaystyle \frac {q^{n+2}-p^{n+2}}{q-p}}{q(1-q^n)},$$

where $q = 1-p$, and the fraction $\frac {q^{n+2}-p^{n+2}}{q-p}$ should be changed to $\frac {n+2}{2^{n+1}}$ when $p=q=\frac 1 2$.

$\endgroup$
0
$\begingroup$

An easy way to reason about this, albeit with some imprecision, is to think about "distance between pieces" when you have less than half the torrent, and "distance between holes" when you have more. So, if you have $x<n$ pieces, there are likely to be large stretches of emptyness between a piece and the next, and your average chain length is going to be less than $2$ (and converging to $1$ if $x<<n$). If instead you have $x>n$ pieces, then there are likely streches of pieces between isolated holes. How long are these stretches? Well, if you have $1$ "hole" every $m$ pieces, your "chain length" is likely to be $\approx m$.

So, In general, if you miss $y=n-x$ pieces, your chain length is going to be about $n/y=n/(n-x)=1/(1-x/n)$. This is a good approximation even if you have few pieces! In this sense, note that for $x<n/2$, we have $1/(1-x/n)<2$, and for $x<<n$, we have $1/(1-x/n)\approx 1$.

To make this more precise, you have to be a bit more precise about what you mean with "average chain length". A piece followed by a hole is definitely a chain of length $1$. But a hole followed by a hole ... is it a chain of length $0$? Probably it's not, but it's not unconceivable to define a chain from a given point as the longest uninterrupted streak of pieces from that point - such a streak can have length $0$. These details affect the analysis and the answer.

$\endgroup$
  • $\begingroup$ Only downloaded pieces count as chains. $\endgroup$ – William Grannis Jun 5 '18 at 10:52

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.