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

[@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???

[@rohanchopra1539]

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

[@colgatelampinen2501]

Not much stuffed, those are related

[@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

[@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!

[@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 :)

[@pianfensi]

error at 8:25 its to the power of n

[@thevikckick]

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

[@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...

[@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.

[@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!

[@pableraspfgpfg468]

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

[@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.

[@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.

[@Clopma]

Answer is love

[@ComradeChams]

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

[@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

[@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.

[@MKD1101]

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

[@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...

[@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).

[@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

[@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

[@DavidIngerman]

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

[@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.

[@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.

[@shikhanshu]

loved the problem and your explanation!

[@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

[@kamoroso94]

Two thumbs up for this video!

[@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.

[@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.

[@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

[@ljfaag]

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

[@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.

[@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.

[@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!

[@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 ;)

[@SomeRandomFellow]

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

[@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?

[@usurper1091]

A good problem, after a long time

[@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%.

[@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 ^^

[@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.

[@MalevolentDivinity]

Divided by infinity. So that means it approaches zero?

[@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.

[@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.

[@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?

[@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??

[@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%

[@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.

[@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

[@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?

[@jeandupont4252]

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

[@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.

[@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. ;-)

[@laugernberg4817]

the formula at 9:39 is sometimes called Vandermonde's Identity if anyone wondered :) I solved it by expanding the product of the binomial coefficient, and ending up with this product, (here printed out from "below:"): (1/2)* 3/4* 5/6* 7/8* 9/10 * … which you can show goes to zero: (Show that log of the product diverges towards -inf, (it transforms into a telescoping SUM), and therefore that the product itself must go towards 0, (by continuity of log/exponential function)). This gives a complete proof that the probability goes towards zero without drawing the un-explained asymptote out of the hat :). If you want the probability for n x n grid, stop the above product at … n/n+1, or use (2n)!/((n!)^2*4^n). Great vid!

[@Vextrove]

Quantum problem, very nice

[@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?

[@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%

[@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

[@numcrun]

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

[@jorgschimmer8213]

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

[@Daniel-ty9ei]

Jörg Schimmer lol

[@schiz2002]

I am confused. The problem say 50% chance of going up or going right. But if you are at the top left corner you can only go right. So 100% chance of going right. What am I missing?

[@MrSophus123]

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

[@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

[@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

[@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

[@asr2009]

presh: RU and UR are the same. rubik's cubers: disagree

[@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.

[@danielettedgui148]

Brilliant. Thank you.

[@emanonmax]

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

[@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!))

[@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?

[@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?

[@drazse1995]

What if they meet between two crossroads (on a road they are taking to opposite directions)?

[@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

[@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?

[@marcolo3489]

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

[@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.

[@klixto8686]

Fantastic!

[@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.

[@jeffreycanfield1939]

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

[@lori2364]

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

[@dustinbachstein]

Very nice!

[@SomebodyLikeXeo]

Could anyone help me with this? So, it's converging but to what? Is it converging to inf, 1, 0, e, -inf?

[@banuteja4676]

please post tough ones like this, dont post school problems.

[@artix2468]

Nice, i got this one

[@paulruwe6251]

nice vid

[@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...

[@dushyanthabandarapalipana5492]

Thank you!

[@TimJSwan]

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

[@marsgal42]

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

[@azureabyss538]

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