Hey all, I just noticed I made a slight mistake at 6:10: In the part of the animation where we have b1/2 + b2/4 + 1/2f(0.b3b4...), it should really say b1/2 + b2/4 + 1/4f(0.b3b4...), and in general, the denominator of the fraction in front of f should multiply by 2 at every iteration. The end result shown on the screen is still correct, but the intermediate steps are a bit off because of that. Also, some of you have pointed out that at 9:29, since the sets are infinite, it is not technically correct notation to write that the cardinality of the one on top is greater than the cardinality of the one on the bottom. Instead it should say that the set on the bottom is a subset of the set on the top, which still has the same implications in terms of probabilities.
That made me think: what if we allow more integers? Or what about complex numbers? An octahedron dice (4 sides)? Even more dimensions? Thats so amazing dude!
It's very easy to fall into the trap of assuming f(x) = x at 6:24 and call the problem solved. While the answer is still correct, the fact that this simple function becomes a complex fractal for any P≠0.5 is a good reminder that the kind of rigorous analysis you did at the end was indeed necessary for the proof.
At 9:24, instead of saying that one set is “larger” than the other, which might be a bit confusing given that both sets are countably infinite, you could simply show that the lower set of sequences is a subset of the upper set. It follows immediately from the axioms of probability that P(x_2 -> 1) >= P(x_1 -> 1) and therefore f(x_2) >= f(x_1).
For the fractals produced by the biased coin, I think the easiest explaination is to look specifically at what happens at x=~1/2. Let's consider a coin with a low probability of going towards 1. For values of x slightly above 1/2, if you flip going towards 1, you'll go straight to 1, but if you flip going towards 0, you'll need to flip towards 1 several times in a row just to get back to the middle. So f(1/2+k)=p(coin flips 1)+negligible for k
Yeah, this is essentially the thought process I went through too! I just noticed @mrpojsomnoj3313 was thinking about what happens when we do this experiment inside a triangle instead of a line segment. I wonder what kinds of shapes you get for a probability distribution in that case -- or for that matter, any other shapes! Maybe I'll get around sometime to visualizing this.
@@PurpleMindCS They are the modulos in relation of the size of the circle and how much that bias would 'typically' shortcut (or not) when it affects the outcome. For a very small circle, the bias is seen over a number of many flips (smooth), but at r=1/2 there is likely to be just one flip proportional to the bias since its already touching both edges. Now imagine a circle with r=1/8, so 4 circles width to width - that could be the "least turns to travel the longest path." If we add a 5th circle of the same r, it would sit beyond the ends. Thats excess until r shrinks down to 1/10, is wasted "shortcutting" and the pattern is "excess" circle which in relation to the bias, producing different mods across all r since the flips are whole integers but the r was continuous.
@@PurpleMindCS I feel like if we want to do this we would end up using Complex Numbers and Nth Roots of 1 in some capacity, which is nice because it feels like that could generalize back to the 2 point case (2nd roots of 1 being 1 and -1 and confining the steps to the real line.) Since the system is symmetrical, we only need the expression for "probability that a point z eventually goes to 1" P(z->1). For N = 1/2, P(z->1) = 1/2 + z/2; which works because the result is confined to the reals. If we allow the point to begin off the real line, then whether it begins above or below the line does not matter, implying we need something like (z + z')/2 in place of z in the formula, where z' is the complex conjugate. Indeed, in N>2 case, we would not expect whether z is specifically above or below the real line to have any effect on the probability that it goes to 1, specifically. Due to rotational symmetry, we expect that the probability that it goes to the Nth root of 1 to be the P(z->1) function rotated about the origin by 2pi/N. This enforces that, at the origin, the probability of ending up at any endpoint is 1/N, since if we add up all the P(z->e^2pi/k) for k from 0 to N-1, we should get 1; that is, the total probability of getting to any of the endpoints should be 1, and the probability from the center is identical in all rotations. We could probably use similar arguments about the function being increasing along any line between two endpoints to nail down the distribution. The real trick will be proving that starting closer to an endpoint point actually does increase the probability of ending up there, which seems like it ought to be true. We can replace the clumsy complex conjugate stuff above with something involving the Argument of z so we can track which angled slice of the figure we're in. I'm not sure exactly what the form of the solution looks like, explicitly. It probably involves a product over terms related to each endpoint so that the whole product goes to zero when it's close to an endpoint that isn't '1'? Hmm.
@@dumblockdubbed2455 well it's not just the animation! the sound quality, the engaging script, the background music. everything seems so... professional! did not expect to find this hidden gem today.
Extra solution (because lol) Take a look at the expected value of x. It can't change (when the coin is fair). So it has to be the probability x ends as 1.
@@FrostedSnowFlakes- Imagine you started at some x. I now tell you that I made one coin flip, but don't tell you my result. So you know there is a 50% chance for the value to be 0 and 50% to be 2x. The expected value of the value after one coin flip is therefore still x. This logic can be applied symmetrically for the case x > 0.5, and recursively for multiple flips. We assume the process eventually ends (it doesn't have to but every flip has a 50% chance to do so), and find out the expected value is still x. But the value can only be 0 or 1, and there is a bit of extra algebra here, but I'm too lazy to write it here.
My attempt at reasoning about the fractal with the biased coin: At 1/2, the probability of reaching 1 is X, and of reaching 0 is 1-X. For reasons stated in method 1, the entire left half should be a similarly scaled version of the whole object, and so should the right. Applying this recursively should give some nice fractal pattern.
I think the self-similar fractal happens because the problem itself is self-similar. Each flip of the coin, either the game ends, or half of the initial values turns into the full set.
Great video! I found your channel too late to submit anything for this first one, but I did find (without a proof) that f(x) = x. I’m excited to see what I missed in my solution to the dice problem!
This was a fun problem! I missed the original video and found it through this, but I had a blast solving it anyways before watching this one. I hope we get more of these in the future!
A puzzle I’ve tried to solve is the probability that when picking k dominos from a triangular set from double blank to double l, that they form at least one chain that uses every domino picked, Mexican train style. There are countless ways to extend this such as the probability that a certain domino is the beginning of the chain. For k=2, I got (4l-4)/(l^2 +5l +6) and I’ve also figured out k=3, too.
I believe there is this book by Barnsley which treats these kinds of self-referential functions. I would highly recommend any viewer which is curious about these kinds of functions to read “Fractals everywhere”.
I imagine it comes from the the fact our probabilities come from a recursive application of a function on our binary expansion, combined w the inherent fractal nature of digit expansions like that. (Imagine writing binary numbers with an infinite number of leading 0s, and color 1s black, 0s white. You will see a pattern where each time you add a digit, i.e going from 2 digit binary numbers to 3 digit numbers, you take the 2 digit binary numbers, duplicate it, and give the first half a leading 0 and the second half leading 1s. 00 01 10 11 Into 000 001 010 011 100 101 110 111) If you pay attention to the graph, it appears the duplication points happen on the diatics.
The way I came to method #1: You can look at where the coin ends up if you never take the 50% chance that the point ends up on one of the endpoints. Record down at each step if x < 0.5, or x > 0.5. This process basically encodes the input number as a base 2 decimal! (input to the next step is the fractional part of 2x, output is equal to whether 2x < or > 1) The probability calculation just happens to look exactly like base 2 decoding. (assuming you terminate when x equals exactly 1/2.) The rest is the painful work of formalizing and proving that intuition. whiiich. I didn't really know how to do because I'm a programmer, not a mathematician, lol.
6:23 the question here is whether the function is continuous… if it is, then the diadic rationnals being dense in R, the function *is* f(x) = x. But yeah if you can prove that the f(0.b_k b_k+1 …)/2^k goes to 0 it does seem to work quite well. Edit : I like method 2 better x') - Just seeing this makes me wanna try on the n-simplex : instead of just two points 0 and 1, use n (evenly spaced) vertices and see what happens ! Edit : maybe picking the ending point with a coin flip makes that harder… unless we only deal with the vertices and forget the inside and different faces of the simplex.
There's an easy solution which is being missed here if you know a bit more advanced probability theory. Simply observe that the process of position of the point over time forms a bounded martingale, so the optional stopping theorem applies. Hence the initial position equals the expectation of the ending position, and since the ending position is either 0 or 1, this expectation is the probability of ending at 1. Therefore the probability of ending at 1 is x and we are done. See en.wikipedia.org/wiki/Optional_stopping_theorem
Ok, I gave the problem a try before watching the video and while I haven't really solved it and only came up with a heuristic argument, I'd still like to share my thought process: First we conjecture that f(x) = x based on the highly rigorous reasoning that f(0) = 0, f(1/2) = 1/2 and f(1) = 1; and f(x) is probably continuous. then we know that f(x) = f_1(x) + f_2(x) + f_3(x) + ... Where f_i(x) is the probability that the sequence ends of trials ends on the number 1 after exactly i iterations. (Basically, the probability that the sequence finishes on 1 = the probability that the sequence finishes on 1 after 1 coin flip + the probability that the sequence ends after 2 coin flips and so on). f_1(x) = 0 (0
The expected displacement of the point on each iteration is 0, by construction. (In other words, this is a martingale.) Thus, the expected *total* displacement must also be 0, so the expected endpoint must equal the expected starting point, x. Since the endpoint is always 0 or 1, the only way that this can happen is for P[end at 1] = x.
I'm not well-versed in martingale theory myself, but I get the gist of what you're saying and I think it's really funny that the "expected displacement" is zero even though the only possible outcomes are the opposite extremes.
@@fredfred9847 I agree! It's quite short, which is very elegant. However I also think there are merits to a lot of different methods. While they may all lead to the same answer to the question if done correctly, the different perspectives on the puzzle not only add to our toolbox of problem-solving techniques but also provide insights for the intuition behind various aspects of the solution, in addition to suggesting variants of the question, such as the biased coin variant which produces the fractal pattern.
@@PurpleMindCSyou don't have to call it martingale theory it's just finding an invariant and knowing there's only 2 possible end states. The Wikipedia article on gamblers ruin (specifically Huygens result which generalize to unfair coin flips by finding a different invariant) Now, let's try finding the expected number of steps this would take. We know we start at x and finish at 0 or 1 which means a variance of x(1-x). Each step at x has a variance of x² or (1-x)² if x > 0.5. so the remaining variance is x(1-2x) or (1-x)(2x-1) ok I think the solution here is probably discontinuous so we'd need simulation/harder math, but let's look at smaller cases: for x = 0.5 it's 1 step for x = 0.25 or 0.75 it's 1 or 2 so 1.5 on average for x = odd/8 it's 1 or 1+(1 or 2) so 1.75 on average so it looks like for a non binary number it's probably 2 in the limit. Would be nice to get a satisfactory explanation for why I graphed it and a simple intuitive explanation is that x(1-x) has an average value of 1/6 while the x(1-2x) or (1-x)(2x-1) has an average value of 1/12 so we have half as much variance. Oh lol this is painfully obvious my bad it's just a exponential distribution so obviously 50% of 1 step 25% of 2 steps 12.5% of 3 steps . . . averages to 2
Even if you don't think you could've figured out the solution on your own, I hope you at least enjoyed watching the video and learned something from it anyway! In fact, several submissions I've gotten for this project so far have been from people who didn't fully complete the problem, but rather just had some first observations / general approaches. The process of doing math can be slow, and every bit of progress, no matter how small, can be celebrated!
Can you make math videos that explain media or tv show scenarios. This type of content could better help students learn and see how math is relatable through media we’re familiar with.
Nice problem, havent seen the first video, but i love the combination of math and computer science done here! Would have totaly written a program if i had watched the first video
Another way to view the fractal pattern is to notice what happens to the binary formula. With an arbitrary probability p we get a formula f(0.b₁b₂...) = p b₁ + p f(0.b₂b₃...), so 1/2 replaced with p, but the expansion is still binary. It has the effect of replacing b₁/2 + b₂/4 + ... = ∑bₖ/2⁻ᵏ by b₁p + b₁p² + ... = ∑bₖpᵏ. So the fractal pattern comes from taking the binary expansion of x and then replacing all the powers of 1/2 with powers of p. This is also the reason why it has this jumping behavior near all the dyadic rationals, take 0.1 for example. The number x₁ = 0.0111111111₂ is really close to x₂ = 0.1000000000₂, since they only differ by 0.0000000001₂, however f(x) would replace every 1 with a power of p, not 1/2, and so the powers of p in f(x₁) and f(x₂) don't add up anywhere close. It's also curious that even though the curve is fractal it still seems to be continuous at every point. This can also be proven: if we flip bₖ in x, that will just flip p⁻ᵏ in f(x). That means that for every ε > 0 we can find a bit bₖ such that flipping it (or any bit after that) only changes f(x) by less than ε.
Yeah, that's a good way to put it. Recently I've become curious to see if anyone can find a formula for a "curve of best fit" (however you may define that) through the fractal pattern, since it seems to have some sort of defined shape.
It's funny you thought the curve was continuous at every point - my first thought was the curve was discontinuous at every point. Turns out we're both wrong: In your example, you showed curve is discontinuous at 0.5. It's also discontinuous at every dyadic rational using the same logic. But the discontinuity is only on the left side, the function is right-continuous everywhere.
@@timpressey Do you mean "continuous" or "smooth?" I don't see how the function isn't continuous, as even at the dyadic rationals, an arbitrarily small change in x seems to produce an arbitrarily small change in f(x) in either direction. I think silentob's argument is just that the function is not differentiable at the dyadic rationals.
That's not quite the correct formula, as that assumes a probability of p for going left and a probability of p for going right, which generally does not make sense for any p other than 1/2. The correct formula would be f(0.b₁b₂...) = p b₁ + (1-p)f(0.b₂b₃...) if b₁ = 1 and f(0.b₁b₂...) = (1-p)b₁ + p f(0.b₂b₃...) if b₁ = 0. I don't immediately see a way to simplify this, which makes sense is the result is a function that is continuous everywhere (probabiy, I haven't proved it...), but not differentiable on a dense subset of the domain, and these rarely have nice closed-form descriptions. Note that the function you give is not continuous at the dyadic rationals, and also at x = 1 gives a value of p + p^2 + p^3 + ... = 1/(1/p - 1), which is only equal to 1 at p = 0.5.
@@danielgostein3039 I did mean continuous, and I was talking about the function f(0.b₁b₂...) = ∑bₖpᵏ. Take p = 0.25 for example: at 0.5 we have f(0.1₂) = 1/4, but f(0.0111111...₂) = 1/12 by summing the geometric series. (More precisely, any value x < 0.5 will have f(x) < 1/12). So there is a discontinuity to the left of 0.5. The problem is what @reginaldlybbert7374 points out: the function f(0.b₁b₂...) = ∑bₖp does not describe the function at the end of the video, the formula just happens to work at p = 0.5 because p_left = p_right = 0.5.
Today, I came up with a puzzle: you have a function (c(x) = sin(x)) and a circle r=1. What is the highest y coordinate of the circle where it still touches the curve at each x position? The height is then given by the function h(x). Things I found out: h is oscillating from 1 to 2. Create the function f(x)=c(x)+sqrt(1-(x-x0)^2), x0 being the x-position of the circle, the highest point of f equals h(x)
I missed the first video, but I still want to make a guess before seeing the solution: I say that the probability is x itself. We solve this problem by finding a recursive formula for the probability given x. If x is smaller than 0.5 the circle hits 0 on the left and some other number on the right. As that number has the same distance to x as x has to 0, it must be twice the value of x. So p(x) = 0.5 * 0 + 0.5 * p(2x) [if x < 0.5]. If x is bigger than 0.5 the circle hits 1 on the right and some other number on the left. As that number has the same distance to x as x has to 1, it must be twice the value of x minus 1. So p(x) = 0.5 * 1 + 0.5 * p(2x - 1) [if x > 0.5]. We continue by making two observations: a) when looking at the binary representation of the number x, if the first digit after the dot is 0 the number must be smaller than 0.5 and if it is 1 it must be greater or equal to 0.5 and b) multiplying by two (and subtracting one of number is greater than 0.5) is equivalent to left shifting the number by one (and cutting off any non decimal place). We can rewrite the formula now as follows: p(x) = 0.5 * x_1 + 0.5 * p(x
The appearance of the fractal at the end reminds me of this wonderful functional equation, somewhat similar to the one considered here: f(x) = f(x/2) + f((x+1)/2). This (up to linearity) has only a single continuously differentiable solution, but many continuous solutions, which nevertheless can be completely described, though this is quite tricky. The continuously differentiable solution is 2x-1. The other continuous solutions all look like the Weierstraß function: They are of form W = \sum_k w(2^k x)/2^k, where w is a function satisfying the functional equation w(x+1) = -w(x) (like sin and cos). This can be shown by considering a certain transform of a solution which is the inverse of the mapping w \mapsto W.
The fractal looks like a relative of (if not an instance of) the so-called blancmange curve which, unsurprisingly, is defined in terms of powers of two. Wikipedia currently has an article on it, as does MathWorld.
My solution for this problem: . . . After each coin flip, the expected location of the coin does not change. Since the process almost surely terminates, the final expected location will remain x. This implies that the probability it ends at 1 is x and the prob. it ends at 0 is 1-x.
There's a fun subtlety here. This function you mentioned is actually not a function! It is a family of functions indexed by the limit set of coin flips (isn't that the Cantor Space?). What y'all have done is actually prove that these statements are true for every function in the family!! I love the idea of changing the underlying set by changing the random variables used. I wonder what you can say if you get more general about the behavior of these random variables.
My argument by symmetry was a bit hand-wavy, and not really a full solution: First, we know that the probability this doesn’t end is (1/2)^infinity=0. Now, the probabilities must either be 50-50 or dependent on x: P(x ends 1) + P(x ends 0) = 1 By symmetry: P(x ends 1) = P(1-x ends 0) P(x ends 0) = P(1-x ends 1) Let F(x) = P(x ends 1). Then: F(x) + F(1-x) = 1 For the greatest n such that x is between 1-(1/2)^n and 1, look at a decision tree: x either goes to 1 or leaves the “neighborhood”. This means that there must be less average moves left to end at 1 the closer x is to 1, so F(x) must be increasing. The most intuitive and simple guess here is F(x) = x. This is bolstered by the fact that F(x)+F(1-x)=1 implies F(.5)=.5 and F(1)=1 implies F(0)=0.
My solution before watching the video past the problem description: Say x is a binary number: x=0.1101110... Also, define whose "turn" it is as T=0 or T=1. At the start, set T=0. Now on each step, we can check if x
Before watching video: Notice that from the perspective of the mid point, going to the right is identical probabalistically to going to the left. Therefore: The inverse probability of any statement is true of the opposite side. Next, notice at 1/2 of the line, the odds of going to 1 (which we will now ONLY talk about these odds, as the inverse is the same thing) is a 50/50 AND it must happen on a single coinflip. Next, let's ask about the point 1/2+1/4 This point is at 3/4ths, and initially the circle is 1/4th wide. But if it goes left, we return to the middle point, who is then a 50/50 (and will conclude the experiment) So we do a 50/50, into another 50/50 to NOT go into the 1. Therefore: at 3/4ths, the probability of going to 1 is a 3/4. Repeat ad neasuem. Now the only question that is left is how does this work when you are not perfectly afixed to a point who is in the series 1/2 + 1/4 + 1/8... or 1/2 - 1/4 - 1/8 ...... Let's study the charachter of this movement from .6 .6-> .2->.4->.8->.6 We find a repeating cycle from the initial position, around back eventually to the initial position. The length of time to leave the side you started on is: what bracket of 1/2+1/4+.... you were in when you started. Therefore: We know for a fact that the 1/2+1/4+1/8.... probabilities define "probability buckets" for their neighbors, which I will now arbitrarily declare to be relatively linear, and therefore: The odds to go to one if you are at .6 is .6 and the odds to go to one if you start at .99 is .99, and vice versa. The odds to go to one at .01 is .01. Maybe I was too quick to finish the problem, but I think i'm satified with my solution. After video: My solution is right? Lets go! The final tidbit at the end, if i had to guess, it is following the bucket sizes. Where the largest relative maximum happens exactly at 1/2+1/4+1/8.... and 1/2 - 1/4 - 1/8 - 1/16th.... Why this is? It seems intuitive, and so its kind of hard to explain, but when you are drifting towards one or the other, being on one of these bucket values makes you have less total coin flips before hitting the end. For instance, 1/2 is a 50/50 to hit into 1 IMMIDIATELY, but so is slightly less than 3/4ths. I would guess this is why the graph is no longer linear, and all bumpy. Edit: oh also there is a special charachteristic of points like 1/2+1/8th. if they fail to go to one, its - (1/2 - (1/2 + 1/8th)) for the next point location = 1/8th. But 1/8th is in the series that's perfectly collapsing. So there is another something special about these points, which directly lead into collapsing coinflips (determenisticly ending, cannot endlessly loop)
I dont see anyone solving this problem the way I did so I'll just say it here. I first thought about the only point we know the probability of . For x = 1/2 the probability is one half . Then I realised that for example , for 3/4 the probability is the average between 1 and the probability for x=1/2 which gives 3/4. Then I calculated the recursive formula for numbers of the form x = ((2^n)-1)/2^n which just gives P(x) equals x. Its definetly not a thorough proof as it only works in this specific example . I suppose that is why fractals appear for different coin probabilities
oh i remember looking at this! i managed to solve it assuming P was differentiable at zero, this was needed because i got that it should be fractally repeating as you get closer and closer and needed it to look like a straight line somewhere, i didnt spend that long on it so i wonder if this assumption of differentiability is even true in the weighted case, it looks like it could be but far less clearly so
Wow I like the idea of leaving behind challenges for the comment section to fuddle on. So I'd give y'all a problem I came up with once: You are given 5 points in the plane. Every 5 points in the plane define a unique conic section. Find the tangents to that conic sections at the given points. Good luck.
yeah, both you and I were thinking a level too low, it IS an average of 50/50 as to which end it ends up on given you average all the possible outcomes of all the possible starting conditions, but the video is asking: "For any given point between zero and one, what is the probability it ends up at 1?" that's a much more complex question lol
@@RaiymbekZhasulanuly no, it's only 50% at 0.5, try it at 0.75 and it becomes 75% chance to end at 1 the question is both A) what's the relationship between starting point and probability to end at 1 and B) prove it the answer is 1:1, and this video outlines several proofs, but it turns out that with a coin with any balance other than 50% it turns into a fractal graph
Here's my non-rigorous attempt at insight into the weird shape of the graph for the biased coin. (It can't be fully rigorous because we haven't rigorously defined the weird shape.) It's based on the argument from @B-nu8ss for the fair coin, based on the expected value of the position being x at every step (also how I solved the original problem). That isn't true for a biased coin -- but it isn't true in a particular way. The more steps, the less likely the point is to defy the bias. Let's suppose the coin is biased toward moving left -- by symmetry you can adapt the argument to the other case. With every step, the expected value becomes smaller. So how many steps does it take to get to an endpoint? That's a random variable, call it Y. For most starting numbers x, Y has geometric distribution: P(Y=y)=1/2^y. But if x is a dyadic rational, say with denominator 2^n, then the distribution of Y is truncated: wherever the geometric distribution would give Y>n, we have Y=n instead. That means for dyadic rationals, especially with small denominator, the probability of getting to 1 (defying the bias in the coin) is slightly higher than a smooth pattern would predict. Those are the points where the graph seems to have a sharp corner, steeper to the left and flatter to the right. That's for P(right)1/2, then the graph is flatter to the left and steeper to the right of those points.
4:25 That's not exactly how IEEE-754 floating point numbers work, but sure. (you store the bits for the decimals and exponent like in this example: 1.123 * 2⁴ btw. that number converts to 17.968 and the binary representation is 0 10000011 00011111011111001110110 the first bit says if it's negative or positive, the next 8 bits is the exponent (+ 127 because it's between -127 and +128), and the last 23 bits is the decimal/mantissa)
Some of your viewers are definitely NOT geniuses, and would love to listen to you explain the reasoning and solutions regardless. (Like, I can see it, but damn I can't do the thing!) Maybe a second channel even? MouveBrain?? 😅😆
Before starting solving this problem, I suspected that there will be fractal of dyadic rationals and was confused that it didn't happen, if it's because coin's 50/50 it explain a lot. Now I want to know what happens if it was triangle and not a line and how bias change that. Can you change bias to increase the chance to get from one point in triangle to the particular area of the triangle.
@@MaxCubing11 Pick a triangle with vertices labeled 1, 2, and 3. Pick a point inside the triangle and produce the smallest circle centered on it that intersects a vertex. Imagine a line from the point to each of the 3 vertices, and select a random vertex. Move your point to the spot on the circle that intersects the line to that vertex. You can then ask what is the probability that a given point reaches a given vertex.
0:30 in an im just gonna guess they are equal, so 1/2. since like if you start with a number less then 1/2, all the probabilitys for it should be equal to the corresponding number greater then 1/2, just opposite, so yeah. im most likely wrong though causw that solution seemed too easy
Don't be discouraged! Math written symbolically can be a lot to take in, even with a good bit of experience. If you don't get why something is true, pause the video and try to work it out yourself. If the notation is unfamiliar to you, there are plenty of places online to help you with that
@@PurpleMindCSLol. Can you make video on the " Would you sit on a sword and eat the cake or would you sit on the cake and eat the s word (probably sh1t)?"? (Joke)
Do you accept submissions for additional puzzles? I've had a math question for literal years that neither my geometry professors nor my calculus professors could solve, and I've found no answers to it on a cursory google search, so I'm very curious as to how the collective intelligence of the internet goes about it (and also what the answer is lol).
@JacNoLie, @@SpencerTwiddy If you're interested, I actually just made a discord server: discord.gg/xDJGCzmc. Part of the purpose of the server is exactly so that people can suggest new ideas for videos!
You could do that, but notice that the x = 1/2 case and the 1/2 < x < 1 case actually agree (plug in the numbers and see for yourself). So those two cases can be combined into a single case for 1/2
9:26 what do you mean by "larger"? This is a very vague statement. Both are uncountable infinite, but there probably is a Lebesgue measure to formalise your statement.
Are you sure that these sets are uncountable? I have assumed that they are countable because they are both subsets of the set of all sequences, whose cardinality is countable (proof by bijection on the integers).
Could you say that since every point has a uniform distribution and if the coin flip does not bring the point to the end it is simply picking another initial point thus the outcome is solely depended on the coin?
Looking at the pseudocode, my mind asked me how does it failsafe if the process ever gets stuck in a loop of jumping values between 0 and 1 Do you have a proof that it will always collapse?
Each coin flip always has exactly a 50% chance of ending the experiment, so while there is no guarantee that it will end after any finite number of flips, a computer can run the code fast enough to make that possibility irrelevant.
@@kaustubhpandey1395 This isn't a fully rigorous proof, but the probability that the experiment will end after n steps can be expressed as the sum (1/2 +1/4 + 1/8... 1/(2^n)) which has a limit of 1.
@@kaustubhpandey1395 On each iteration, there's a 1/2 chance that the simulation goes to the next iteration. This means that the probability that the simulation lasts N iterations is (1/2)^N. This probability limits to zero, but that doesn't matter in this case since the probability limitting to zero doesn't change the fact that your computer can hang for an infinite amount of time, since the probability itself is never zero for any real number. Just know that your computer can do a billion iterations in less than a second.
@@kaustubhpandey1395 This is a very good question! I would recommend reading about Las Vegas algorithms, which is a type of randomized algorithm that is very commonly used: en.wikipedia.org/wiki/Las_Vegas_algorithm#:~:text=In%20computing%2C%20a%20Las%20Vegas,differs%20depending%20on%20the%20input.
I dont know what the hell is going on with coding and stuff, I dont know if im wrong but I found like a modular arithmetic thing if the number is rational which I dont know how to solve and a thing to find whether or not a number will be eligible for getting to 1 or 0 on the nth turn.
What font is being used here? I see it all the time in 3blue1brown, and ive wondered what font it is for awhile now. Can someone please tell me? Edit: Ive also been wondering what tool you use to visualize your graphs and stuff
3blue1brown made a tool called Manim, which this video uses. Manim uses LaTeX for typesetting, so by default it uses the default LaTeX math font, probably a version of "Computer Modern".
Bro these types of videos trigger me cause it's so painfully obvious to me that E[x] = x so obviously the probability it's 1 is x and 0 is 1-x. Its basics of random walks which have been studied forever
Like why are we wasting 10 minutes? OK the last part was actually kinda interesting since I also independently discovered that by considering a random sequences of 1s and 0s where the probability the next term is 1 is (1/3 a[n-1] +2/9 a[n-2]..... + 0.7)/3 so the maximum probability is 0.9 when all previous values are 1.
Hey all,
I just noticed I made a slight mistake at 6:10: In the part of the animation where we have b1/2 + b2/4 + 1/2f(0.b3b4...), it should really say b1/2 + b2/4 + 1/4f(0.b3b4...), and in general, the denominator of the fraction in front of f should multiply by 2 at every iteration. The end result shown on the screen is still correct, but the intermediate steps are a bit off because of that.
Also, some of you have pointed out that at 9:29, since the sets are infinite, it is not technically correct notation to write that the cardinality of the one on top is greater than the cardinality of the one on the bottom. Instead it should say that the set on the bottom is a subset of the set on the top, which still has the same implications in terms of probabilities.
That made me think:
what if we allow more integers?
Or what about complex numbers? An octahedron dice (4 sides)?
Even more dimensions?
Thats so amazing dude!
This is out of topic but you sound similar to Derek Muller, Veritasium host/creator. I even thought Derek has another channel.
same description as last video
It's very easy to fall into the trap of assuming f(x) = x at 6:24 and call the problem solved. While the answer is still correct, the fact that this simple function becomes a complex fractal for any P≠0.5 is a good reminder that the kind of rigorous analysis you did at the end was indeed necessary for the proof.
At 9:24, instead of saying that one set is “larger” than the other, which might be a bit confusing given that both sets are countably infinite, you could simply show that the lower set of sequences is a subset of the upper set. It follows immediately from the axioms of probability that P(x_2 -> 1) >= P(x_1 -> 1) and therefore f(x_2) >= f(x_1).
You are correct. See the pinned comment.
For the fractals produced by the biased coin, I think the easiest explaination is to look specifically at what happens at x=~1/2.
Let's consider a coin with a low probability of going towards 1. For values of x slightly above 1/2, if you flip going towards 1, you'll go straight to 1, but if you flip going towards 0, you'll need to flip towards 1 several times in a row just to get back to the middle. So f(1/2+k)=p(coin flips 1)+negligible for k
Yeah, this is essentially the thought process I went through too! I just noticed @mrpojsomnoj3313 was thinking about what happens when we do this experiment inside a triangle instead of a line segment. I wonder what kinds of shapes you get for a probability distribution in that case -- or for that matter, any other shapes! Maybe I'll get around sometime to visualizing this.
@@PurpleMindCSmaybe the tryadics rationals will pop out (I don't even know if they exist 😂)
@@MaxCubing11 Lol
@@PurpleMindCS They are the modulos in relation of the size of the circle and how much that bias would 'typically' shortcut (or not) when it affects the outcome. For a very small circle, the bias is seen over a number of many flips (smooth), but at r=1/2 there is likely to be just one flip proportional to the bias since its already touching both edges. Now imagine a circle with r=1/8, so 4 circles width to width - that could be the "least turns to travel the longest path." If we add a 5th circle of the same r, it would sit beyond the ends. Thats excess until r shrinks down to 1/10, is wasted "shortcutting" and the pattern is "excess" circle which in relation to the bias, producing different mods across all r since the flips are whole integers but the r was continuous.
@@PurpleMindCS I feel like if we want to do this we would end up using Complex Numbers and Nth Roots of 1 in some capacity, which is nice because it feels like that could generalize back to the 2 point case (2nd roots of 1 being 1 and -1 and confining the steps to the real line.)
Since the system is symmetrical, we only need the expression for "probability that a point z eventually goes to 1" P(z->1).
For N = 1/2, P(z->1) = 1/2 + z/2; which works because the result is confined to the reals. If we allow the point to begin off the real line, then whether it begins above or below the line does not matter, implying we need something like (z + z')/2 in place of z in the formula, where z' is the complex conjugate. Indeed, in N>2 case, we would not expect whether z is specifically above or below the real line to have any effect on the probability that it goes to 1, specifically.
Due to rotational symmetry, we expect that the probability that it goes to the Nth root of 1 to be the P(z->1) function rotated about the origin by 2pi/N. This enforces that, at the origin, the probability of ending up at any endpoint is 1/N, since if we add up all the P(z->e^2pi/k) for k from 0 to N-1, we should get 1; that is, the total probability of getting to any of the endpoints should be 1, and the probability from the center is identical in all rotations.
We could probably use similar arguments about the function being increasing along any line between two endpoints to nail down the distribution. The real trick will be proving that starting closer to an endpoint point actually does increase the probability of ending up there, which seems like it ought to be true.
We can replace the clumsy complex conjugate stuff above with something involving the Argument of z so we can track which angled slice of the figure we're in.
I'm not sure exactly what the form of the solution looks like, explicitly. It probably involves a product over terms related to each endpoint so that the whole product goes to zero when it's close to an endpoint that isn't '1'? Hmm.
Fantastic content. Thoroughly rigorous but a nice faster pace that I hope for in UA-cam content.
Thanks so much!
this channel is SO underrated, I saw the animation and thought "oh he must have like a million subs or something". truly amazing stuff
Thank you!
Give it time. Quality like that won't stay hidden for long.
I mean not to hate or anything but this video probably used a software created by 3Blue1Brown
@@dumblockdubbed2455 well it's not just the animation! the sound quality, the engaging script, the background music. everything seems so... professional! did not expect to find this hidden gem today.
@@dumblockdubbed2455 Yes, that is correct. I use Manim, by 3Blue1Brown for these animations.
Extra solution (because lol)
Take a look at the expected value of x. It can't change (when the coin is fair). So it has to be the probability x ends as 1.
Took me a minute but this is genius. You just made this problem trivial with 1 observation.
This is the first thought I had too
I don’t get it, can you explain please
@@FrostedSnowFlakes-
Imagine you started at some x.
I now tell you that I made one coin flip, but don't tell you my result.
So you know there is a 50% chance for the value to be 0 and 50% to be 2x.
The expected value of the value after one coin flip is therefore still x.
This logic can be applied symmetrically for the case x > 0.5, and recursively for multiple flips.
We assume the process eventually ends (it doesn't have to but every flip has a 50% chance to do so), and find out the expected value is still x.
But the value can only be 0 or 1, and there is a bit of extra algebra here, but I'm too lazy to write it here.
My attempt at reasoning about the fractal with the biased coin:
At 1/2, the probability of reaching 1 is X, and of reaching 0 is 1-X.
For reasons stated in method 1, the entire left half should be a similarly scaled version of the whole object, and so should the right.
Applying this recursively should give some nice fractal pattern.
I think the self-similar fractal happens because the problem itself is self-similar. Each flip of the coin, either the game ends, or half of the initial values turns into the full set.
This was terrific! Great explanations and visualizations, keep it up
Thanks so much!
Great video! I found your channel too late to submit anything for this first one, but I did find (without a proof) that f(x) = x. I’m excited to see what I missed in my solution to the dice problem!
Thanks! Looking forward to putting that all together.
This was a fun problem! I missed the original video and found it through this, but I had a blast solving it anyways before watching this one. I hope we get more of these in the future!
Thanks so much! The plan is for there to be more to come :)
A puzzle I’ve tried to solve is the probability that when picking k dominos from a triangular set from double blank to double l, that they form at least one chain that uses every domino picked, Mexican train style. There are countless ways to extend this such as the probability that a certain domino is the beginning of the chain. For k=2, I got (4l-4)/(l^2 +5l +6) and I’ve also figured out k=3, too.
I believe there is this book by Barnsley which treats these kinds of self-referential functions. I would highly recommend any viewer which is curious about these kinds of functions to read “Fractals everywhere”.
1:34 woah.
I had quite a bit of fun working on the problem! Ultimately I didn't reach a solution, but I don't think that's really what mattered :D
Glad you enjoyed and submitted what you had! I'm trying to incorporate as many different peoples' work as possible in a coherent way.
10:55 - SPOIL IT!
I imagine it comes from the the fact our probabilities come from a recursive application of a function on our binary expansion, combined w the inherent fractal nature of digit expansions like that.
(Imagine writing binary numbers with an infinite number of leading 0s, and color 1s black, 0s white. You will see a pattern where each time you add a digit, i.e going from 2 digit binary numbers to 3 digit numbers, you take the 2 digit binary numbers, duplicate it, and give the first half a leading 0 and the second half leading 1s.
00
01
10
11
Into
000
001
010
011
100
101
110
111)
If you pay attention to the graph, it appears the duplication points happen on the diatics.
The way I came to method #1:
You can look at where the coin ends up if you never take the 50% chance that the point ends up on one of the endpoints. Record down at each step if x < 0.5, or x > 0.5.
This process basically encodes the input number as a base 2 decimal! (input to the next step is the fractional part of 2x, output is equal to whether 2x < or > 1)
The probability calculation just happens to look exactly like base 2 decoding. (assuming you terminate when x equals exactly 1/2.)
The rest is the painful work of formalizing and proving that intuition.
whiiich. I didn't really know how to do because I'm a programmer, not a mathematician, lol.
Great video! It was really well explained and is something which I haven't seen anyone else really talk about. Looking forward to the next part :D
6:23 the question here is whether the function is continuous… if it is, then the diadic rationnals being dense in R, the function *is* f(x) = x. But yeah if you can prove that the f(0.b_k b_k+1 …)/2^k goes to 0 it does seem to work quite well.
Edit : I like method 2 better x')
-
Just seeing this makes me wanna try on the n-simplex : instead of just two points 0 and 1, use n (evenly spaced) vertices and see what happens !
Edit : maybe picking the ending point with a coin flip makes that harder… unless we only deal with the vertices and forget the inside and different faces of the simplex.
There's an easy solution which is being missed here if you know a bit more advanced probability theory. Simply observe that the process of position of the point over time forms a bounded martingale, so the optional stopping theorem applies. Hence the initial position equals the expectation of the ending position, and since the ending position is either 0 or 1, this expectation is the probability of ending at 1. Therefore the probability of ending at 1 is x and we are done. See en.wikipedia.org/wiki/Optional_stopping_theorem
yo wth? only 160 comments. you deserve a heck of a lot more, keep going.
Thanks so much!
@@PurpleMindCS no need to thank me brother, your content speaks for itself
Ok, I gave the problem a try before watching the video and while I haven't really solved it and only came up with a heuristic argument, I'd still like to share my thought process:
First we conjecture that f(x) = x based on the highly rigorous reasoning that f(0) = 0, f(1/2) = 1/2 and f(1) = 1; and f(x) is probably continuous.
then we know that f(x) = f_1(x) + f_2(x) + f_3(x) + ... Where f_i(x) is the probability that the sequence ends of trials ends on the number 1 after exactly i iterations. (Basically, the probability that the sequence finishes on 1 = the probability that the sequence finishes on 1 after 1 coin flip + the probability that the sequence ends after 2 coin flips and so on).
f_1(x) = 0 (0
Spent way too long on this given that its not rigorous at all
The expected displacement of the point on each iteration is 0, by construction. (In other words, this is a martingale.) Thus, the expected *total* displacement must also be 0, so the expected endpoint must equal the expected starting point, x. Since the endpoint is always 0 or 1, the only way that this can happen is for P[end at 1] = x.
I'm not well-versed in martingale theory myself, but I get the gist of what you're saying and I think it's really funny that the "expected displacement" is zero even though the only possible outcomes are the opposite extremes.
This is an amazing solution icl
@@fredfred9847 I agree! It's quite short, which is very elegant. However I also think there are merits to a lot of different methods. While they may all lead to the same answer to the question if done correctly, the different perspectives on the puzzle not only add to our toolbox of problem-solving techniques but also provide insights for the intuition behind various aspects of the solution, in addition to suggesting variants of the question, such as the biased coin variant which produces the fractal pattern.
@@PurpleMindCSyou don't have to call it martingale theory it's just finding an invariant and knowing there's only 2 possible end states.
The Wikipedia article on gamblers ruin (specifically Huygens result which generalize to unfair coin flips by finding a different invariant)
Now, let's try finding the expected number of steps this would take.
We know we start at x and finish at 0 or 1 which means a variance of x(1-x).
Each step at x has a variance of x² or (1-x)² if x > 0.5.
so the remaining variance is x(1-2x) or (1-x)(2x-1)
ok I think the solution here is probably discontinuous so we'd need simulation/harder math,
but let's look at smaller cases:
for x = 0.5 it's 1 step
for x = 0.25 or 0.75 it's 1 or 2 so 1.5 on average
for x = odd/8 it's 1 or 1+(1 or 2) so 1.75 on average
so it looks like for a non binary number it's probably 2 in the limit.
Would be nice to get a satisfactory explanation for why
I graphed it and a simple intuitive explanation is that x(1-x) has an average value of 1/6
while the x(1-2x) or (1-x)(2x-1) has an average value of 1/12 so we have half as much variance.
Oh lol this is painfully obvious my bad it's just a exponential distribution so obviously
50% of 1 step
25% of 2 steps
12.5% of 3 steps
.
.
.
averages to 2
best solution i've seen, really mindblowing if you thought of this the first time and didn't derive it based on the solution
Math and computer science channels are definitely my favourite! Please keep it up ❤️❤️
Amazing content!! Glad I got recommended to your channel.
Thanks so much!
UA-cam accidentally recommend me a video i could never relate to
*Suffers in crippling mathematical inability*
Even if you don't think you could've figured out the solution on your own, I hope you at least enjoyed watching the video and learned something from it anyway! In fact, several submissions I've gotten for this project so far have been from people who didn't fully complete the problem, but rather just had some first observations / general approaches. The process of doing math can be slow, and every bit of progress, no matter how small, can be celebrated!
+1
Can you make math videos that explain media or tv show scenarios.
This type of content could better help students learn and see how math is relatable through media we’re familiar with.
this is the 1d case of "walk on spheres" algorithm which can be used to smoothly interploate boundary values over a space in any dimension :)
Yes, that's right!
Nice problem, havent seen the first video, but i love the combination of math and computer science done here! Would have totaly written a program if i had watched the first video
Another way to view the fractal pattern is to notice what happens to the binary formula. With an arbitrary probability p we get a formula f(0.b₁b₂...) = p b₁ + p f(0.b₂b₃...), so 1/2 replaced with p, but the expansion is still binary. It has the effect of replacing b₁/2 + b₂/4 + ... = ∑bₖ/2⁻ᵏ by b₁p + b₁p² + ... = ∑bₖpᵏ. So the fractal pattern comes from taking the binary expansion of x and then replacing all the powers of 1/2 with powers of p.
This is also the reason why it has this jumping behavior near all the dyadic rationals, take 0.1 for example. The number x₁ = 0.0111111111₂ is really close to x₂ = 0.1000000000₂, since they only differ by 0.0000000001₂, however f(x) would replace every 1 with a power of p, not 1/2, and so the powers of p in f(x₁) and f(x₂) don't add up anywhere close.
It's also curious that even though the curve is fractal it still seems to be continuous at every point. This can also be proven: if we flip bₖ in x, that will just flip p⁻ᵏ in f(x). That means that for every ε > 0 we can find a bit bₖ such that flipping it (or any bit after that) only changes f(x) by less than ε.
Yeah, that's a good way to put it. Recently I've become curious to see if anyone can find a formula for a "curve of best fit" (however you may define that) through the fractal pattern, since it seems to have some sort of defined shape.
It's funny you thought the curve was continuous at every point - my first thought was the curve was discontinuous at every point. Turns out we're both wrong:
In your example, you showed curve is discontinuous at 0.5. It's also discontinuous at every dyadic rational using the same logic. But the discontinuity is only on the left side, the function is right-continuous everywhere.
@@timpressey Do you mean "continuous" or "smooth?" I don't see how the function isn't continuous, as even at the dyadic rationals, an arbitrarily small change in x seems to produce an arbitrarily small change in f(x) in either direction. I think silentob's argument is just that the function is not differentiable at the dyadic rationals.
That's not quite the correct formula, as that assumes a probability of p for going left and a probability of p for going right, which generally does not make sense for any p other than 1/2. The correct formula would be f(0.b₁b₂...) = p b₁ + (1-p)f(0.b₂b₃...) if b₁ = 1 and f(0.b₁b₂...) = (1-p)b₁ + p f(0.b₂b₃...) if b₁ = 0. I don't immediately see a way to simplify this, which makes sense is the result is a function that is continuous everywhere (probabiy, I haven't proved it...), but not differentiable on a dense subset of the domain, and these rarely have nice closed-form descriptions.
Note that the function you give is not continuous at the dyadic rationals, and also at x = 1 gives a value of p + p^2 + p^3 + ... = 1/(1/p - 1), which is only equal to 1 at p = 0.5.
@@danielgostein3039 I did mean continuous, and I was talking about the function f(0.b₁b₂...) = ∑bₖpᵏ. Take p = 0.25 for example: at 0.5 we have f(0.1₂) = 1/4, but f(0.0111111...₂) = 1/12 by summing the geometric series. (More precisely, any value x < 0.5 will have f(x) < 1/12). So there is a discontinuity to the left of 0.5.
The problem is what @reginaldlybbert7374 points out: the function f(0.b₁b₂...) = ∑bₖp does not describe the function at the end of the video, the formula just happens to work at p = 0.5 because p_left = p_right = 0.5.
Today, I came up with a puzzle: you have a function (c(x) = sin(x)) and a circle r=1. What is the highest y coordinate of the circle where it still touches the curve at each x position? The height is then given by the function h(x). Things I found out: h is oscillating from 1 to 2. Create the function f(x)=c(x)+sqrt(1-(x-x0)^2), x0 being the x-position of the circle, the highest point of f equals h(x)
9:25 it might be better to say that it's a subset of the other set, as their cardinslities will usually be equal to |R| and each other.
I missed the first video, but I still want to make a guess before seeing the solution:
I say that the probability is x itself. We solve this problem by finding a recursive formula for the probability given x. If x is smaller than 0.5 the circle hits 0 on the left and some other number on the right. As that number has the same distance to x as x has to 0, it must be twice the value of x. So p(x) = 0.5 * 0 + 0.5 * p(2x) [if x < 0.5]. If x is bigger than 0.5 the circle hits 1 on the right and some other number on the left. As that number has the same distance to x as x has to 1, it must be twice the value of x minus 1. So p(x) = 0.5 * 1 + 0.5 * p(2x - 1) [if x > 0.5]. We continue by making two observations: a) when looking at the binary representation of the number x, if the first digit after the dot is 0 the number must be smaller than 0.5 and if it is 1 it must be greater or equal to 0.5 and b) multiplying by two (and subtracting one of number is greater than 0.5) is equivalent to left shifting the number by one (and cutting off any non decimal place). We can rewrite the formula now as follows: p(x) = 0.5 * x_1 + 0.5 * p(x
Your explanation is unsettlingly similar to the video for not having watched it yet! Wow.
@@PurpleMindCS I smiled the whole way through the video. I was not expecting to be this close!
Great video! the manim animations look and feel great, congrats 🎉🎉
Thank you! Glad you enjoyed.
i knew there was gonna be some fractalness somewhere!
i also was curious what would happen if you get the expected number of flips to reach 1 or 0
Do I get a special prize for being a math genius?
Yes -- you get permanent free access to all future PurpleMind videos!
🏅
Yes, harder math problems to challenge your genius brain
@@PurpleMindCSWhere is the indigo
@@NikoCubeRoot I recognize you!
lol I love how youtube algorithm recommended me this video. Keep going!
Thank you!
Underrated channel right here 💯
Thanks so much!
The appearance of the fractal at the end reminds me of this wonderful functional equation, somewhat similar to the one considered here: f(x) = f(x/2) + f((x+1)/2). This (up to linearity) has only a single continuously differentiable solution, but many continuous solutions, which nevertheless can be completely described, though this is quite tricky.
The continuously differentiable solution is 2x-1. The other continuous solutions all look like the Weierstraß function: They are of form W = \sum_k w(2^k x)/2^k, where w is a function satisfying the functional equation w(x+1) = -w(x) (like sin and cos). This can be shown by considering a certain transform of a solution which is the inverse of the mapping w \mapsto W.
The fractal looks like a relative of (if not an instance of) the so-called blancmange curve which, unsurprisingly, is defined in terms of powers of two. Wikipedia currently has an article on it, as does MathWorld.
My solution for this problem:
.
.
.
After each coin flip, the expected location of the coin does not change. Since the process almost surely terminates, the final expected location will remain x. This implies that the probability it ends at 1 is x and the prob. it ends at 0 is 1-x.
There's a fun subtlety here. This function you mentioned is actually not a function! It is a family of functions indexed by the limit set of coin flips (isn't that the Cantor Space?). What y'all have done is actually prove that these statements are true for every function in the family!! I love the idea of changing the underlying set by changing the random variables used. I wonder what you can say if you get more general about the behavior of these random variables.
Loved your video and want more, subscribed!
Thanks!
I have this interesting idea for the Riemann Zeta function. It uses derivatives of the permutation function.
My argument by symmetry was a bit hand-wavy, and not really a full solution:
First, we know that the probability this doesn’t end is (1/2)^infinity=0. Now, the probabilities must either be 50-50 or dependent on x:
P(x ends 1) + P(x ends 0) = 1
By symmetry:
P(x ends 1) = P(1-x ends 0)
P(x ends 0) = P(1-x ends 1)
Let F(x) = P(x ends 1). Then:
F(x) + F(1-x) = 1
For the greatest n such that x is between 1-(1/2)^n and 1, look at a decision tree: x either goes to 1 or leaves the “neighborhood”. This means that there must be less average moves left to end at 1 the closer x is to 1, so F(x) must be increasing.
The most intuitive and simple guess here is F(x) = x. This is bolstered by the fact that F(x)+F(1-x)=1 implies F(.5)=.5 and F(1)=1 implies F(0)=0.
the fair coin graph is a fractal too, its just degenerate
My solution before watching the video past the problem description:
Say x is a binary number: x=0.1101110...
Also, define whose "turn" it is as T=0 or T=1. At the start, set T=0.
Now on each step, we can check if x
Clicked and felt my skull volume expand ≈ 23.8485936%
this series is very interesting, loved the concept!!
Thank you!
I find the fractal answer so much more understandable. You telling me this dynamic recursive formula is just an alias for f(x)=x ?! That's nutso
Yeah, it's quite surprising at first, isn't it?
Collaboration and Clear Clarification.
Before watching video:
Notice that from the perspective of the mid point, going to the right is identical probabalistically to going to the left. Therefore: The inverse probability of any statement is true of the opposite side.
Next, notice at 1/2 of the line, the odds of going to 1 (which we will now ONLY talk about these odds, as the inverse is the same thing) is a 50/50 AND it must happen on a single coinflip.
Next, let's ask about the point 1/2+1/4
This point is at 3/4ths, and initially the circle is 1/4th wide. But if it goes left, we return to the middle point, who is then a 50/50 (and will conclude the experiment)
So we do a 50/50, into another 50/50 to NOT go into the 1.
Therefore: at 3/4ths, the probability of going to 1 is a 3/4.
Repeat ad neasuem.
Now the only question that is left is how does this work when you are not perfectly afixed to a point who is in the series 1/2 + 1/4 + 1/8... or 1/2 - 1/4 - 1/8 ......
Let's study the charachter of this movement from .6
.6-> .2->.4->.8->.6
We find a repeating cycle from the initial position, around back eventually to the initial position.
The length of time to leave the side you started on is: what bracket of 1/2+1/4+.... you were in when you started.
Therefore: We know for a fact that the 1/2+1/4+1/8.... probabilities define "probability buckets" for their neighbors, which I will now arbitrarily declare to be relatively linear, and therefore:
The odds to go to one if you are at .6 is .6 and the odds to go to one if you start at .99 is .99, and vice versa. The odds to go to one at .01 is .01.
Maybe I was too quick to finish the problem, but I think i'm satified with my solution.
After video: My solution is right? Lets go!
The final tidbit at the end, if i had to guess, it is following the bucket sizes. Where the largest relative maximum happens exactly at 1/2+1/4+1/8.... and 1/2 - 1/4 - 1/8 - 1/16th.... Why this is? It seems intuitive, and so its kind of hard to explain, but when you are drifting towards one or the other, being on one of these bucket values makes you have less total coin flips before hitting the end.
For instance, 1/2 is a 50/50 to hit into 1 IMMIDIATELY, but so is slightly less than 3/4ths. I would guess this is why the graph is no longer linear, and all bumpy.
Edit: oh also there is a special charachteristic of points like 1/2+1/8th. if they fail to go to one, its - (1/2 - (1/2 + 1/8th)) for the next point location = 1/8th.
But 1/8th is in the series that's perfectly collapsing. So there is another something special about these points, which directly lead into collapsing coinflips (determenisticly ending, cannot endlessly loop)
Hey can you someday make tutorial on how to make these types of animations, we need way more channels like this!
I use a library called Manim, created by 3Blue1Brown. The community edition is open-source and pretty well documented: www.manim.community/
decided to become a viewer
Lol
Great videos, I am looking for more
Thanks so much!
Thank you!
That is such a nice problem
Thanks!
Unfortunately my math level is inadequate
I dont see anyone solving this problem the way I did so I'll just say it here. I first thought about the only point we know the probability of . For x = 1/2 the probability is one half . Then I realised that for example , for 3/4 the probability is the average between 1 and the probability for x=1/2 which gives 3/4. Then I calculated the recursive formula for numbers of the form x = ((2^n)-1)/2^n which just gives P(x) equals x. Its definetly not a thorough proof as it only works in this specific example . I suppose that is why fractals appear for different coin probabilities
3:45 look here, this is what your talking about, it doesn’t work as although there are infinite dyadic rationals they are not all the reals :(
@@tysonwu6312 proof by its obviousy continuous
oh i remember looking at this! i managed to solve it assuming P was differentiable at zero, this was needed because i got that it should be fractally repeating as you get closer and closer and needed it to look like a straight line somewhere, i didnt spend that long on it so i wonder if this assumption of differentiability is even true in the weighted case, it looks like it could be but far less clearly so
Only 1550 subscribers??? Well, time to make it a palindromic number!
Lol, thank you :)
Wow I like the idea of leaving behind challenges for the comment section to fuddle on. So I'd give y'all a problem I came up with once:
You are given 5 points in the plane. Every 5 points in the plane define a unique conic section. Find the tangents to that conic sections at the given points.
Good luck.
Method #2는 그저 함수가 단조증가함을 나타낼 뿐이며, 6:50의 그래프와 같이 점 사이의 파형이 어떻게 나타나는 지를 이야기 하지 않습니다. 함수는 각 점에서 선형적으로 증가하고 각 점 사이에서 단조증가하지만, 여전히 각 점 사이에 파형이 존재할 수 있습니다.
Me with my: For every situation you'll find it's symmetric version except x at 1/2, thus, chances are 50/50
That is my thought too. I wonder if there is some subtlety we are missing.
@@michaeldamolsen Maybe, if there was someone who would explain
yeah, both you and I were thinking a level too low, it IS an average of 50/50 as to which end it ends up on given you average all the possible outcomes of all the possible starting conditions, but the video is asking:
"For any given point between zero and one, what is the probability it ends up at 1?"
that's a much more complex question lol
@@TheAechBomb It's still 50%. I guess video is asking how to solve it with algorithms
@@RaiymbekZhasulanuly no, it's only 50% at 0.5, try it at 0.75 and it becomes 75% chance to end at 1
the question is both
A) what's the relationship between starting point and probability to end at 1
and
B) prove it
the answer is 1:1, and this video outlines several proofs, but it turns out that with a coin with any balance other than 50% it turns into a fractal graph
Here's my non-rigorous attempt at insight into the weird shape of the graph for the biased coin. (It can't be fully rigorous because we haven't rigorously defined the weird shape.) It's based on the argument from @B-nu8ss for the fair coin, based on the expected value of the position being x at every step (also how I solved the original problem). That isn't true for a biased coin -- but it isn't true in a particular way. The more steps, the less likely the point is to defy the bias. Let's suppose the coin is biased toward moving left -- by symmetry you can adapt the argument to the other case. With every step, the expected value becomes smaller. So how many steps does it take to get to an endpoint? That's a random variable, call it Y. For most starting numbers x, Y has geometric distribution: P(Y=y)=1/2^y. But if x is a dyadic rational, say with denominator 2^n, then the distribution of Y is truncated: wherever the geometric distribution would give Y>n, we have Y=n instead. That means for dyadic rationals, especially with small denominator, the probability of getting to 1 (defying the bias in the coin) is slightly higher than a smooth pattern would predict. Those are the points where the graph seems to have a sharp corner, steeper to the left and flatter to the right. That's for P(right)1/2, then the graph is flatter to the left and steeper to the right of those points.
4:25 That's not exactly how IEEE-754 floating point numbers work, but sure.
(you store the bits for the decimals and exponent like in this example: 1.123 * 2⁴
btw. that number converts to 17.968 and the binary representation is 0 10000011 00011111011111001110110
the first bit says if it's negative or positive, the next 8 bits is the exponent (+ 127 because it's between -127 and +128), and the last 23 bits is the decimal/mantissa)
isnt it true for the range 0-1?
well, who said that he used floating point numbers. He clearly was using fixed point numbers
Some of your viewers are definitely NOT geniuses, and would love to listen to you explain the reasoning and solutions regardless. (Like, I can see it, but damn I can't do the thing!)
Maybe a second channel even? MouveBrain?? 😅😆
we can generalize this to a triangle and a 3-sided coin
3-sided coin lol
@@felipedutra5276 Yes, of course. You haven't heard of that? ;)
@@felipedutra5276 sadly most 3 sided coins are incredable biased
@@monkyyy0You're better off with a 3-sided die for sure.
Before starting solving this problem, I suspected that there will be fractal of dyadic rationals and was confused that it didn't happen, if it's because coin's 50/50 it explain a lot. Now I want to know what happens if it was triangle and not a line and how bias change that. Can you change bias to increase the chance to get from one point in triangle to the particular area of the triangle.
That is a really neat idea! If you end up playing around with this, I'd love to see what you find.
I don't understand how we can change this problem from a line to a triangle
@@MaxCubing11 Pick a triangle with vertices labeled 1, 2, and 3. Pick a point inside the triangle and produce the smallest circle centered on it that intersects a vertex. Imagine a line from the point to each of the 3 vertices, and select a random vertex. Move your point to the spot on the circle that intersects the line to that vertex. You can then ask what is the probability that a given point reaches a given vertex.
Ah... what if I saw first video just now and in half an hour reach 1st solution? I don’t think it making me math genius, because it basically easy.
binary fraction proof is the simplest and coolest
ªMy Viewers Are Math Geniusesª (i have just asked my teacher)
Mom! I'm a genius he said it!
Well, that code leaves a little to be desired... 😅🤔
0:30 in an im just gonna guess they are equal, so 1/2. since like if you start with a number less then 1/2, all the probabilitys for it should be equal to the corresponding number greater then 1/2, just opposite, so yeah. im most likely wrong though causw that solution seemed too easy
good video but can you change the font? this one is too thin and it hard to see
I feel like I'm looking at ancient egypt hierolygraphics
Don't be discouraged! Math written symbolically can be a lot to take in, even with a good bit of experience. If you don't get why something is true, pause the video and try to work it out yourself. If the notation is unfamiliar to you, there are plenty of places online to help you with that
@@ambiguousheadline8263 I know but how do I pronounce the last word in my comment correct?
Seconded
@@PurpleMindCSLol.
Can you make video on the " Would you sit on a sword and eat the cake or would you sit on the cake and eat the s word (probably sh1t)?"?
(Joke)
@@ambiguousheadline8263I finally know to how to spell it
this community is amazing, I'm just too dumb for it😭
I didn’t really understand the problem… on average, 1/2 will end up with 1 and the other 1/2 will end up with 0…. That’s it I think
Do you accept submissions for additional puzzles? I've had a math question for literal years that neither my geometry professors nor my calculus professors could solve, and I've found no answers to it on a cursory google search, so I'm very curious as to how the collective intelligence of the internet goes about it (and also what the answer is lol).
Is it difficult to formulate the question? If not, paste it here in the comments?
@JacNoLie, @@SpencerTwiddy If you're interested, I actually just made a discord server: discord.gg/xDJGCzmc. Part of the purpose of the server is exactly so that people can suggest new ideas for videos!
@@PurpleMindCS cool, I might check it out. I’m currently 5/7th done bingeing your videos, definitely going to subscribe after I finish.
Can you share video code??
Shouldn’t there be 5 cases in the recurrence, not 4?:
x=0, 0
You could do that, but notice that the x = 1/2 case and the 1/2 < x < 1 case actually agree (plug in the numbers and see for yourself). So those two cases can be combined into a single case for 1/2
Before watching: 💩
After watching: 🗿
9:26 what do you mean by "larger"? This is a very vague statement. Both are uncountable infinite, but there probably is a Lebesgue measure to formalise your statement.
Yes, you are correct. See the pinned comment.
Are you sure that these sets are uncountable? I have assumed that they are countable because they are both subsets of the set of all sequences, whose cardinality is countable (proof by bijection on the integers).
@@stylextv The sets are countable, but the point still stands about the comparison their "sizes"
1:00 in
is the answer not 50/50?
7:38
You should prove that f(x) increase in a construction speed
Right! Right!?
Could you say that since every point has a uniform distribution and if the coin flip does not bring the point to the end it is simply picking another initial point thus the outcome is solely depended on the coin?
can you use this to implement arithmetic compression schemes?
Not exactly sure what you mean. Would you mind elaborating?
About Probability?
I have arrived to disprove your conjecture
10:20 wait that’s literally the blancmange curve (see for yourself on Wikipedia)
Ooh cool! I wasn't aware of this before.
Looking at the pseudocode, my mind asked me how does it failsafe if the process ever gets stuck in a loop of jumping values between 0 and 1
Do you have a proof that it will always collapse?
Each coin flip always has exactly a 50% chance of ending the experiment, so while there is no guarantee that it will end after any finite number of flips, a computer can run the code fast enough to make that possibility irrelevant.
@@danielgostein3039 can you rigorously show that this probability of infinite steps limits to zero?
@@kaustubhpandey1395 This isn't a fully rigorous proof, but the probability that the experiment will end after n steps can be expressed as the sum (1/2 +1/4 + 1/8... 1/(2^n)) which has a limit of 1.
@@kaustubhpandey1395 On each iteration, there's a 1/2 chance that the simulation goes to the next iteration. This means that the probability that the simulation lasts N iterations is (1/2)^N. This probability limits to zero, but that doesn't matter in this case since the probability limitting to zero doesn't change the fact that your computer can hang for an infinite amount of time, since the probability itself is never zero for any real number. Just know that your computer can do a billion iterations in less than a second.
@@kaustubhpandey1395 This is a very good question! I would recommend reading about Las Vegas algorithms, which is a type of randomized algorithm that is very commonly used: en.wikipedia.org/wiki/Las_Vegas_algorithm#:~:text=In%20computing%2C%20a%20Las%20Vegas,differs%20depending%20on%20the%20input.
not all...
I dont know what the hell is going on with coding and stuff, I dont know if im wrong but I found like a modular arithmetic thing if the number is rational which I dont know how to solve and a thing to find whether or not a number will be eligible for getting to 1 or 0 on the nth turn.
What font is being used here? I see it all the time in 3blue1brown, and ive wondered what font it is for awhile now. Can someone please tell me?
Edit: Ive also been wondering what tool you use to visualize your graphs and stuff
3blue1brown made a tool called Manim, which this video uses. Manim uses LaTeX for typesetting, so by default it uses the default LaTeX math font, probably a version of "Computer Modern".
@@int32_ Thank You! I never knew this, but yeah, it looks exactly right, so thank you so much for this!
@@int32_ Yup
Bro these types of videos trigger me cause it's so painfully obvious to me that
E[x] = x so obviously the probability it's 1 is x and 0 is 1-x.
Its basics of random walks which have been studied forever
Like why are we wasting 10 minutes?
OK the last part was actually kinda interesting since I also independently discovered that by considering a random sequences of 1s and 0s where the probability the next term is 1 is
(1/3 a[n-1] +2/9 a[n-2]..... + 0.7)/3
so the maximum probability is 0.9 when all previous values are 1.
Do you have a discord server?
Just made one! discord.gg/xDJGCzmc
Is the title confirmation bias or your channel is literally only shown to math geniuses?
I think that's for you to decide ;)
The discord invite link in your channel page has expired; thought you'd want to know!
Thank you! I just updated the link and it shouldn't expire now.
Great vid pls blowup