Counter-Intuitive Probability Puzzle: Random Walkers Meeting On A Grid

Alice and Bob start at opposite corners of a 5x5 grid. Alice moves up/right randomly and Bob moves down/left randomly. What is the chance they meet? What happens for an nxn grid? As n goes to infinity, the answer is interesting and involves pi! Watch the video for the solution.
My blog post for this video:
wp.me/p6aMk-57D
Links for asymptotic formula
en.wikipedia.o...
en.wikipedia.o...
en.wikipedia.o...
math.stackexcha...
planetmath.org/...
If you like my videos, you can support me at Patreon: / mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisio...
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.co...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 3.8/5 stars on 27 reviews) www.amazon.com...
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 2 reviews) www.amazon.com...
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 13 reviews. www.amazon.com...
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) www.amazon.com...
"Math Puzzles Volume 3" is the third in the series. (rated 5/5 stars on 3 reviews) www.amazon.com...
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.7/5 stars on 10 reviews) www.amazon.com...
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 3 reviews) www.amazon.com...
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 3 reviews) www.amazon.com...

[@tamirerez2547]

One of the BEST explanation EVER!! Step by step, very clear, cold logic, great animation, forced conclusions, solution!! Pure art. Bravo!

[@Dreadpirate404]

12:01 Did YOU figure this out? Never before has Price infused so much delicious salty-sass in his delivery. We said we wanted harder problems. He delivered.

[@shameekbaranwal]

Salty Sass xD

[@ashirizly]

I actually got the probability for the specific case down, so I felt pretty good. (shamed that I didn't recognize the pattern of 1,5,10, but I'll live with it, somehow...)

[@Dreadpirate404]

MisterCyanide That's actually good to know. I swear every time it sounds like Price to me.

[@steffen5121]

MisterCyanide My name Jeff...

[@glowingfish]

@MisterCyanide I think is name should be Price, because it is clear that Price is right.

[@yxlxfxf]

More problems like this one, please.

[@yohansaldana8218]

Wow,168 likes and I'm the only one who replied.

[@ryanye8441]

@@yohansaldana8218 you are not, lol

[@twwc960]

This is an awesome problem! Easy enough that I was able to get it but hard enough that I felt a sense of accomplishment. I did cheat a bit. At one point in the solution I did a google search for sums of squares of binomial coefficients, and I was led to a page on Vandermonde's identity. I also had to look up the Stirling approximation for factorials, as I had forgotten its exact form. But I got the problem, mostly. This is much better than your "90% of people get this trivial algebra problem wrong" videos.

[@turun_ambartanen]

I didn't know about those rules, but i got the ugly solution with the summation :)

[@merubindono]

twwc960 Nah, I don't think that's cheating. That's just being resourceful!

[@peter_castle]

Im glad you could advance, doesnt matter the cheating, you still smart and hard worker student, but please if yu think a video is too easy, why criticize? cant he make videos for "dumber" people? There is a lot of dumb people, they want to feel included too.

[@aorbital3628]

What grade are you in???

[@nsnick199]

*pauses video* Let's see... The two can only meet in the middle, so we only need to look at that diagonal, and with symmetry we only need to look at 3 points. The odds of the two meeting are: Pab = 2(Pab1 + Pab2 + Pab3), where Pab1 is the odds of Pa1 * Pb1, Pa1 is the odds of A landing on point 1, etc. since the two are mirrored, this is the same as: Pab = 2(Pa1^2 + Pa2^2 + Pa3^2) Pab = 2( (1/2^5)^2 + (5/2^5)^2 + (10/2^5)^2 ) Pab = 2( (1 + 25 + 100) / 2^10 ) Pab = 126 / 2^9 Pab = 0.24609 Pab ~= 25%

[@xXDarQXx]

Except that Pa1 =/= 1/2^5 because we're not calculating the probability of A reaching 1; we're calculating the probability of A passing through 1. In other words, from all possible routes that A can follow, which of them pass through 1

[@rohanchopra1539]

Permutations & Combinations, Binomial Theorem and Probability, all stuffed in a single question. Loved it!

[@colgatelampinen2501]

Not much stuffed, those are related

[@jumpman8282]

Thanks for the very intuitive explanation to _why_ the center binomial coefficient on row 2𝑛 of Pascal's triangle is the sum of the squares of the binomial coefficients on row 𝑛.

