Wikipedia:Reference desk/Archives/Mathematics/2014 January 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 18

Expected proportion of completed files?

While waiting around for files in some large torrents to complete, I observed that, without specific files being assigned higher priority, the percentage of files complete is usually much lower than the percentage of the torrent complete, for obvious reasons (for example, if you have 30% of the entire torrent complete, it's likely that you have less than 5% of the files complete, because that 30%-completed is spread out between files, so that you have a little bit of many mostly incomplete files, and a very small number of fully-completed files where the pieces just happened to line up). I began to wonder exactly how many files you should expect to be complete, which got me to the following generalized question:

Suppose a torrent consists of n equally-sized files, each consisting of exactly p identically-sized pieces (with no pieces being shared between files), and pieces are downloaded at random and with equal priority. (So the total torrent will consist of np pieces.) If x is the fraction/percentage of the torrent that is complete (that is, the number of complete pieces divided by the total number of pieces), then what fraction/percentage of the files should we expect to be complete?

(Obviously, the above makes a few simplifying assumptions, as, in real life: not all files of a torrent will be equally-sized; users can configure clients to prioritize some pieces higher than others; pieces are downloaded based upon availability, which is not fully random; and pieces at the front- or tail-end of files will usually be shared between the files, containing bytes from both files.)

Anybody know how to solve the above problem? Do we have an article on this generalized problem, since I could see it applying to other situations besides torrents? (A similar problem: suppose a bucket is filled with 100 balls of 10 different colors, so that there is one ball of each color; after picking x balls without replacement, what is the expected number of colors for which you have every ball of that color?) Thanks.

—SeekingAnswers (reply) 01:48, 18 January 2014 (UTC)

You could get a fair approximation by computing the probability of each file being completed as if it was independent of the rest. So, say a given file has 10 chunks, and each chunk has a 60% chance of being completed. The chance of all 10 being completed is then P_{FILE 1 COMPLETED} = 0.6¹⁰. You would calculate all of the P values this way, then combine them to get the total probability (you know how to do this ?). This would be quite straightforward, but you'd want to use a program to calculate it quickly.

Of course, the files are not really independent of each other, since, if more chunks of one file are completed, this would mean fewer chunks are available to spread among the other files. So, to do it properly, you'd have to look at every possible distribution of completed chunks, calculate how many files are completed that way, then combine those together. Of course, this approach would quickly become impractical, even using a computer to do the math.

Another thought, can it download two chunks on the same file at once ? If not, then this complicates things a bit further, as the completion of each chunk is now dependent on the completion of the other chunks in the same file. StuRat (talk) 02:04, 18 January 2014 (UTC)

Suppose that X_i is the random variable that is equal to 0 if piece i (of np, numbered from 1) is incomplete and 1 if piece i is complete. Fix c, the fraction of pieces complete; then X_i is 0 with probability 1 − c and 1 with probability c. Define Y_j to be the random variable that is equal to 0 if file j (of n) is incomplete and 1 if file j is complete. Since the X_i are independent random variables, Y_j is 1 with probability c^p and 0 otherwise, so its expected value is c^p. Since the Y_j are independent random variables, the expected number of complete files is nc^p. Ozob (talk) 01:14, 20 January 2014 (UTC)

As StuRat explained, given that the fraction complete is c, the X_i are not independent - if one piece is known to be completed, it reduces the chance of all other pieces being completed.

E.g., if there are 2 files with 2 pieces each, and you know that 50% of the pieces have been completed, then the average number of completed files is 1/3, not 1/2.

However, it should be a good enough approximation. -- Meni Rosenfeld (talk) 14:06, 20 January 2014 (UTC)

Add up positive numbers to get negative number

Can someone say something about this.. http://www.slate.com/blogs/bad_astronomy/2014/01/17/infinite_series_when_the_sum_of_all_positive_integers_is_a_small_negative.html [1] How can adding up infinite number of positive numbers get you a negative number? 220.239.51.150 (talk) 03:40, 18 January 2014 (UTC)

The series is actually divergent and doesn't have a sum at all in the usual sense. When you apply formulas to a divergent series, even formulas that work perfectly well for a convergent series, weird things can happen. Looie496 (talk) 04:20, 18 January 2014 (UTC)

The appropriate article would seem to be Cesàro summation Rojomoke (talk) 04:55, 18 January 2014 (UTC)

Actually, we have an article on this very series: 1 + 2 + 3 + 4 + ⋯ --Mark viking (talk) 05:38, 18 January 2014 (UTC)

The article in the url link specifically says that

$\sum _{n=1}^{\infty }n=-{\frac {1}{12}}$

220.239.51.150 (talk) 12:28, 18 January 2014 (UTC)

The linked article (Ramanujan summation) gives that value for the Ramanujan sum, but it also says: "Ramanujan summation essentially is a property of the partial sums, rather than a property of the entire sum, as that doesn't exist", and Ramanujan himself also wrote: "If I tell you this you will at once point out to me the lunatic asylum as my goal". Sometimes, though, counter-intuitive working can give useful real results. Dbfirs 14:31, 18 January 2014 (UTC)

Even for partial summation, there is no way you can add up a finite number of positive numbers to get a single negative number. Ohanian (talk) 07:05, 19 January 2014 (UTC)

This is clearly false, here is the proof. You will pay me one dollar on the first day, two dollars on the second day, three dollars on the third day and so on and so forth for ALL ETERNITY. But in reality, you don't owe me anything, instead I owe you eight cents and one third of a cent !!! Does that make any sense to you??? Ohanian (talk) 07:15, 19 January 2014 (UTC)

The flaw in that argument is that you haven't gone all the way to "all eternity" - because you can't. You've stopped at some undefined point well before then. The trick depends on actually going ALL the way. Get back to us when you get there.  :) -- Jack of Oz ^{[pleasantries]} 07:58, 19 January 2014 (UTC)

Well, there are lots of operations you can do on a completed infinite collection. This particular one, though, I don't think really makes all that much sense except in very specific contexts. The sum in the sense of measure theory, for example, would be ∞, and that's what I would generally consider the default answer unless there is some contextual information that makes the Ramanujan sum seem appropriate. --Trovatore (talk) 08:19, 19 January 2014 (UTC)

I thought this "sum" was obtained somehow using analytic continuation. I'm pretty sure, as well, that it appears in a fundamental rôle in String Theory by Barton Zweibach. Don't have it available a t m. YohanN7 (talk) 08:39, 19 January 2014 (UTC)

Indeed, using the analytic continuation of the Riemann zeta function (in particular the functional equation) you can conclude $\zeta (-1)=-{\frac {1}{12}}$. Since the zeta function is defined as $\zeta (s)=\sum _{n=1}^{\infty }n^{-s}$ for $|s|>1$, you can (somewhat dubiously) declare

$\sum _{n=1}^{\infty }n=\zeta (-1)=-{\frac {1}{12}}$

Gutworth (talk) 20:04, 19 January 2014 (UTC)

See also 1+2+4+8. Bo Jacoby (talk) 20:59, 20 January 2014 (UTC).

I think the previous remarks handle this pretty well, but I'll add that this basically comes down to abuse of notation. The popular press somehow got a hold of this (old) notion recently, and most of the press gets it at least partially wrong or sloppy. To be fair to the press, getting it right in detail requires the equivalent of a math degree :) Suffice it to say, the infinite sum has no limit, even under the common rules which do allow for infinite sums to converge to finite sums. The sum can behave as claimed--but only under a rather esoteric and looses sense of what it means to write that equals sign.

I'd be happier if 1/2 + 1/4 + 1/8 + 1/16 + ⋯=1 were being passed around as a "cool math fact" -- it's a concept many people haven't heard of, and it can be explained pretty clearly in a short piece! SemanticMantis (talk) 00:27, 21 January 2014 (UTC)

Ramanujan summation: Independent of f, or not?

So our article on Ramanujan summation, which is apparently what's used to assign a value to 1+2+3+..., strikes me as not the clearest math article I've ever seen on Wikipedia, but the idea filters through to me that one takes certain formulas for sums of the form Σf(n), where I'm being deliberately vague about the limits of summation, and then applies them outside the region where they can be proved to be correct in the sense of the ordinary absolutely convergent infinite sum, and then one declares that to be the answer. Yes?

If I've followed it that far, then to me, the obvious question is, do I get the same answer if I use a different function g, but one that agrees with f on the values that I'm summing? Maybe, if some regularity condition is imposed on g, say that it be an entire function or something? If so, then I can agree that this procedure is genuinely isolating a property of the sum itself. But if not, then it seems to be a property of a particular representation of the sum, and therefore not properly a sum of 1+2+3+... at all. Does anyone know? --Trovatore (talk) 00:42, 21 January 2014 (UTC)

I don't know, but this quote from the article hints that you might be right on the claim that "classical" R_sum might be ill-defined/multi-valued in some cases:

"More recently, the use of C(1) has been proposed as Ramanujan's summation, since then it can be assured that one series \scriptstyle \sum_{k=1}^{\infty}f(k) admits one and only one Ramanujan's summation"

The phrasing certainly implies to me that either the C(0) approach may fail to define an R_sum of certain series, or that the R_sum may not be unique. SemanticMantis (talk) 15:35, 21 January 2014 (UTC)