Stochastic Supertasks | Infinite Series

Supertasks allow you to accomplish an infinite number of tasks in a finite amount of time. Find out how these paradoxical feats get even stranger once randomness is introduced.

Tweet at us! @pbsinfinite
Email us! pbsinfiniteseries [at] gmail [dot] com

Previous Episode
The Honeybcomcs of 4-Dimensional Bees

Vsauce - Supertasks

Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Assistant Editing and Sound Design by Mike Petrow

Resources:
Special Thanks to John Pike

What happens when you try to empty an urn full of infinite balls? It turns out that whether the vase is empty or full at the end of an infinite amount of time depends on what order you try to empty it in. Check out what happens when randomness and the Ross-Littlewood Paradox collide.

Comments answered by Kelsey:

Lowtech

Daniel Shapiro

Professor Politics

Alex 24757

[TheVeryHungrySingularity]

Why not use half the video to talk about the first scenario, a quarter to talk about a second, and so on until you cover them all?

[TankleKlaus]

3:57 Am I being dumb right now!? There are only 28 ball in the urn --- should it not be (1/28) chance?!?

[AgglomeratiProduzioni]

3:14 "There's a literally infinite number of variations of this problem, so we don't have time to reveal them all."
*UNLESS* you explain each one in half the time you used for the previous one!

[kyzer]

"What happens when you add randomness to a supertask"
Me: Uh-oh...

[keithrobben]

Why is nobody talking about Matt showing up!!????!

[florencebacus]

Challenge problem: There are infinitely many balls left in the urn at noon. In particular, all balls except the multiples of 5 are left.

In fact, on the nth step, ball 5n is removed. This is equivalent to saying that on the nth step, the following balls are in the urn: all balls from 1 to 9n, excluding all multiples of 5 up to 5n. This claim can be proven using induction.

The claim holds for n=1, since balls 1 through 9 (=9n) are put in, and 5 (the median) is taken out.

Now suppose the claim holds for some n; then after the nth step, we are left with balls 1 through 9n, excluding 5, 10, 15, ..., 5n. Now let's see what happens on the (n+1)th step. Balls 9n+1, 9n+2, ..., 9n+9 are added. Now, in order for the claim to hold, we want to show that 5n+5 is the median of the balls currently in the urn. There are 8n+9 balls in the urn total (9n+9, minus the n which have been removed). Further, there are 4n+4 balls whose numbers are less than 5n+5 (because 4n+4 is 5n+4, minus the n balls which have been removed, each of which had numbers less than 5n+5). Consequently, there are (8n+9)-(4n+4)-1 = 4n+4 balls in the urn whose numbers are greater than 5n+5. Therefore, ball 5n+5=5(n+1) is in the middle, so it gets removed, thus proving the claim for (n+1).

Okay, so every multiple of 5 gets removed, and every ball that gets removed is a multiple of 5, leaving infinitely many balls in the urn.

[cmilkau]

I think "adding infinitely many zeroes" is worth slightly more consideration. First, it is very important that we add *countably* many zeroes when we want to conclude a sum. Second, there are two simultaneous limits involved: the limit over the number of steps and the limit over the highest ball number included in the disjunction. Just taking one limit then the other doesn't necessarily mean you get the correct answer, there are cases when you can get any answer you want just by manipulating how fast you let each limit approach infinity with respect to the other.

[october]

I did an Actuarial Science degree and I fucking loved the Stochastic Processes module.

[vriskanon]

Am I missing something, or is the idea of a time restriction arbitrary here? Saying "At noon" seems to be a roundabout way of letting N tend to infinity, and would have the same result

[eyaabid]

I am currently studying mathematics, and I am literally in love with it.
I was just so confused about continuing to do that and make math my entire career and switching to medical school, but when I see how beautiful is this universal language I push myself more to continue this path since I began it already. You guys have played a huge role in doing that, so please continue the amazing work and make sure that you are a very successful, professional and unique channel. 💓💓

[ralphinoful]

I didn't prove it, I just wrote down a few scratches on a piece of paper, but it seems like only multiples of 5 will get removed from removing the median. So infinite.