[@jacoboribilik3253]

Yes. Double counting proofs are marvelous. Discrete math has a taste no theorem in Analysis will ever match!

[@jojojorisjhjosef]

seems like when you upload a probability video no one gets mad because it's always hard lol.

[@jumpman8282]

Haha, yeah no one dares to argue :)

[@jamesdean7405]

"hey this is pressure locker"

[@ABHISHEKSHARMA1993]

James Dean Fresh Tall Walker*

[@TheLucidDreamer12]

Fred Towelwaller

[@attackaffection5444]

He is an Indian bro... You can't expect his name to be pronounced easily in English...

[@parkamark]

Now do it for an n × n × n cube (3D space). And then generalize that for any multi-dimensional hyper cube with side length of n. Awesome video, and problem!

[@GretgorPooper]

I was kinda disappointed by the explanation actually, especially when 1/sqrt(4pi n) is pulled out of nowhere instead of explained :(

[@BoundlessxArts]

Pi outta nowhere!

[@franzschubert4480]

Matt Parker would love this.

[@BoundlessxArts]

Or Randy Orton 😂

[@villaholland]

8 Bit Metal Covers OMG PI OUTTA NOWHERE uh I mean RK PI

[@lazaruslong697]

Franz Schubert: Oh, i bet he knows this already and loves it nonetheless. :D

[@DerToasti]

i haven't had anything with this sort of probability stuff in school yet but i know that the sum of (binomial(2k,k)/(4^k*(2k+1)))=pi/2 (taylor series for arcsin I think) so that might be slightly related. it might also not be at all since it's a sum...

[@danthepyroman1]

Hey this is pressure locker😂

[@hectobreak8097]

DanTheMan Hey this is fresh tall walker.

[@zwz.zdenek]

Can't unsee that.

[@quasquaswex4430]

Hey this is Press Toe Hawker

[@jancerny8109]

Thanks for the clip. I'll confess I screwed it up completely--I was thinking of the problem in the wrong way. I treated each of Alice and Bob's successive moves as a fifty percent probability, without accounting for the fact that geometry (duh) dictated that some points would be more probable than others. I hope I learn from that mistake.

[@DavidIngerman]

The meeting probability is simply the probability of going from A to B, going right and up. So, it equals 2n choose n?

[@ComradeChams]

It's cool to see that pascal's triangle show's up in your explanation.

[@Phantomuxas]

MindYourDecisions, this was great. More advanced problems is the way :) thank you for the video. I could solve the problem, but the simplification of the formula was very nice.

[@thevikckick]

very interesting video, always happy to see new uploads from you.

[@pianfensi]

error at 8:25 its to the power of n

[@davidb5205]

Before looking at the answer, my guess: I did a bunch of smaller grids 2x2, 3x3 and saw a pattern dealing with Pascal's triangle/binomial expansion. The probability ends up being 1/(total paths) so for a grid of 5x5, the total number of paths is 252. Probability of meeting is 1/252 ~ 0.4% For an nxn grid, the probability is the inverse of the binomial expansion. So, with n starting at n+1, it ends up being [(n+1)!]^2/[2(n+1)]! As n goes to infinity, prob= 0.

[@davidb5205]

Ah! I see my mistake. Oh well, I'm glad I got as far as I did. I really enjoyed this problem. MORE problems like this please and less of those Facebook viral ones!

[@Clopma]

Answer is love

[@user-zj9rr6yc4u]

The distance between the corners is ten steps, each step brings them one closer to the other and one further from theirs, the only time they could meet is at step 5 where both have the same distance (which is the points on the diagonal). Step order is irrelevant which cuts down quite a bit on the possibilities. The probabilities differ but are symmetrical for the six meeting points with the one at the corners being less likely. For the 5x5 working it out should be relatively easy and the general case sounds like I would have to write too much down so I will just continue watching.

[@vforventure6037]

Hey Price! The total number of ways for an n*n grid is NOT 4^n. In these 4^n ways you are including ways in which A, B can shoot right out of the grid (For example, A going 2n steps straight without changing direction). I figured out an alternate solution to the problem.. It goes something like this... First for A, consider a vertical movement a 1 and a horizontal movement a 0. So in order to reach the opposite corner A must have a binary sequence of five 1s and five 0s. There are 10C5 ways of doing this.. Secondly for B, similarly for B a vertical movement is represented by a 1 and a horizontal movement by 0. It also has 10C5 ways of reaching the opposite corner. Now the meeting, when A and B meet, we fill up the same box(of the binary sequence simultaneously). For them to meet here there must be a total of five 1s and five 0s in the already written parts of the binary numbers. This because when they meet A let's say has gone up x spaces, then B has had to move down 5-x spaces. So together they have covered 5 vertical steps. Same for the lateral movement. This can only happen at the fifth box of the binary numbers.. And this can be achieved in 10C5 ways (filling up five spaces with 1s,the rest with 0s). So the total number of ways they can meet is 10C5. The required probability is 1/10C5. Generalizing for n*n grids, the required probability is 1/2nCn.

[@jjrock8384]

Vfor Venture they only have to consider the movements up to the meeting points

[@hrs7305]

I know its outdated, but imma comment anyway, the question clearly states that Alice and Bob reach the opposite corners at the end, so # of ways alice and bob together complete their walk is (2n choose n)^2 and NOT 4^n

[@ljfaag]

11:31 That might be an idea for Matt Parker for next Pi day :P

[@patrickwienhoft7987]

Pretty easy, but still interesting. Didn't think of Sterling approximation to until you mentioned it. From the thumbnail I already wondered how Pi would come in here ^^

[@CarrotCakeMake]

Two people meeting on an n by n grid is equivalent to 1 person passing by the center point on a 2n by 2n grid (this is just combining both paths by vector summation). So the question is equivalent to "what is the probability a binary sequences of length 2n has exactly n values on". Which is exactly (2n choose n) divided by (2^(2n)). The numerator is larger than the denominator for n=1 and the numerator grows at a rate of a factor of 4 - 2/(n+1) while the denominator grows at a rate of a factor of 4, so the ratio goes to 0.

[@nikolaytsvetkov4661]

Nice! I like it. What is the solution for a cube?

[@nikolaytsvetkov4661]

You are correct, I got it quickly as well. There is no way to meet at the intersection point for a cube but... Technically you can meet in the middle of the corridor or tunnel, right?

[@FrancescoDebortoli]

They could eventually meet in a cube with even side lenght. E.g. they start in (0,0,0) and (2,2,2) and they can meet in (1, 1, 1)

[@FrancescoDebortoli]

Yep, sorry. I didn't understand you were talking about the meeting points. By the way I proved that with a cube with odd side lenght (5x5x5) there are no meeting points.

[@nikolaytsvetkov4661]

Hm. why 7? I got only 3: (2.0.1); (1.1.1); (0.2.1)

[@FrancescoDebortoli]

Also 0, 1, 2 1, 0, 2 1, 2, 0 2, 1, 0

[@trueriver1950]

Note the Q is ambiguous in two ways. Does each walker always move closer to the destination and complete their walk in exactly 10 steps? Or do they move at random therefore taking 10 or more steps to arrive? A 5x5 grid could have 5 lines x 5 lines or 6 lines x 6 lines. A chess board is usually described as 8×8, counting the squares A Go board is usually described as 19x19 counting the lines because that's where the action is (go is played on the intersections of the lines) I suggest that as these walkers are moving along lines from intersection to intersection, it would be more natural to use the Go method and count the lines

[@jskrabac]

The number of total paths is incorrect. It is not 2^n, since the original question as posed requires A ends at point B. This limits the number of paths to N choose N/2. Unless you just require that 50% of the time when either is at an opposing edge they just "skip" a step and stay in place. It's not very clear.

[@numcrun]

I'm surprised if pi doesn't show up.

[@davidaustin2172]

As they move 1 side of each square in 1 second, they can both easily go from a to b in 10 seconds. There is no mention of any obstruction. So, they can both see each other. In my opinion, the probability is they would se each other, think, stuff this grid, take a short cut and meet in the middle in about 3 seconds. That is of course if they’re not doing social distancing.

[@slavikvsvega]

The total number of ways to walk the grid is 2n choose n, not 2^n. So the answer is 1/(2n choose n).

[@tormod1957]

Vertical direction for each person = 1, Horizontal = 0. After N steps A + B = N (Means they cross). This gives a binomial distribution easily solvable

[@jacoboribilik3253]

What took me the longest is to realise the probability for the nxn grid is actually closely related to Legendre's Gamma function multiplication formula (I had been juggling with the factorial limit for quite some time). After that, the the involvement of pi was immediate.