[AlejandroBravo]

6:39 0+0+0+0+0+... infinite times isn't the same as 0 x infinity which is an indetermination?

[Tehom]

5:29 The terms of that series do not resemble 9^n/(9^n+1).
The formula would give the second term as 81/82, which is different than 18/19, and so forth.
(Edit: Never mind; other poster points out that probably 9*n/(9*n+1) was what was meant) I assume some of the reasoning was not shown; most likely the series are related by an inequality and 9^n/(9^n+1) is an upper bound on the value that the nth term can take, so the smaller terms in the true series only make the probability of the ball remaining smaller.

[disorganizedorg]

On the Nth step you add ten balls and then remove one. There are a minimum of nine left after any given turn.

[whatthefua]

6.46 You cannot conclude that adding infinitely many zeroes sum up to zero. And especially, in this case it doesn't.

[franzschubert]

Today I learned that 9^2= 18 and 9^3=28! Cool :)

[metalbraine]

For median problem, infinitely many will be left. Only the ones divisible by 5 will be removed

[PlayTheMind]

Mankind's Supertask:
Avoid extinction before 2020

[rossjennings]

Major twist: In the deterministic version of the paradox, it doesn't matter how quickly you add the balls -- you can go 10 at a time, as described in the video, or double the number you're putting in at every step. It won't change the fact that every ball is eventually removed. In the stochastic version, though, it could. Yes, the infinite product giving (say) the probability that ball 1 is still in the urn at noon converges to zero -- its logarithm is an infinite sum that grows at least as fast as (some scaled version of) the harmonic series. But this fact depends on the fact that the number of balls is the same at every step. If the number of balls added at a given step grows over time, the product could converge to a non-zero probability!

[owenindri]

As n approaches infinity,

9(1)/[9(1)+1] x 9(2)/[9(2)+1] x ... x 9(n)/[9(n)+1]

approaches 0. It does not equal zero. However I can get behind the concept of calculus and say ball 1 has zero chance of remaining after infinite steps.

This equation doesn’t apply for every ball however. If we look at the balls as groups of ten this equation only applies to the first group (balls 1-10). For group 2 (balls 11-20) they are not subject to the first step and are guaranteed to be there for the second step where the balls from group 1 only have a 90% chance of being there for step 2. Group 2’s equation should look like

9(1)/[9(1)+1] x 9(2)/[9(2)+1] x ... x 9(n)/[9(n)+1] x [9(1)+1]/9(1)

And group X’s equation should look like

9(1)/[9(1)+1] x 9(2)/[9(2)+1] x ... x 9(n)/[9(n)+1] x [9(1)+1]/9(1) x [9(2)+1]/9(2) x ... x [9(x-1)+1]/9(x-1)

It’s easy to see that there are terms that cancel out, and the equation can be simplified to,

9(x)/[9(x)+1] x 9(x+1)/[9(x+1)+1] x ... 9(n)/[9(n)+1]

as long as X is a finite value there will remain an infinite amount of terms that don’t cancel out and there fore there is still a zero percent chance of any ball in group X remaining after infinite steps.

However, as the amount of steps increase so do the amount of groups. In fact since they increase at a 1-1 rate we can say for any step n there is a group n. And it’s equation can be written as,

9(1)/[9(1)+1] x 9(2)/[9(2)+1] x ... x 9(n)/[9(n)+1] x [9(1)+1]/9(1) x [9(2)+1]/9(2) x ... x [9(n-1)]/9(n-1)

Cancel all terms and you are left with,

9(n)/[9(n)+1]

As n approaches infinity this equation approaches 1. That is to say the odds of any given ball in group n remaining after step n is 100% after infinite steps.

Similarly for any group (n-x) the equation gets reduced down to,

9(n-x)/[9(n-x)+1] x 9(n-x+1)/[9(n-x+1)+1] x ... x 9(n-x+x)/[9(n-x+x)+1

And as n approaches infinity, for every finite x, this equation approaches 1. So there are an infinite amount of groups that each have 10 ball all with a 100% probability of remaining after an infinite amount of steps.