[@pableraspfgpfg468]

Finally such a hard problem to think quite a bit to solve it! Thanks!

[@alin_ilies]

I have some problems that are clouse to this one: 1. what if in the square are 4 person, in each corner? What is the probability that 2, 3 or 4 meet? 2. What if instead of an square we have an hexagon with 2 or 6 preson. What is the probability that 2, 3, 4, 5,6 meet? 3. What if we have generalized polygon with m sides?

[@thunderbirdizations]

I’m a math major and figured this out pretty easy. I don’t say this to brag, but I don’t understand why this is counterintuitive? I can understand why it might be hard, but counterintuitive??

[@michaeltownsend9725]

Holy cow, I used the wrong maths and even the wrong logic and I got a chance of 1/4. And sure enough the answer given was super close to that. I don't know whether to feel shame or pride.

[@micke_mango]

Weird setup. Why consider only two options in a 4-option situation? If you're memory-less, it ought to be a 1/4 choice, if you have memory, it ought to be a 1/3 choice. Especially confusing since the term 'random walker' is used later in the problem. This is clearly not a general random walk, but one with specific conditions. It also feels weird and unnecessary to introduce time into this problem...

[@virginiofratianni1760]

The limiting probability when n goes to infinity is 0, right?

[@oterodactilo]

yes. in an infinite grid it would take them an infinite time to run into each other at a point that is at an infinite distance from their starting points. it makes sense that the probability of such event is infinitely low, or zero...so many infinities in that sentence ;)

[@virginiofratianni1760]

Daniel Otero yes, it makes sense! :)

[@Adityarm.08]

Daniel Otero NO! zero probability does not have anything to do with time(steps) taken to run into each other. It signifies that the count of (even infinitely long) paths that meet becomes negligible compared to the total number of paths as grid grows without bound.

[@trueriver1950]

You would think so; and that turns out to be true: but surprisingly it approaches zero in a way that is rooted in pi ;)

[@hangukhiphop]

I think this solution is only correct if you assume Alice and Bob stop after n steps. If they continue all the way to their opposite corners, which requires 2n steps, you have to take into account the number of ways to complete each path. That would require raising each term to the 4th power instead of the 2nd. Also, the total number of paths for the entire grid would become the square of 2n choose n.

[@1323545624]

i was thinking that as well... if you take all complete paths into consideration, there should be (1+25^2+100^2)*2 ways two complete paths may cross at the diagonal. if there are e.g. 5 ways to get to a point, there are 5 ways to leave again, same for the other person. The total number of combinations of 2 complete paths is, as you pointed out, 252^2. This would lead to a probability of about 0.3347! Am I mistaken?

[@1323545624]

I made a simulation in R and got the same answer, 0.3347, when the persons are choosing complete paths. At the start of the video he says though, that they choose directions with 50% probability until they reach the opposite point. thats impossible because in cases where they hit the edges of the box before reaching the opposite side, they cant choose directions anymore. they can only do that until they hit an edge. if he meant to say that, his answer is correct.

[@ShafizanRashid]

@@1323545624 I got 33.5% as well. The solution in the video seems to only account of half the journeys of both Alice and Bob. But if we account for the full journeys of Alice and Bob, the probability becomes 33.5%. I'm confused as to why we don't have to account for the full journeys. You said you made a simulation and got 33.47%. Does this mean the video's answer is wrong?

[@TheZenytram]

Pi i the answer for every thing.

[@franzschubert4480]

Tau is still better

[@user-uu5fc5ek7o]

Franz Schubert #teamtau

[@DerToasti]

when in doubt, pi it out.

[@bg6b7bft]

I got a smidge under 30% They can only meet at the intersections that run diagonally from the other corners. There's 1 way to get to the far corners, 5 ways to get to the next closest intersection, and 10 ways to get to the center intersections. Since they both have to reach the same intersection, you square the odds of them meeting at any given one. (1^2 + 5^2 + 10^2 + 10^2 + 5^2 + 1^2) / 32^2 = 29.7% The pattern 1 5 10 10 5 1 might help us figure out a general case... On a 4x4 grid I got the pattern 1 4 8 4 1 On a 6x6 grid I got 1 6 25 64 25 6 1 Let N be the grid size; there will be N+1 corners. If N is odd it looks a pattern of (N+1)^0 , (N)^1 , (N-1)^2 , (N-2)^3 , ..., (N- (N+1)/2) , (N- (N+1)/2) , ...,(N-2)^3, (N-1)^2 , (N)^1 , (N+1)^0 if N is even we need round (N+1)/2 down, and add a single (N-N/2)/2^N in the middle. Square each of these, add them together, and divine by (2^N)^2 to get the odds.

[@bg6b7bft]

so my logic was sound, but I screwed up the arithmetic. Story of my life, right there. And I have no idea if my general case is right, because Presh went in a totally different direction with the notation.

[@JesseLH88]

I have not watched the solution yet. Have not worked it out, but my *guess* is it's the squared sum of Pascal's triangle. The two people can only meet along the diagonal perpendicular to their start points. So the chance of them meeting is the probability that both use the same point along this diagonal. The chance of using the kth point along the diagonal is (n choose k)/n^2 where n is the number of points in the diagonal. So the solution is the squared sum of these. Sorry, hard to explain math in a youtube comment.

[@Paolo_De_Leva]

You can give a more complete explanation by pointing out that the number of possible 5-step paths is 1+5+10+10+5+1 = 32. After that, you can explain that this is equivalent to 2^k, where k=5 is the number of steps (i.e., 2^5 = 32), which is needed to generalize for different values of k.

[@Paolo_De_Leva]

You can also compute the probability to meet at each of the six "common points". The sum of these probabilities is Pr(meet) = (1/32)^2+(5/32)^2+(10/32)^2+(10/32)^2+(5/32)^2 + (1/32)^2 = 24.6%.

[@jamirimaj6880]

I'm more and more convinced that pi is not just a circular property, it has other properties that we still don't know

[@blub232324]

I came to the same result. But then I wondered, if we shouldn't include the rest of the path as well (after they met). If so, each probability would get squared again, since both walkers could go the same number of paths after the meeting point as before. ANd if we want to find the number of paths with meetings this would be the right approach. And the resulting ratio would be ~33.5% for n=5.

[@ShafizanRashid]

I got 33.5% as well. The solution in the video seems to only account of half the paths of both Alice and Bob. But if we account for the full paths of Alice and Bob, the probability becomes 33.5%. The answer on the webs is 24.6% as in the video. I'm confused as to why we don't have to account for the full paths.

[@francoism2232]

I try my solution: The meeting can only occur at the half of the way, which is somewhere on a diagonal (not the A-B diagonal but the other one). In the case of a 5x5 grid, the length of the grid in squares is 5, but measured in "intersection points" it is 6. That is the important number. At half of the way from A to B or from B to A, the walkers will both be at a distance of 5 steps from their start position (ie A or B), thus on the diagonal. In this case (5x5 grid), the length of the diagonal is 6 points. --> The probability question can be changed as: What is the probability that the second traveller be on the same point of the diagonal than the first one, when both are at the half of their way to the opposite corner ? The probabilities are not equivalent for each point on the diagonal. With a 5x5 grid (thus 6 points), the probabilities for each point of the diagonal, from one corner to the other one are (assume di are the points of the diagonal) : d1: 1/32 d2: 5/32 d3: 10/32 d4: 10/32 d5: 5/32 d6: 1/32 --> So, in this case, the probability for both walkers to be on the same point is: probability that A is on d1 and B is on d1 + probability that A is on d2 and B is on d2 + ... + probability that A is on d6 and B is on d6 = 1/32 * 1/32 + 5/32 * 5/32 + ... ======> I found a probability of 24.6%

[@Minecraftster148790]

A harder version of this would be if they could go in any direction but not repeat arcs. I can't be bothered to that, but it is interesting to think about

[@Sapphire04]

Another general method for finding out the probility of two random walkers meet is what we just did. For any n × n square, there is a total of (1 + n + ... + n + 1) ways for each person to reach the common meeting points. So, as we learnt, the number of ways that two random walkers can meet at a common meeting point is the square of the ways *one* can get there. So, there are a total of (1 + n^2 + ... + n^2 + 1) or (2 + 2n^2 + ...) ways for two random walkers meet in the common meeting points. And since there are 2 choices a random walker can make, there are a total of 2^n ways for a random walker to walk, and a combined 4^n ways for two random walkers to walk. So, in general, there is a 2 + 2n^2 + ... ------------------- × 100 4^n percent chance that two random walkers will meet in a n × n grid. And yes, that value is getting closer and closer to pi. Note that the "..." are values that cannot be expressed using algebra. P.S. Wow, there are just so many approximations of Pi!

[@Al.2]

To get from point A to a point on the diagonal of "height" k the walker has to choose to go up exactly k-times out of n - that simplifies the argument that there are indeed n choose k ways to get there.

[@kamoroso94]

Two thumbs up for this video!

[@mortkebab2849]

Analysis-wise I got as far as seeing that the collision points were all on the diagonal. Lesson learned is that if I had counted the possible paths to each point on a small (3x3, say) grid, then I would have seen Pascal's Triangle, at least.

[@MalevolentDivinity]

Divided by infinity. So that means it approaches zero?

[@JianJiaHe]

How about 3-dimensional grids? What is the probability of meeting? And what value does the probability approach to? How about 4th dimension, and so on?

[@fishcanroll0]

i divided square diagonally which neither of paths can go trough and took a avg path of up right up right and so on (it takes average game which is perfect for finding estimate chances) chances of it going further or closer to diagonal is the same so overall answer is half of chance to go off the line which is 50% so final answer is 25%

[@lucianosalvetti5852]

Shouldn't the limiting probability as n goes to infinity be (2/pi)^1/2? You can expand the binomial coefficient (2n choose n) to (2n)!/(2n-n)!n! = (2n)!/(n!)^2 and prove that the probability for an n x n grid P(n) is also equal to (1x3x5x...x(2n-1))/(2x4x6x...x(2n)) and the limit of this expresion as n goes to infinity is (2/pi)^1/2 . This is true because if you take the square of the expresion above you get the Wallis Product! (but inverted). So, the limit of P(n) when n goes to infinity squared is equal to 2/pi (the wallis formula inverted). That's my answer without using approximations

[@jiaming5269]

Where on earth did u find (1x3x5..(2n-1))/(2x4x6..2n)??

[@lucianosalvetti5852]

JiaMing Lim P(n)= (2n choose n)/4^n --> this could be written as P(n)= (2n)!/(n!xn!x4^n) by the definition of binomial coefficients. But 4^n=(2^2)^n=2^(2n)=2^n x 2^n, so P(n)= (2n)!/(2^n x n! x 2^n x n!). (2n)! is the product of all positive integers up to 2n, and 2^n x n! is the product of all positive even numbers up to 2n (i.e. 2x4x6x...x2n). So, all even numbers of numerator cancels out with this whole expression (2^n x n!) and you get the product of odd numbers on the numerator up to 2n-1 and the other expression (2^n x n!) on the denominator, which is the product of even integers up to 2n (as I stated before). Then you get P(n)= ((1x3x5x...(2n-1))/(2x4x6...2n). If you still don't believe me prove it by induction

[@recessiv3]

It is not actually always 50%, if either of them hit the edge, the probability suddenly drops to 0 for one, and 100 for the other

[@TheMofRider2]

Even in an "straight" easy world, where sin and cos (if ever needed) are either 0 or |1| there can appear pi. God damn it...

[@shikhanshu]

loved the problem and your explanation!

[@kokainum]

Yup. Got it. It was nice since it was using some discrete mathematics and analysis when it came to Stirling. I wonder how bad approximation it is. There are 2 types of error. First it The error cause by the fact that size of the grid is finite and second one is that we only have estimator of probability. However we know that variance of this estimator is bounded by 1/4 (and 1/4 is independent of n) so increasing n (the grid) doesn't affect our estimation too much (we can set number of simulation without thinking about n). So the main problem should be that Stirling is converging too slow. Is my reasoning right?

[@ramyelbehery9264]

What will be the solution for three and four dimensional grid? I use this approach to build up topological structure and it will be great if you give the solution for the three and four dimensional grids

[@jorgschimmer8213]

No. I didn't figure that out. But I ca fix your car. 😆

[@Daniel-ty9ei]

Jörg Schimmer lol

[@garychap8384]

Alice and Bob cannot occupy the same point in space and time ... if they could, they'd become a new and somewhat short-lived entity called perhaps Bolice or Aliob. If there's even a remote chance that, during their walk, they might end up occupying the same space at the same time ... then they'd be better off staying at home. Thank goodness it doesn't happen in real life .... oh shit ... wait .... ... is that why all the "please keep left" signs ? 8O

[@jamesalexander7540]

No, I did not figure this out. But then again, I have never studied statistics, and have very little grasp of what you were saying.

[@marcolo3489]

Answer will be different if given A eventually will get to B and B will get to A

[@emanonmax]

Well if you know binomial distribution this really becomes a really reasonable way to estimate pi.

[@yanivnevechen]

6:00 " for each step, each walker has 2 choices." This is an inaccurate statement! What if Walker A gets to the upper left corner? Then he only has *one* way to go towards B's origin, and that is right all the way …

[@ChronoQuote]

Only the _k_ steps up to the diagonal line are being considered, which all contain two possible proceeding steps.

[@yanivnevechen]

True, which was not mentioned, I think, in this cumbersome solution.

[@SomeRandomFellow]

8:28 *(2^n)(2^n)=4^n

[@azureabyss538]

Hey , Alex was only supposed to move either upwards or rightwards. He shouldn't be able to move leftwards.

[@57200008]

if you use the Stirling approximation, it will only work for very large n, so if you use for n equal five I don't think it will work very fine. :)

[@mangeurdecowan]

Two random walkers will never meet if Rick Grimes is near that grid.

[@AntoshaPushkin]

What is the probability they meet in a Parker square?

[@mangeurdecowan]

it would be close... but not quite. ;-)

[@usurper1091]

A good problem, after a long time

[@marsgal42]

When pi shows up in "random integer" problems I usually start looking for Riemann zeta functions.

[@leif1075]

You didn't actually derive pi..can you do this without having been aware of these Stirlings approximations beforehand? I'm concluding yes just with a bit more work.

[@MrSophus123]

But why did you ask about letting n go to infinity? Was pretty distracting trying to figure that out.

[@jeandupont4252]

What if Alice and Bob can each go up, down, left or right with probability 1/4?

[@chinareds54]

I wonder what the probability is for a 5x6 rectangle (or in general, and n by n+1 rectangle). Now the meeting point has to be halfway in between steps so it's on a line segment rather than an intersection point.

[@austinconner2479]

I worked out the probability of meeting in an nxn board to be the average value of cos^(2n)(x) on [0,2pi]. with this you can at least see the probability goes to zero. I did not work out the asymptotic expression involving pi :)

[@jakolu]

Initial problem statement: It is not made clear what happens when an edge of the 5x5 grid is reached. Does the probability of an impossible direction become zero?

[@konraddapper7764]

There is als a simpler solution: Because this problem is isomophic to flipping a coin 2n times and observing the same number of heads and tails. This is can be seen by introducing Two distinct "measures" for the distance between aliice and bob M1 = x + y M2 = x - y Here x=xA-xB and y=yA-yB Alice and bob meat if and only if both distance "measures" are simultaneously equal to zero In the isomophic coin toss Imagen that alice and bob both flip coins instead of walking, with head corresponding to a horizontal step and tail to a vertical one In this case M1 = 2n- the number of coin flips and M2 =total number of heads - total number of tails It should be noted that the both meausres dont discriminate between alices and bobs coin tosses. This means that we don't have to distinguish between them anny more Now M1 = 0 if an only if we had 2n con tosses And M2 = 0 if and only if the total number od heads is equal to the total number of tails This completeds the isomphisem The solution is now trivial (2^(2n)*n!^2)/((2n!))

[@shieldon530]

6:20 for two walkers the total number of choices after 5 steps should be 2^5 plus 2^5 right? which becomes 2^5 times 2 or 2^6. because it's just adding the total number of choices, nowhere in that should multiplication be the used operation

[@penguin1023]

There are 2^5 paths for the first walker, and for each of those 2^5 paths there are 2^5 paths that the second walker can take. Therefore, the total number of outcomes is (2^5)(2^5), not (2^5)+(2^5). In general, a given outcome can be represented by an ordered pair (a,b) where a is the path the first walker took and b is the path the second walker took. Let A be a set of all possible paths the first walker can take. Let B be the set of all paths that the second walker can take. Then the set of all ordered pairs (a,b) is the cartesian product of A and B, AxB, and |AxB| = |A|*|B|, where | | represents the number of elements in a set. For example, if you are making pizza and you have three types of toppings and two types of cheese, there are 3*2=6 possible types of pizza you can make.

[@TimJSwan]

Man, I let myself off the hook too easily. I should have figured it out.

[@MKD1101]

8:34 shouldn't it be n-k instead of n in second term?

[@quinnencrawford9707]

imma try finding out when they have a 100% chance of meeting 1 = 1/(sqrt(pi(n))) 1 = sqrt(pi(n)) Assuming the grid has positive dimensions, 1 = pi(n) 1/pi = n its tha reciprocal of pi

[@johnschmidt1262]

Wouldn't you meet after n-1 steps on an n x n grid? So 5 steps a 6 x 6 grid? Is he counting initial start as first move?

[@AugustoCesardeFoggi]

wouldn't the ways to meet in an nxn grid be (2n,n) divided by the repetitions? If you create a group of n people out of 2n people but you only care if they are man or woman you will have a lot of repetitions since the people can swap places with others from the same gender

[@tomriddle2257]

And now the same problem with a change: Intersection of paths.

[@Engelst]

what if there were a person starting in each of the 4 corners.? What then would be the probabilty that 2 of them meet each other. What about 3 of them? And whats the probability that they all meet each other? And finally what is the probability that they meet up 2 and 2?

[@DaKnightsofawesome]

why always alice and bob?

[@RanEncounter]

Chandler Gloyd Why not?

[@altres16]

Chandler Gloyd A and B

[@stevethecatcouch6532]

Because if he used Alexandra and Boris the comment section would be all about his his ties to Russia.

[@pierreabbat6157]

The problem as stated is inconsistent. If Alice starts at point A, and goes up with probability 1/2 and right with probability the other 1/2, the probability that she will hit point B is only 252/1024. The rest of the time, she will walk off the square. If Alice and Bob each pick randomly one of the 252 paths from A to B, the probability that they meet is 0.334656.

[@ShafizanRashid]

I got 33.5% as well. The solution in the video seems to only account of half the paths of both Alice and Bob. But if we account for the full paths of Alice and Bob, the probability becomes 33.5%. The answer on the webs is 24.6% as in the video. I'm confused as to why we don't have to account for the full paths.

[@jeffreycanfield1939]

Auto Captions in Beginning: "Hey this is Pressure Locker"

[@jerwen9]

You know that multiplying 2 exponents is going to be exponent + exponent, right?

[@angelhelp]

I see that others are not having difficulties viewing the video past the 15-second mark. I've tried 9 different times today. It simply won't load.

[@lori2364]

Where does 125 come from. It's not 2/3 of 200 I don't see why it'd make sense here.

[@shinytan]

In grid 5x5 Number Alloted to grid as number ways to reach that particular point on grid midway point or cross way point. Why we put 1O rather then 15 cause their is 3 total ways to reach particular point from A and B respective corner? Please explain

[@vj_henke]

Dear Presh, I have a question concerning the way the problem is stated: At the beginning you stated that there is a 50% chance of either going up/right for Alice and down/left for Bob. This works until, let's say, Alice meets the upper boundary forcing her to only move right or the right-most boundary forcing her to only move up. Under the circumstance they ALWAYS land on their respective starting point, Alice on B abnd Bob on A, its a random walk of the kind (2n over n). You looked at the paths until up to n steps, summing to a total of 2^n possible paths, ignoring the rest of the path possibilities. You may be right, depending on the understanding of "Random Walk". Using the approach presented in your video, considering the entire path branching A→B/B→A, would lead to the sum of (n over k)^4/(2n over n)^2 for all integer k in [0;n], which is just messy written out. (trust me) Is there an issue in the problem statement ? Is my approach correct, your's or maybe a different one ? Is this dependent on the meaning of "Random Walk" ? Thanks a lot for your consideration, L. H., Germany

[@MR_Foffe]

I know very well this is incredibly outdated, but I'll just type the answer if anybody else stumbles around the comments looking for the answer, or if you see this, it might confuse you, which makes me happy. If any of the two go in one direction by chance until they reach the corner and are forced to move the other direction, they've reached the diagonal in which they have any chance of meeting. The next move, they'll have moved on past this diagonal and won't be able to meet each other anyways, making that circumstance moot. Any movements after the n'th move is moot, as explained in the video, as they'll have passed each other having no way of going back.

[@Vextrove]

Quantum problem, very nice

[@michellauzon4640]

the first part was quite easy, but i am very please with the generalization.

[@safrprojects]

Well hang on, it's not 50% anymore once you hit a far wall