For non-coders, you can replicate this game on a much smaller scale using playing cards. Separate the deck into 4 suits and remove the Kings to keep the numbers even. Spades = Prisoners Diamonds = Slips of paper Clubs = Boxes Hearts = Prisoner Choices (when simulating random chance)
You ad on toms videos is very clever thanks for introducing me to your channel i know you will grow and surpass 1 mil in no time :) so much effort and love put in to your videos and it’s obvious 😊 keep it up
The Prisoners problem comes down to finding out whether there is a loop that is longer than half the population size (as mentioned at 8:25 in video). If there is, then some prisoners will not find their own number (failure), if there isn't, then the prisoners are guaranteed to all find their own number (success). The main idea is that you do not need to generate the numbers in advance to determine the loops, you can generate them on the fly. Let's take the 10 prisoners as an example, and examine how a loop is determined. All numbers are random, so you can just as well start with prisoner 1. He first opens the box with number 1, with a chance of 1/10 to get 1. If that result is not 1, then he needs to open the box with that number. But note that it does not really matter which specific number was in box 1, what is important is that the chance for the next box to contain 1 is 1/9. To test that, you just need to generate a random number from 1-9. The prisoner opens the next box, with a chance of 1/9 to get 1. If it is not 1, then the next box has chance 1/8 to contain 1, etc. Suppose the prisoner draws 1 at this third occasion, then you know there is a loop of size 3. But you don't know anything yet about the remaining 7 numbers, so you repeat the process searching for the next loop, starting with 7 numbers this time. If after finding a loop, fewer than 5 boxes remain, you are certain the loops in there are all going to be shorter than 5, and the test succeeds. As soon as a loop gets longer than 5, the test fails. The key insight is that it does not really matter which specific number comes up, it just matter what the probability is that it is the starting number of the loop. And that probability can be used to generate the random numbers on the fly. I ran a program over night with 10,000 tests with 1 billion prisoners, and the statistics came pretty close to the number mentioned in the video.
I wrote some python code that tested 'random' and 'follow your number' algorithms for 100 prisoners. My results agreed with Verulamium. I also wrote code that calculated the length of the loops and this worked out OK. I find this 'thought experiment' absolutely amazing.
If you're already accepting to take the leap to analysing just the length of the circuit. Just use something like the code below. The video is doing the same thing, but a lot more inefficient. n = 10**9 H = 0 for k in range(int(n/2 + 1), n+1): H = H + 1/k print(1 - H)
You know what's hilarious. I rewatched Veritasium's video on it just a short while ago. I got the recommended of this video, I opened in a new tab and put it to the side. I went and coded a solution to test it (and it is right). At 0:37 I see some code there and the single_prisoner_attempt and run_simulation functions are functionally the same as my SendPrisoner(...) and FullRun(...) methods I made. Like exactly the same just in C#;
This is the first time youtube has put you in my recs. I loved Veritassium’s video. I’ve been thinking about it since I watched it a couple days ago (oh, that’s why I got the rec). I thought everything you said was an addition to what I learned from Veritassium. I’ll check out your channel. Subscribed!
It would have been nice if you had put an error bar to the percentage of success since you are doing a statistical sampling and the result can fluctuate around the mean value, where the amplitude of the fluctuations is proportional to the standard value (i.e. the sqrt of the variance) of the sampling. Not only it is standard good practice in statistics when sampling data, but also we would have seen that the theoretical value stands inside the confidence interval. Otherwise, great video.
Fortunately, since this is a Bernoulli experiment (only two outcomes), if you have an estimate p of the success probability, then your estimate of the variance is p(1-p), so the standard error is sqrt(p(1-p)/n). For n=1'000'000 (experiments, not prisoners), I get the following standard errors: 0.047848% 0.046339% 0.046144% 0.046142% (To get the error bars I'd have to multiply by 1.96 for a 95% confidence interval.)
If this strategy is done will less prisoners, the odds of success increase. If done with only 2 people, each person just opens the box with their own number on it and there's a 50% chance they both get it right.
@@Ishant875 How is it 25%? If they each open the box with their own number on it, either they both get it right or they both get it wrong, each of which has a 50% chance of happening. There's no other possibility.
@@osiris3791 Because then if the first one succeeds (50%), the second one is guaranteed to succeed (100%). It's 25% if they open randomly and 0% if they're suicidal and both agree to open the same box. In a way they're using a loop of length 1 and there's a 50% chance no loop of length 2 exists
@@jacobwansleeben3364 The odds is always 50% for each individual prisoner, but the odds of two people both being right is 50% times 50%, which is 25%. The original video said that it approaches 30.7% as the number of prisoners increase, but it never addressed how the numbers would change if decreased to the point where there's essentially no loops.
TH-cam ads sometimes take you to really good content; thank you TH-cam for showing me this ad on vertesium channel videos (well, it was intentional, but I am still happy)
So the trick is they not shuffle the boxes like in a deck of card but switching two of them than repeat, thats why you guaranteed you find your box if you do it long enough So you can't hide the box from it's the original loop. But counting the chances like all outcome has equal chances seems very wrong. I think Switching pairs is different than shuffle. Let's say you do 10K or 20K switching i think it has higher possibility to get to a longer queue. (but i'm not really sure ) So the calculation of 30% is incorrect, Because it is relative to the times of switching. (because it is different from throwing dices or shuffle deck) Please help if i misunderstand
Over the last two weeks or so I ran my own C# version with a billion prisoners. I only ran 10000 rounds. I outputted the running average after each round. Out of those 10k rounds 3072 succeeded while 6928 failed. This gives us a "rough"average of 30.72%. Of course the sample size is still too low. Though the trend seems to be there ^^. Note that filling the array with a billion numbers took about 0.6 seconds each trial. Scrambling the numbers with fisher-yates took between 52 and 56 seconds. The actual check for the longest chain took between 80 and 160 seconds. That gives us an approximate 200 seconds per trial. So roughly 18 trials an hour, about 432 trials a day. Note that I didn't bother to multithread anything ^^. It was just a simple console application that ran in the background over the last two weeks and a few days. I didn't wanted to bring my PC down. I barely even noticed it running. A major issue here is that we can not really get a good ranomization of the numbers. PRNGs work decently for smaller sets of numbers. However the closer you get to the internal state of the PRNG, the more "patterns" will emerge. Since every trial is essentially completely independent from each other, we could simply remember the success / fail / total counts and combine the results of several equal tests. So I got 3072 success over 10k. We get a better result if someone does, say 1k and he gets something like 307 successes, we can simply add up the success counts and the total runs. Though keep in mind that the program occupies 4GB of ram since we need an array with 1 billion int32 values. When you want to multithread the whole thing, the best approach would be to have each thread / core doing its own trial. Though that means the memory would be multiplied by the number of threads / cores. So running 4 thread means 16GB of ram and you don't want your OS to start swapping the ram, so you really need a lot of ram. I do have 32GB, but I still want to use my PC :)
Well, 16Gb out of 32Gb is not that bad. And it would increase output 4 times. Definitely worth it IMHO. Also you don't use your computer all the time, so you may run even more consuming version of a program while you sleep/going for a walk/doing something else. Damn, should I try it myself? :) Kinda want to program something in C and this looks interesting to try... 🤔
You don't need to store the numbers. Remember that we just need to know how long the loops are. Exactly which numbers are on the loop is not really relevant. So you could just assume the first door has number 1, and draw random numbers until 1 comes up, reducing the maximum number to draw from with 1 for each draw. The number of draws you need before 1 comes up is the loop length. Once that loop length is larger than half the population size, the test fails. If the loop is smaller than half the population, and there is more than half the population left to draw from, continue drawing numbers to establish the next loop length. When there is less than half left, the remaining loops must all be smaller and the test succeeds.
@@renedekker9806 I don't think that this would even be remotely similar to what this problem was about. You just play with statistical propabilities and assume that give you the same outcome? That almost assumes you already know the exact statistical value / limit we wanted to figure out. I'm not that good with statistics, however what you propose would give you a total statistical probabilty of 50% of drawing the 1 after drawing half the numbers in the way you proposed. To get the overall statistical probability that at least one of x independent event happens can be calculated by the product of the inverse of the individual probabilities. So our goal is essentially how likely it is to draw any other number. So for 10 numbers it would becomes (9/10) * (8/9) * (7/8) * (6/7) * (5/6) == 0.5 Of course we want the inverse of that (1.0-0.5) but in case of 0.5 it's again 0.5 or 50%. That would be the statistical mean. The main issue with this problem is that every number can only be drawn once since every number is always in a particular loop. When you just draw random numbers between 0 and n, you will draw the same numbers multiple times. So I don't think your setup would actually represent the problem at all. I'm sure this problem can actually be solved by pure stochastic analysis to actually directly calculate the expected limit at a certain sample size. Though as I said I'm not that good with probabilities and I kinda hate stochastic as it's used way too often to justify things in this world :) It has its place and is very useful in many situations, but real world problems can not always be reduced to a single probability value as the actual weighting of values plays an important factor. Anyways, I got sidetracked ^^. Unless you can show that your approach holds up to the values we get from the other methods, I don't think that will work.
@@Bunny99s _"statistical probabilty of 50% of drawing the 1 after drawing half the numbers"_ - I think you misunderstood what I proposed. The Prisoners problem comes down to finding out whether there is a loop that is longer than half the population size (as mentioned at 8:25 in video). If there is, then some prisoners will not find their own number (failure), if there isn't, then the prisoners are guaranteed to all find their own number (success). The main idea is that you do not need to generate the numbers in advance to determine the loops, you can generate them on the fly. Let's take the 10 prisoners as an example, and examine how a loop is determined. All numbers are random, so you can just as well start with prisoner 1. He first opens the box with number 1, with a chance of 1/10 to get 1. If that result is not 1, then he needs to open the box with that number. But note that it does not really matter which specific number was in box 1, what is important is that the chance for the next box to contain 1 is 1/9. To test that, you just need to generate a random number from 1-9. The prisoner opens the next box, with a chance of 1/9 to get 1. If it is not 1, then the next box has chance 1/8 to contain 1, etc. Suppose the prisoner draws 1 at this third occasion, then you know there is a loop of size 3. But you don't know anything yet about the remaining 7 numbers, so you repeat the process searching for the next loop, starting with 7 numbers this time. If after finding a loop, fewer than 5 boxes remain, you are certain the loops in there are all going to be shorter than 5, and the test succeeds. As soon as a loop gets longer than 5, the test fails. The key insight is that it does not really matter which specific number comes up, it just matter what the probability is that it is the starting number of the loop. And that probability can be used to generate the random numbers on the fly. I ran a program over night with 10,000 tests with 1 billion prisoners, and the statistics came pretty close to the number mentioned in the video.
I think it's useful to provide simulations like this. It helps people who have a hard time believing abstract reasoning. And I know you've been called out on this already, so it may not be worth me mentioning this, but the video title, comments made in the video, and comments you've made in response to people in this comment section seem to suggest you believe that running a bunch of tests is more reliable at finding the truth than rigorous logic. For example, in the video description, you say, "I wrote a simulation with code to prove once and for all whether Veritasium was right or wrong." Veritasium proved in his own video that he was correct. I'm sure plenty of people didn't understand the reasoning, but he _proved_ it. Your simulation, on the other hand, could have been anomalous and not matched with the actual statistic. Unlikely events can happen, so if your simulation hadn't matched with the result Veritasium gave, that wouldn't prove Veritasium wrong. Likewise, just because your simulations were close to the results Veritasium gave doesn't prove Veritasium right. In either case, your experiments could have failed to match with the truth, whereas Veritasium's reasoning based on sound logic _has to._
Perhaps I should use a different word than "prove" - maybe tested or verified. But yes I think running tests is more reliable than thought logic. Would you want to board an airplane that logically should fly but had never been tested?
Just to reiterate this: I think that doing experiments like you does add a lot and helps bring in people who don't necessarily understand the theory (and I also think it's cool to see the number work out in practice, even when I know the theoretical result is rock solid). So it's a good video overall! Just a picky point.
@@DataTime27 There are certain circumstances where running tests is more reliable. I admit that. However, in those circumstances, there aren't clear axioms given. Instead, people using the theoretical reasoning have to _choose_ axioms to model the scenario. Those axioms can always be called into question, and I would say that experiments are likely to be more reliable in that setting. In this scenario, however, is entirely theoretical - we are given specific axioms for how the puzzle/game works. The puzzle has to work a certain way, and using how the puzzle works, we can deductively prove this strategy has a success rate of close to 30% (for sufficiently many prisoners). To me, it seems as silly as saying, "Sure, by definition, bachelors are unmarried, but let's _really prove it_ by finding as many bachelors as we can and then determining the proportion which are married. If it's close to 100%, then we can be actually be confident that bachelors are unmarried." Sure, the prisoner puzzle is a lot more complicated, so you could reasonably be concerned that some subtlety in reasoning was missed, especially if you find the reasoning hard to follow. And in that situation, running experiments might give you more confidence that the reasoning didn't miss anything. And I think that's also a very valid reason to make a video like this.
I think we need to take into the account that even if you choose a n-loop, (n>50), the prisoner is gonna go out and random pick the remaining boxes, and there’s a 1/(100-n) chance he choose the right box. Hence the slight difference in probability answer. You can try 4 prisoners, and the difference in answer will be bigger.
So, if I'm understanding what you're saying correctly, you're trying to say that if the prisoner picks a loop that is larger than 50, they'll just pick randomly instead, thereby increasing the chances even more, however, they won't know whether or not the loop is over 50 until they have already exhausted all their chances, and since they can't tell the prisoners coming behind them (and it would be too late by then anyways) Everyone else will still follow the same pattern.
"I think we need to take into the account that even if you choose a n-loop, (n>50), the prisoner is gonna go out and random pick the remaining boxes, and there’s a 1/(100-n) chance he choose the right box." No, you're mistaken. The right box is always the last one in the loop because that's how we defined the loops. If there is a >50 loop then failure is guaranteed.
Unfortunately simulation is not a good example to prove the correctness of a solution. To prove something is wrong, you need ONE and ONLY ONE counter example. Having said that, if you really want to prove the correctness of his theory (analysis, or whatever you want to call it), formal methods is the way to do it and ofc NOT using simulation
@@DataTime27 if it was *FORMALLY VERIFIED*, absolutely! As described by Professor Edsger W. Dijkstra “testing can be used to show the presence of bugs, but never to show their absence”. Look at the Floating Point bug in the intel chip, or the failure of any system in the world… it was tested (and probably heavily tested). However a formally verified design/concept will never fail as the correctness is guaranteed.
@@DataTime27 No, but the title of this video says "prove." Veritasium provided something much closer to a proof than you have here with is a simulation.
Lets try this again. I posted before that running loops is NOT the ideal solution. You can do better and therefore, I believe, this is the real solution to the riddle. I hypothesized that it is better to switch loops. Specifically I applied Benford's law to the 100 boxes. What does this mean? It means the prisoners should switch loops every 3 numbers. The idea is that statistically short loops should occur more often than long loops. 1. The prisoner starts by opening the box with her number. If the prisoner does not find her number by the 3rd attempt; switch loops. That means opening another box instead of following the next box in the current loop. 2. Follow this loop for 3 attempts. if she don't find her number open another random box and follow that loop for 3 attempts. 3. This will allow the prisoner to test 16 three box loops and 1 two box loop to find her number. According to Benford's law 3 box loops should appear 12.5% of the times in a random number sequence. Switching loops allows the prisoner to check 16X for a 3 box loop and 1X for a 2 box loop in the 100 boxes. This has a greater chance of success than running each loop to it's conclusion because a 3 box loop is statistically more probable than longer loops. Meaning Benford's Law saying, it is more likely the prisoner's number will be in a 3 box loop than is is to be in a 51+ box loop. I would like Data Time to create an experiment to demonstrate is this is greater than the 31% chance Veritasium gives. Thank you.
I need you to explain me something please. The goal is to find its own number, not to do the most circuit. In my understanding of your reasoning, indeed you will have more 3 number circuits but those circuits will not end with the prisoner number but rather the number of the box he switched to in the "3 pick" cycle. And we don't need that one, do we ? So here is my question: What is the percentage of chance for a prisoner to get his own number (not just a number of any loop) ?
You posted this nonsense about Benford's law on the other video. You tried to claim the chance of all prisoners succeeding is 70% with your strategy. You were told why Benford's law is not applicable, and why it is not possible for ANY strategy to go past 50%. You have been told that the strategy has been PROVED optimum. Yet here you are again refusing to accept you are wrong.
@@DataTime27 IF that's true then it proves that following a loop to conclusion vs switching loops has no impact on probability of success. And if that's true then the explanation for why the solution works is disproved. Either way, that's a huge reveal.
Nice video Can you do the test differently. Let say you have 100 prisoners. Make them in two groups. One group is larger 67% and other is 33%. Larger group open boxes like in your video. First box is their own number and try to find end of the loop. Second group(33%), they open box with a different number and start from there. Lets say if prisoner has number 6 they open box 9 and try to find the loop. And every prisoner in this group must add 3 to their own number.
I was actually watching the exact veritassium video on the prisoners and i saw the ad of you guys and i was totally mind blown. i mean what are the odds?
I am inclined to guess that Veritasium is right, but perhaps I am mistaken. Veritasium offers an apparently clever procedure, and a sketch of a proof. You may verify his solution by brute force. I would be more impressed by an abstract theoretical (non-brute force) verification.
It's important to have both a mathematical proof and a demonstration (brute force method). If proofs are truly solid, them we can predict what will happen when demonstrations are used. Therefore, demonstrations are another form of verifying mathematical proofs. If you have a mathematical proof that seems sound, but you try to simulate it and it fails - then it means either the simulation was flawed or the proof was flawed.
I still have a big problem which was explained in the Veritesium video. As there can be very small loops (circuits), there has to be a chance of me being on a loop that does not have my number. If it was a 15 box loop, in the your computation, does the prisoner jump and start another loop? And if he does what number does he use? I feel this type of failure wasn't addressed.
No, the loop which includes the box with your number is guaranteed to also contain the paper with your number. That is basically the whole point. Each box links to only one other box, so the at the end of the loop you enter via box X, you will always reach paper X.
That is why you start with number box that is your number. If you are prisoner 13 you will first open box 13 and see that it has number 2 for example. you will go around the loop and the very last one in the loop will be box 46 and it will have 13 in it, thus completing the loop since you started with box 13. So its even better if you have a small loop because you will find your number quickly. The only trouble is loops longer than 51 as mentioned.
Dude, credit is owed to Peter Bro Miltersen who proposed the puzzle en.wikipedia.org/wiki/100_prisoners_problem#cite_ref-gal2003_4-0 (And not to Veritasium. Veritasium was a gracious messenger)
@@DataTime27 YES, they stated you could add some number, say 5, to each box to reorder loops Seems like this method might pit you on a loop that did not include your box.
You ok, one day for one million simulations with 10 prisoners. I run your GO code in 15 seconds and my Rust code in 11 seconds. You probably have similar hardware because you have to deal with After Effects
Although Derek Muller was somewhat informal in his presentation, I believe he properly summarized the steps in a mathematical proof of his result. He was quoting results of other computer scientists and applied mathematicians, and their result is reasonably "established". In this video, you appear to be accepting the following assumption. Setting up a computer simulation (with imperfect randomization at the base of it all) and then running that as a statistical experiment is somehow more reliable to give a final validation of a probability statement than just performing the math and believing that valid work in statistics will give the correct answer. I think simulations are important to help validate, but they are at best another pillar of a proof, though not the central pillar. In other words, this simulation in Go on a PC has given some solid experimental corroboration of the result, but I think it is quite an overstatement to claim you have proven his unproven statement. But maybe I'm being too critical of your good effort.
Is Veritasium wrong? Well, in 99% of cases, yes they are. They often slip in a little "trick" to switch from the correct answer to their own and, unless you spot it, their answer seems legitimate. Take, for example, their "wind powered car" video . . in reality, a car travelling with the wind will accelerate, and the resultant net "wind force" will decrease linearly, e.g. at 20mph, a 20mph tail wind will exert 0 force. They then "proved" their theory using a treadmill which provided a _constant_ wind force, regardless of the speed of the car .. and he made $10,000 from that scam
With one alteration to the plan, you can win even with loops of 51. If you don't find your number on pull 50, you assume the number you last pulled is the box that's holding your number. Giving loops the size of 51 a win.
@@Pestsoutwest At 0-45 of the *Veritasium* video: _"One at a time each prisoner is allowed to _*_OPEN_*_ any 50 of the 100 boxes."_ Now point out where they said you get another chance by picking a 51st box.
@@godfreypigott They can add n value to every boxes in the room, therefore making an impact the same as redistributing the slips inside the boxes, break any loops over than 50 into smaller one.
@@DataTime27 right now i am seeing success of 30.33% I suspect i am incorrectly testing the size of the biggest loop or incorrectly counting the number of members The RNG is not the greatest either.
@@DataTime27 I modified the program to run more last night any by morning it was over 3000. Still about the same though 33.20 something percent. I am investigating whether I am counting the lengths of the loops correctly. I am still gonna blame the RNG though I think.
The problem is interesting, but the presentation is misleading and confusing. It is NOT that prisoners have 31.2% chance to be freed. 31.2% chance is for the map f: Box Labels - -> Prisoner's # to be good, in the sense that all cycle lengths of f
@@DataTime27 Here is the link th-cam.com/video/vIdStMTgNl0/w-d-xo.html They didn't write a program but they do a similarly good job of explaining the riddle
Nice video! If the puzzle is modified such that odd numbered boxes contain only odd numbered slips and even boxes contain only even slips, then no loop would be > 50. Even worst case scenario would be 2 loops of 50 each. Then they would have a 100% chance of winning once they find out the loop strategy. In the current version, they can plan the strategy but still have to depend on luck. In the modified version, P(success) = P(coming up with the right strategy).
The only problem is that if it’s known that only even slips appear in even boxes then each prisoner would just open the 50 boxes that are even or odd depending on the number assigned and you wouldn’t need a loop strategy.
You still didn't prove it, while he did with the ln2 result taking the limit. Good concept haha, "ThEOreTIcaL" stuff, but no way I'm laughing at a joke that states that they have to test experimentally a correct result of a theoretical problem that, again, has been successfully solved using the only way you can prove mathematics, with mathematics
When doing mathematical proofs there's always a chance that you have made a mistake in your proof that no one has yet detected. Actually testing it (if you can) can increase the confidence that the result is correct.
@@seneca983 I would rather it be tested by rigorously going through the proof and looking for errors. The test may give me more confidence that my proof is right, but once the proof is verified we no longer need to keep testing. This is different than in science where we often "prove" things by piling up evidence through multiple experiments. In science it is good to remember that these aren't truly proofs in the mathematical sense, but just overwhelming evidence leading us to conclusions.
@@zackcinq-mars2129 "I would rather it be tested by rigorously going through the proof" Well, you can do both if you want more certainty. Also, this kind of testing approach does have the advantage that it can be quick and easy (depending on the case), so you may be able to catch some errors with little effort, even if this alone isn't enough for a high level of confidence.
You needed to explain why the fraction 1/m of all choices of sequences of n integers are in cycles of length m, when m is > n/2. That can be done simply, clearly. Please fix your video so people don't waste time on an inadequate explanation, one with part of the proof missing. Now I know I can't trust that your videos will prove what they claim to show.
You need to explain where you are getting the fraction 1/m from, if you want your comment to be accepted, as this notation is not used anywhere in the video. You claimed your explanation could be done simply and clearly, yet you made no actual attempt to explain it. Please refrain from making insolent comments, especially if you are not prepared to provide evidence. The video stays.
Oops, I didn't mean insolent! I meant don't just claim that the result in a very special case (the # of boxes in the cycle = the max possible, the total #of boxes) is the same (1/max or 1/# in cycle). You can explain the general case clearly. Not explaining leaves us not understanding.
It's called "science". There is no place for faith or authorities. There is always doubts. For example, did you know that result heavily depends on shuffle algorithm? Veritasium said nothing about how boxes are rearranged. But with your own program you can experiment and get pretty unexpected results sometimes. How do I know? Because I was curious enough to write my own program in C and played with it.
@@1kvolt1978 what shuffle algorithm? The box arrangement was a sample from a theoretical distribution. There's no algorithm involved. That is only relevant when you start simulating it (which does not implement the problem exactly, because then you need to use a pseudo-random number generator)
@@TomasAragorn I don't remember details now, but I do remember that I was doing different reshuffling trying to improve performance and I've got different results. I don't know why, I'm bad at math. But somehow result depends on reshuffling even if it feels like it shoudn't. At least in my program.
@@DataTime27 I think if you wrote it while the video it will be really useful but you actually took a screenshots of your code we didn't know how the code written down and how the simulation really done .. I know you say the approach quickly but no one really know it. at the end you show some numbers of percentages of the probability of winning. But I will prefer if you go deeply in the code it will be fun actually. And dude no offence I really loved the video :P but as I said it will be more fun if you focus in the journey of writing code more.. may be it's easy for you to write a code as you said "simple software" but for me it will be really helpful. thanks a lot for considering my comment ,, this days no channels cares about feedback actually
Thanks! I'm afraid to go too deep into code because I don't want to bore people. I have a link to the code in the description for people who are really into the code
@@DataTime27 I think a mathematical proof is enough to say that it's known. What you're doing can still be meaningful since it can increase the confidence that there isn't a error in the proof. However, it's not necessary for saying the result is known if the proof has been checked thoroughly enough.
suppose that the boxes contained the number *one more* than the box, so that box 1 contains 2, box two contains 3, box 3 contains 4 etc. So *each* prisoner would open their box, then move to the next box, then the next, and *none* of them would find their own box, because it would *always* be the one *before* the first box they opened. The veritasium algorithm fails in this case.
@@DataTime27 At the 7:20 mark, you output the results of the run after EACH run, flooding the terminal with output. You could potentially get faster results w/o printing the results until the very end. All that I/O has a cost.
you have 100 prisoners...your first choice of your own number is always 1 out of 100 just start with your number plus 2 then when you get result add 3 to it if you go over 100 just take away the 100 to get the next box you check .each time you go up to the next prime number...then your chances will be about 50 percent instead of 33 percent.... LOL
I don't see how this would result in 50% chance that they all succeed in finding their number. By adding a different number each time it is no longer a loop. And by not starting with your number, even if it was a loop you aren't garaunteed to be in the loop.
Faust can you give me more info? I have told the ads system to not serve this ad more than once a month to people. How often are you seeing this ad? Are you watching it on the same device each time? I'm worried other people might be having the same problem as you. Thanks
Hmm, I wonder if the asymptote is irrational or not? It probably is, But my sciatica keeps me from looking into it right now. I will when I get a chance. @@DataTime27
@@DataTime27 well I’m not a scientist plus I didn’t actually see all your videos so idk but still everybody makes mistakes even data time. Even the person with the least mistakes has mistakes. When you didn’t make your TH-cam channel you made mistakes no doubt
Got the video in the ad of veritesium's video, I knew he was right. Anyway appreciate your hardwork. Subscribed :)
Thanks!
Same
Yeah man, how this is possible, how we get related ad on a channel 😱
@@sapandream kinda lame I think.
@@sapandream Feature in YT Advertising
For non-coders, you can replicate this game on a much smaller scale using playing cards.
Separate the deck into 4 suits and remove the Kings to keep the numbers even.
Spades = Prisoners
Diamonds = Slips of paper
Clubs = Boxes
Hearts = Prisoner Choices (when simulating random chance)
You ad on toms videos is very clever thanks for introducing me to your channel i know you will grow and surpass 1 mil in no time :) so much effort and love put in to your videos and it’s obvious 😊 keep it up
Thanks! Glad you're with us!
@@DataTime27 heck yeah man! Keep it up, also that ad was very clever iv never seen someone do that before 😄
The Prisoners problem comes down to finding out whether there is a loop that is longer than half the population size (as mentioned at 8:25 in video). If there is, then some prisoners will not find their own number (failure), if there isn't, then the prisoners are guaranteed to all find their own number (success).
The main idea is that you do not need to generate the numbers in advance to determine the loops, you can generate them on the fly. Let's take the 10 prisoners as an example, and examine how a loop is determined. All numbers are random, so you can just as well start with prisoner 1. He first opens the box with number 1, with a chance of 1/10 to get 1. If that result is not 1, then he needs to open the box with that number.
But note that it does not really matter which specific number was in box 1, what is important is that the chance for the next box to contain 1 is 1/9. To test that, you just need to generate a random number from 1-9. The prisoner opens the next box, with a chance of 1/9 to get 1. If it is not 1, then the next box has chance 1/8 to contain 1, etc.
Suppose the prisoner draws 1 at this third occasion, then you know there is a loop of size 3. But you don't know anything yet about the remaining 7 numbers, so you repeat the process searching for the next loop, starting with 7 numbers this time. If after finding a loop, fewer than 5 boxes remain, you are certain the loops in there are all going to be shorter than 5, and the test succeeds. As soon as a loop gets longer than 5, the test fails.
The key insight is that it does not really matter which specific number comes up, it just matter what the probability is that it is the starting number of the loop. And that probability can be used to generate the random numbers on the fly.
I ran a program over night with 10,000 tests with 1 billion prisoners, and the statistics came pretty close to the number mentioned in the video.
I wrote some python code that tested 'random' and 'follow your number' algorithms for 100 prisoners. My results agreed with Verulamium. I also wrote code that calculated the length of the loops and this worked out OK. I find this 'thought experiment' absolutely amazing.
That's amazing thanks! I'm glad everything matches up
Verulamium 💀💀💀
@vollkornkeks9177 what is that?
@@DataTime27 he wrote Verulamium instead of Viritasium
@@vollkornkeks9177 Bro corrected the wrong spelling wrongly. It's Veritasium u stoopid ni
If you're already accepting to take the leap to analysing just the length of the circuit. Just use something like the code below. The video is doing the same thing, but a lot more inefficient.
n = 10**9
H = 0
for k in range(int(n/2 + 1), n+1):
H = H + 1/k
print(1 - H)
Which can easily be shown to be 1 - ln(2) for n goes to infinity.
You know what's hilarious. I rewatched Veritasium's video on it just a short while ago. I got the recommended of this video, I opened in a new tab and put it to the side. I went and coded a solution to test it (and it is right). At 0:37 I see some code there and the single_prisoner_attempt and run_simulation functions are functionally the same as my SendPrisoner(...) and FullRun(...) methods I made. Like exactly the same just in C#;
This is the first time youtube has put you in my recs. I loved Veritassium’s video. I’ve been thinking about it since I watched it a couple days ago (oh, that’s why I got the rec). I thought everything you said was an addition to what I learned from Veritassium. I’ll check out your channel. Subscribed!
Thanks!
It would have been nice if you had put an error bar to the percentage of success since you are doing a statistical sampling and the result can fluctuate around the mean value, where the amplitude of the fluctuations is proportional to the standard value (i.e. the sqrt of the variance) of the sampling. Not only it is standard good practice in statistics when sampling data, but also we would have seen that the theoretical value stands inside the confidence interval. Otherwise, great video.
Thanks for the input
How do you know what the error is meant to be?
I only quickly skimmed some of the video but at one point I think he made an assumption that might be counter to stats theory. I'll check it later.
Fortunately, since this is a Bernoulli experiment (only two outcomes), if you have an estimate p of the success probability, then your estimate of the variance is p(1-p), so the standard error is sqrt(p(1-p)/n).
For n=1'000'000 (experiments, not prisoners), I get the following standard errors:
0.047848%
0.046339%
0.046144%
0.046142%
(To get the error bars I'd have to multiply by 1.96 for a 95% confidence interval.)
Awesome! Thanks!
If this strategy is done will less prisoners, the odds of success increase. If done with only 2 people, each person just opens the box with their own number on it and there's a 50% chance they both get it right.
Why is it not 25% they cant even use the loop strategy at that point
no its 25
@@Ishant875 How is it 25%? If they each open the box with their own number on it, either they both get it right or they both get it wrong, each of which has a 50% chance of happening. There's no other possibility.
@@osiris3791 Because then if the first one succeeds (50%), the second one is guaranteed to succeed (100%). It's 25% if they open randomly and 0% if they're suicidal and both agree to open the same box.
In a way they're using a loop of length 1 and there's a 50% chance no loop of length 2 exists
@@jacobwansleeben3364 The odds is always 50% for each individual prisoner, but the odds of two people both being right is 50% times 50%, which is 25%. The original video said that it approaches 30.7% as the number of prisoners increase, but it never addressed how the numbers would change if decreased to the point where there's essentially no loops.
There was nothing confusing about the original solution. And he did mathematically prove the percentages originally.
Not rigorously.
It has been solved rigorously in published works. Veratasium didn't create this premise or its solution
TH-cam ads sometimes take you to really good content; thank you TH-cam for showing me this ad on vertesium channel videos (well, it was intentional, but I am still happy)
Thanks? Glad you're with us!
So the trick is they not shuffle the boxes like in a deck of card but switching two of them than repeat, thats why you guaranteed you find your box if you do it long enough So you can't hide the box from it's the original loop. But counting the chances like all outcome has equal chances seems very wrong. I think Switching pairs is different than shuffle. Let's say you do 10K or 20K switching i think it has higher possibility to get to a longer queue. (but i'm not really sure ) So the calculation of 30% is incorrect, Because it is relative to the times of switching. (because it is different from throwing dices or shuffle deck) Please help if i misunderstand
Subscribed to your channel. You deserve more subs. I Appreciate your work
Oh thank you! I agree 😁
Good work with the intro!! Interesting video, keep up the work!!!!!
Thanks!
Very good video for a channel this small keep it up🙌
Thanks!
this channel is going to explode very soon :) keep up the great work you two......one.......er.
Haha thanks! I hope so!
The effort for making this video deserves more views.
I know right? Thanks!
You explain even the most difficult concepts in a simple way.
Over the last two weeks or so I ran my own C# version with a billion prisoners. I only ran 10000 rounds. I outputted the running average after each round. Out of those 10k rounds 3072 succeeded while 6928 failed. This gives us a "rough"average of 30.72%. Of course the sample size is still too low. Though the trend seems to be there ^^. Note that filling the array with a billion numbers took about 0.6 seconds each trial. Scrambling the numbers with fisher-yates took between 52 and 56 seconds. The actual check for the longest chain took between 80 and 160 seconds. That gives us an approximate 200 seconds per trial. So roughly 18 trials an hour, about 432 trials a day.
Note that I didn't bother to multithread anything ^^. It was just a simple console application that ran in the background over the last two weeks and a few days. I didn't wanted to bring my PC down. I barely even noticed it running.
A major issue here is that we can not really get a good ranomization of the numbers. PRNGs work decently for smaller sets of numbers. However the closer you get to the internal state of the PRNG, the more "patterns" will emerge.
Since every trial is essentially completely independent from each other, we could simply remember the success / fail / total counts and combine the results of several equal tests. So I got 3072 success over 10k. We get a better result if someone does, say 1k and he gets something like 307 successes, we can simply add up the success counts and the total runs.
Though keep in mind that the program occupies 4GB of ram since we need an array with 1 billion int32 values. When you want to multithread the whole thing, the best approach would be to have each thread / core doing its own trial. Though that means the memory would be multiplied by the number of threads / cores. So running 4 thread means 16GB of ram and you don't want your OS to start swapping the ram, so you really need a lot of ram. I do have 32GB, but I still want to use my PC :)
Well, 16Gb out of 32Gb is not that bad. And it would increase output 4 times. Definitely worth it IMHO. Also you don't use your computer all the time, so you may run even more consuming version of a program while you sleep/going for a walk/doing something else.
Damn, should I try it myself? :) Kinda want to program something in C and this looks interesting to try... 🤔
You don't need to store the numbers. Remember that we just need to know how long the loops are. Exactly which numbers are on the loop is not really relevant.
So you could just assume the first door has number 1, and draw random numbers until 1 comes up, reducing the maximum number to draw from with 1 for each draw. The number of draws you need before 1 comes up is the loop length. Once that loop length is larger than half the population size, the test fails. If the loop is smaller than half the population, and there is more than half the population left to draw from, continue drawing numbers to establish the next loop length. When there is less than half left, the remaining loops must all be smaller and the test succeeds.
@@renedekker9806 I don't think that this would even be remotely similar to what this problem was about. You just play with statistical propabilities and assume that give you the same outcome? That almost assumes you already know the exact statistical value / limit we wanted to figure out.
I'm not that good with statistics, however what you propose would give you a total statistical probabilty of 50% of drawing the 1 after drawing half the numbers in the way you proposed. To get the overall statistical probability that at least one of x independent event happens can be calculated by the product of the inverse of the individual probabilities. So our goal is essentially how likely it is to draw any other number. So for 10 numbers it would becomes (9/10) * (8/9) * (7/8) * (6/7) * (5/6) == 0.5 Of course we want the inverse of that (1.0-0.5) but in case of 0.5 it's again 0.5 or 50%. That would be the statistical mean.
The main issue with this problem is that every number can only be drawn once since every number is always in a particular loop. When you just draw random numbers between 0 and n, you will draw the same numbers multiple times. So I don't think your setup would actually represent the problem at all.
I'm sure this problem can actually be solved by pure stochastic analysis to actually directly calculate the expected limit at a certain sample size. Though as I said I'm not that good with probabilities and I kinda hate stochastic as it's used way too often to justify things in this world :) It has its place and is very useful in many situations, but real world problems can not always be reduced to a single probability value as the actual weighting of values plays an important factor. Anyways, I got sidetracked ^^. Unless you can show that your approach holds up to the values we get from the other methods, I don't think that will work.
@@Bunny99s _"statistical probabilty of 50% of drawing the 1 after drawing half the numbers"_ - I think you misunderstood what I proposed.
The Prisoners problem comes down to finding out whether there is a loop that is longer than half the population size (as mentioned at 8:25 in video). If there is, then some prisoners will not find their own number (failure), if there isn't, then the prisoners are guaranteed to all find their own number (success).
The main idea is that you do not need to generate the numbers in advance to determine the loops, you can generate them on the fly. Let's take the 10 prisoners as an example, and examine how a loop is determined. All numbers are random, so you can just as well start with prisoner 1. He first opens the box with number 1, with a chance of 1/10 to get 1. If that result is not 1, then he needs to open the box with that number.
But note that it does not really matter which specific number was in box 1, what is important is that the chance for the next box to contain 1 is 1/9. To test that, you just need to generate a random number from 1-9. The prisoner opens the next box, with a chance of 1/9 to get 1. If it is not 1, then the next box has chance 1/8 to contain 1, etc.
Suppose the prisoner draws 1 at this third occasion, then you know there is a loop of size 3. But you don't know anything yet about the remaining 7 numbers, so you repeat the process searching for the next loop, starting with 7 numbers this time. If after finding a loop, fewer than 5 boxes remain, you are certain the loops in there are all going to be shorter than 5, and the test succeeds. As soon as a loop gets longer than 5, the test fails.
The key insight is that it does not really matter which specific number comes up, it just matter what the probability is that it is the starting number of the loop. And that probability can be used to generate the random numbers on the fly.
I ran a program over night with 10,000 tests with 1 billion prisoners, and the statistics came pretty close to the number mentioned in the video.
Ok, this channel looks wild af. I'm subscribing.
Thanks!
Hey
This video is awesome!
So awesome as the veritasium video!
Thanks!
What the hell 😱 this channel only had 6k subs why? This ***** yt algorithm 😡
This is amazing 👍 hope you get as many recognition as you deserve ❤️✌️
Thanks! Yeah I was thinking the same thing! 😁
Yay! New Data Time video!
Appreciate your work on the theory! Great video!
Thanks!
HOW DID YOU KNOW I WAS WATCHING VERITASIUM, I'm honestly scared rn
Good video tough
Haha thanks! Check out my video on how I used ads to increase my subscribers
Same lol
I think it's useful to provide simulations like this. It helps people who have a hard time believing abstract reasoning. And I know you've been called out on this already, so it may not be worth me mentioning this, but the video title, comments made in the video, and comments you've made in response to people in this comment section seem to suggest you believe that running a bunch of tests is more reliable at finding the truth than rigorous logic.
For example, in the video description, you say, "I wrote a simulation with code to prove once and for all whether Veritasium was right or wrong."
Veritasium proved in his own video that he was correct. I'm sure plenty of people didn't understand the reasoning, but he _proved_ it. Your simulation, on the other hand, could have been anomalous and not matched with the actual statistic.
Unlikely events can happen, so if your simulation hadn't matched with the result Veritasium gave, that wouldn't prove Veritasium wrong. Likewise, just because your simulations were close to the results Veritasium gave doesn't prove Veritasium right. In either case, your experiments could have failed to match with the truth, whereas Veritasium's reasoning based on sound logic _has to._
Perhaps I should use a different word than "prove" - maybe tested or verified. But yes I think running tests is more reliable than thought logic. Would you want to board an airplane that logically should fly but had never been tested?
Just to reiterate this: I think that doing experiments like you does add a lot and helps bring in people who don't necessarily understand the theory (and I also think it's cool to see the number work out in practice, even when I know the theoretical result is rock solid). So it's a good video overall! Just a picky point.
@@DataTime27 There are certain circumstances where running tests is more reliable. I admit that. However, in those circumstances, there aren't clear axioms given. Instead, people using the theoretical reasoning have to _choose_ axioms to model the scenario. Those axioms can always be called into question, and I would say that experiments are likely to be more reliable in that setting.
In this scenario, however, is entirely theoretical - we are given specific axioms for how the puzzle/game works. The puzzle has to work a certain way, and using how the puzzle works, we can deductively prove this strategy has a success rate of close to 30% (for sufficiently many prisoners).
To me, it seems as silly as saying, "Sure, by definition, bachelors are unmarried, but let's _really prove it_ by finding as many bachelors as we can and then determining the proportion which are married. If it's close to 100%, then we can be actually be confident that bachelors are unmarried." Sure, the prisoner puzzle is a lot more complicated, so you could reasonably be concerned that some subtlety in reasoning was missed, especially if you find the reasoning hard to follow. And in that situation, running experiments might give you more confidence that the reasoning didn't miss anything. And I think that's also a very valid reason to make a video like this.
Ok, ur gonna blow up . Glad I'm early for the 100k journey.
Haha. Thanks! I hope!
Good you made this video,
I tried to explain it to my family, and they where like, “nope” “don’t believe it” “prove it”
So…
Thanks
xD
Definitely! Thanks for watching!
I think we need to take into the account that even if you choose a n-loop, (n>50), the prisoner is gonna go out and random pick the remaining boxes, and there’s a 1/(100-n) chance he choose the right box. Hence the slight difference in probability answer. You can try 4 prisoners, and the difference in answer will be bigger.
Can u elaborate this with an example
So, if I'm understanding what you're saying correctly, you're trying to say that if the prisoner picks a loop that is larger than 50, they'll just pick randomly instead, thereby increasing the chances even more, however, they won't know whether or not the loop is over 50 until they have already exhausted all their chances, and since they can't tell the prisoners coming behind them (and it would be too late by then anyways) Everyone else will still follow the same pattern.
"I think we need to take into the account that even if you choose a n-loop, (n>50), the prisoner is gonna go out and random pick the remaining boxes, and there’s a 1/(100-n) chance he choose the right box."
No, you're mistaken. The right box is always the last one in the loop because that's how we defined the loops. If there is a >50 loop then failure is guaranteed.
Haha this is great! My initial response to the video was also to write a script and experiment with it lol
I know right?
Unfortunately simulation is not a good example to prove the correctness of a solution. To prove something is wrong, you need ONE and ONLY ONE counter example.
Having said that, if you really want to prove the correctness of his theory (analysis, or whatever you want to call it), formal methods is the way to do it and ofc NOT using simulation
Would you get on an airplane that had passed all of the theoretical proofs but had never actually flown?
@@DataTime27 if it was *FORMALLY VERIFIED*, absolutely! As described by Professor Edsger W. Dijkstra “testing can be used to show the presence of bugs, but never to show their absence”. Look at the Floating Point bug in the intel chip, or the failure of any system in the world… it was tested (and probably heavily tested). However a formally verified design/concept will never fail as the correctness is guaranteed.
@@DataTime27 No, but the title of this video says "prove." Veritasium provided something much closer to a proof than you have here with is a simulation.
So what would be a more accurate word than "prove" Verified? Confirmed? Solved?
@@DataTime27 The screen at 7:30 says, "Successful Simulation."
Just saw this ad while watching a Veritasium video😂
You've gotten better at high fiving the robot. Much smoother now
You mean the high five at the beginning of the video?
@@DataTime27 yea
@@DataTime27 I just realized I was being an utter dumbass
Thanks!
I think is only working if the problem follows the solution. What if the numbers are not shuffled in a complete circle
Lets try this again. I posted before that running loops is NOT the ideal solution. You can do better and therefore, I believe, this is the real solution to the riddle.
I hypothesized that it is better to switch loops. Specifically I applied Benford's law to the 100 boxes.
What does this mean? It means the prisoners should switch loops every 3 numbers. The idea is that statistically short loops should occur more often than long loops.
1. The prisoner starts by opening the box with her number. If the prisoner does not find her number by the 3rd attempt; switch loops. That means opening another box instead of following the next box in the current loop.
2. Follow this loop for 3 attempts. if she don't find her number open another random box and follow that loop for 3 attempts.
3. This will allow the prisoner to test 16 three box loops and 1 two box loop to find her number.
According to Benford's law 3 box loops should appear 12.5% of the times in a random number sequence. Switching loops allows the prisoner to check 16X for a 3 box loop and 1X for a 2 box loop in the 100 boxes. This has a greater chance of success than running each loop to it's conclusion because a 3 box loop is statistically more probable than longer loops.
Meaning Benford's Law saying, it is more likely the prisoner's number will be in a 3 box loop than is is to be in a 51+ box loop.
I would like Data Time to create an experiment to demonstrate is this is greater than the 31% chance Veritasium gives.
Thank you.
I need you to explain me something please. The goal is to find its own number, not to do the most circuit.
In my understanding of your reasoning, indeed you will have more 3 number circuits but those circuits will not end with the prisoner number but rather the number of the box he switched to in the "3 pick" cycle. And we don't need that one, do we ?
So here is my question: What is the percentage of chance for a prisoner to get his own number (not just a number of any loop) ?
About 30%
You posted this nonsense about Benford's law on the other video. You tried to claim the chance of all prisoners succeeding is 70% with your strategy. You were told why Benford's law is not applicable, and why it is not possible for ANY strategy to go past 50%. You have been told that the strategy has been PROVED optimum. Yet here you are again refusing to accept you are wrong.
@@DataTime27 IF that's true then it proves that following a loop to conclusion vs switching loops has no impact on probability of success. And if that's true then the explanation for why the solution works is disproved. Either way, that's a huge reveal.
@@godfreypigott "You have been told that the strategy has been PROVED optimum."
Where has it been proven optimal? Do you have a reference?
Nice video
Can you do the test differently. Let say you have 100 prisoners. Make them in two groups. One group is larger 67% and other is 33%.
Larger group open boxes like in your video. First box is their own number and try to find end of the loop.
Second group(33%), they open box with a different number and start from there.
Lets say if prisoner has number 6 they open box 9 and try to find the loop.
And every prisoner in this group must add 3 to their own number.
Woo! Go Peter doing science things!
Thanks Marie!
I was actually watching the exact veritassium video on the prisoners and i saw the ad of you guys and i was totally mind blown. i mean what are the odds?
Haha! Great!
About 30%, I think.
Haha
That is great content!!! Congrats!
Thanks!
This channel is too underrated
Thanks!
In your example there is a 0% chance of success since there are four 72s in your picture of the numbers in the box.
Haha. You are the first person to notice that. Gold star ⭐
best advertisement award goes to the ad for this video
Thanks!
I am inclined to guess that Veritasium is right, but perhaps I am mistaken. Veritasium offers an apparently clever procedure, and a sketch of a proof. You may verify his solution by brute force. I would be more impressed by an abstract theoretical (non-brute force) verification.
It's important to have both a mathematical proof and a demonstration (brute force method).
If proofs are truly solid, them we can predict what will happen when demonstrations are used. Therefore, demonstrations are another form of verifying mathematical proofs.
If you have a mathematical proof that seems sound, but you try to simulate it and it fails - then it means either the simulation was flawed or the proof was flawed.
@@NoNameNoWhereGood comment. Thank you.
I still have a big problem which was explained in the Veritesium video. As there can be very small loops (circuits), there has to be a chance of me being on a loop that does not have my number. If it was a 15 box loop, in the your computation, does the prisoner jump and start another loop? And if he does what number does he use? I feel this type of failure wasn't addressed.
No, the loop which includes the box with your number is guaranteed to also contain the paper with your number. That is basically the whole point. Each box links to only one other box, so the at the end of the loop you enter via box X, you will always reach paper X.
That is why you start with number box that is your number. If you are prisoner 13 you will first open box 13 and see that it has number 2 for example. you will go around the loop and the very last one in the loop will be box 46 and it will have 13 in it, thus completing the loop since you started with box 13. So its even better if you have a small loop because you will find your number quickly. The only trouble is loops longer than 51 as mentioned.
Beautiful video, great work. Love you guys, u both rocks 😉😉😘😊😊😄😄😄😄
Thanks!
We need more like this
When you hit 1M subs host a gameshow called Date a Thyme.
Haha
Dude, credit is owed to Peter Bro Miltersen who proposed the puzzle en.wikipedia.org/wiki/100_prisoners_problem#cite_ref-gal2003_4-0
(And not to Veritasium. Veritasium was a gracious messenger)
Great video testing the theory!
Thanks!
Why not use Google MapReduce to do it really fast with lots of parallel computations
Stay in prison and do your time and nobody will be executed... that is the best odd of all 100 prisoners being free.
Haha. Wise advice!
Can you test their statement about renumbering boxes. Seems like this would not work as breaking connection between box and loop it is in.
Are you talking about adding 1 to each box?
@@DataTime27 YES, they stated you could add some number, say 5, to each box to reorder loops
Seems like this method might pit you on a loop that did not include your box.
You ok, one day for one million simulations with 10 prisoners. I run your GO code in 15 seconds and my Rust code in 11 seconds. You probably have similar hardware because you have to deal with After Effects
Oh interesting. I've never used rust before. Originally I used python which was too slow
That's realy well made, you're criminaly underrated
Thanks! Help spread the word!
Although Derek Muller was somewhat informal in his presentation, I believe he properly summarized the steps in a mathematical proof of his result. He was quoting results of other computer scientists and applied mathematicians, and their result is reasonably "established". In this video, you appear to be accepting the following assumption. Setting up a computer simulation (with imperfect randomization at the base of it all) and then running that as a statistical experiment is somehow more reliable to give a final validation of a probability statement than just performing the math and believing that valid work in statistics will give the correct answer. I think simulations are important to help validate, but they are at best another pillar of a proof, though not the central pillar. In other words, this simulation in Go on a PC has given some solid experimental corroboration of the result, but I think it is quite an overstatement to claim you have proven his unproven statement. But maybe I'm being too critical of your good effort.
Thanks. Perhaps a better word than 'prove' is 'tested' or 'verified'?
I 'tested' his proof. I 'validated' his proof.
@@DataTime27 Yes, I think those words would apply.
you guys are the only ones made me click on an add, Ginius.
Is Veritasium wrong?
Well, in 99% of cases, yes they are. They often slip in a little "trick" to switch from the correct answer to their own and, unless you spot it, their answer seems legitimate.
Take, for example, their "wind powered car" video . . in reality, a car travelling with the wind will accelerate, and the resultant net "wind force" will decrease linearly, e.g. at 20mph, a 20mph tail wind will exert 0 force. They then "proved" their theory using a treadmill which provided a _constant_ wind force, regardless of the speed of the car .. and he made $10,000 from that scam
Great video. Thanks for the experiment.
Thanks for watching!
Thanks for the ad 😃
Thanks for watching!
With one alteration to the plan, you can win even with loops of 51.
If you don't find your number on pull 50, you assume the number you last pulled is the box that's holding your number. Giving loops the size of 51 a win.
... if you do not find your number in pull 49, I guess. But otherwise a spledid idea! It even, obviously, makes the probability higher!
Except you don't get to open a 51st box, so you will lose.
@@godfreypigott they never say you have to open it. You just have to say what box it is.
@@Pestsoutwest At 0-45 of the *Veritasium* video:
_"One at a time each prisoner is allowed to _*_OPEN_*_ any 50 of the 100 boxes."_
Now point out where they said you get another chance by picking a 51st box.
@@godfreypigott They can add n value to every boxes in the room, therefore making an impact the same as redistributing the slips inside the boxes, break any loops over than 50 into smaller one.
I ran this same process with my computer for 100 prisoners - but I used Applesoft Basic and my apple IIC+
Oh awesome! Did you arrive at a similar result?
@@DataTime27 right now i am seeing success of 30.33%
I suspect i am incorrectly testing the size of the biggest loop or incorrectly counting the number of members
The RNG is not the greatest either.
How many iterations are you averaging over?
@@DataTime27 I modified the program to run more last night any by morning it was over 3000. Still about the same though 33.20 something percent. I am investigating whether I am counting the lengths of the loops correctly. I am still gonna blame the RNG though I think.
Yeah I think I had to run it longer. Like maybe closer to a million iterations
The problem is interesting, but the presentation is misleading and confusing. It is NOT that prisoners have 31.2% chance to be freed. 31.2% chance is for the map f: Box Labels - -> Prisoner's # to be good, in the sense that all cycle lengths of f
a person better likes to choose imprisonment than checking half a billion boxes. 😂🤣😂🤣🤣🤣lol
This was also in a ted ed video!
Oh what's the link? Did they write software to solve this as well?
@@DataTime27 Here is the link
th-cam.com/video/vIdStMTgNl0/w-d-xo.html
They didn't write a program but they do a similarly good job of explaining the riddle
Stop interrupting my Tom Scott videos!
I saw the add
Nice video! If the puzzle is modified such that odd numbered boxes contain only odd numbered slips and even boxes contain only even slips, then no loop would be > 50. Even worst case scenario would be 2 loops of 50 each. Then they would have a 100% chance of winning once they find out the loop strategy. In the current version, they can plan the strategy but still have to depend on luck. In the modified version, P(success) = P(coming up with the right strategy).
The only problem is that if it’s known that only even slips appear in even boxes then each prisoner would just open the 50 boxes that are even or odd depending on the number assigned and you wouldn’t need a loop strategy.
bro got the best intro
Thanks!
You still didn't prove it, while he did with the ln2 result taking the limit. Good concept haha, "ThEOreTIcaL" stuff, but no way I'm laughing at a joke that states that they have to test experimentally a correct result of a theoretical problem that, again, has been successfully solved using the only way you can prove mathematics, with mathematics
When doing mathematical proofs there's always a chance that you have made a mistake in your proof that no one has yet detected. Actually testing it (if you can) can increase the confidence that the result is correct.
@@seneca983 I would rather it be tested by rigorously going through the proof and looking for errors. The test may give me more confidence that my proof is right, but once the proof is verified we no longer need to keep testing.
This is different than in science where we often "prove" things by piling up evidence through multiple experiments. In science it is good to remember that these aren't truly proofs in the mathematical sense, but just overwhelming evidence leading us to conclusions.
@@zackcinq-mars2129 "I would rather it be tested by rigorously going through the proof"
Well, you can do both if you want more certainty. Also, this kind of testing approach does have the advantage that it can be quick and easy (depending on the case), so you may be able to catch some errors with little effort, even if this alone isn't enough for a high level of confidence.
Minute physics did this 8 years ago
I watched their videos about this problem. I didn't see them write any software to prove it works. Can you post a link?
You needed to explain why the fraction 1/m of all choices of sequences of n integers are in cycles of length m, when m is > n/2. That can be done simply, clearly. Please fix your video so people don't waste time on an inadequate explanation, one with part of the proof missing. Now I know I can't trust that your videos will prove what they claim to show.
You need to explain where you are getting the fraction 1/m from, if you want your comment to be accepted, as this notation is not used anywhere in the video. You claimed your explanation could be done simply and clearly, yet you made no actual attempt to explain it. Please refrain from making insolent comments, especially if you are not prepared to provide evidence. The video stays.
Oops, I didn't mean insolent! I meant don't just claim that the result in a very special case (the # of boxes in the cycle = the max possible, the total #of boxes) is the same (1/max or 1/# in cycle). You can explain the general case clearly. Not explaining leaves us not understanding.
I wonder what's the probability of success rate would be if you program for each prisoner picked randomly.
it would be closer to the 1/2^prisoners. Which were the odds calculated at the start.
Who are you to doubt veritasium?
Man.... knock it off.
That guy won a bet of $10k against a prof.
Did you watch the video?
It's called "science". There is no place for faith or authorities. There is always doubts.
For example, did you know that result heavily depends on shuffle algorithm? Veritasium said nothing about how boxes are rearranged. But with your own program you can experiment and get pretty unexpected results sometimes.
How do I know? Because I was curious enough to write my own program in C and played with it.
@1kvolt1978 awesome!
@@1kvolt1978 what shuffle algorithm? The box arrangement was a sample from a theoretical distribution. There's no algorithm involved. That is only relevant when you start simulating it (which does not implement the problem exactly, because then you need to use a pseudo-random number generator)
@@TomasAragorn I don't remember details now, but I do remember that I was doing different reshuffling trying to improve performance and I've got different results. I don't know why, I'm bad at math. But somehow result depends on reshuffling even if it feels like it shoudn't. At least in my program.
i just coment to tell you to make your videos longer your videos are great make them 20 minutes or something like that
Thanks! Actually it takes a long time for me to make even the shorter videos 😕. But stay tuned for my next video coming out next week. It'll be longer
Did you just do it all in a single execution? Doesnt look like a cryptographically secure (pseudo)random
Yeah, but if you're running it a million times I would think that wouldn't matter as much.
You should do a food poisoning trend video,idk I think it would be interesting . Keep it up !
It's wrong anybody who comes up with a number is wrong it's not a numbers problem I've already solved this riddle it is a linguistic problem
You here try to get some views and says nothing more than Veritasium actually!
Anyway I liked the video :P
What about the experiments I did on the computer? Veritasium didn't do that
@@DataTime27 I think if you wrote it while the video it will be really useful but you actually took a screenshots of your code we didn't know how the code written down and how the simulation really done .. I know you say the approach quickly but no one really know it.
at the end you show some numbers of percentages of the probability of winning. But I will prefer if you go deeply in the code it will be fun actually.
And dude no offence I really loved the video :P
but as I said it will be more fun if you focus in the journey of writing code more.. may be it's easy for you to write a code as you said "simple software" but for me it will be really helpful.
thanks a lot for considering my comment ,, this days no channels cares about feedback actually
Thanks! I'm afraid to go too deep into code because I don't want to bore people. I have a link to the code in the description for people who are really into the code
@@DataTime27 btw you looks like Errichto (CP guy) a bit :"
Oh haha. Interesting
Tf. U just bruteforced the already known solution
It wasn't known. It was theorized
@@DataTime27 I think a mathematical proof is enough to say that it's known. What you're doing can still be meaningful since it can increase the confidence that there isn't a error in the proof. However, it's not necessary for saying the result is known if the proof has been checked thoroughly enough.
suppose that the boxes contained the number *one more* than the box, so that box 1 contains 2, box two contains 3, box 3 contains 4 etc. So *each* prisoner would open their box, then move to the next box, then the next, and *none* of them would find their own box, because it would *always* be the one *before* the first box they opened. The veritasium algorithm fails in this case.
Yep. In fact it fails most of the time. It has about 30% success rate
Include this in squid game.....
My dude, stop with all that I/O and you'll see that you're computer can handle much higher numbers.
What I/O exactly are you referring to? The program doesn't hardly take any input
@@DataTime27 At the 7:20 mark, you output the results of the run after EACH run, flooding the terminal with output. You could potentially get faster results w/o printing the results until the very end. All that I/O has a cost.
Ah I see. Yes I simplified the code for the video. In reality I reduced the print statements for the time cost reason you mentioned
great job
Thanks!
you have 100 prisoners...your first choice of your own number is always 1 out of 100 just start with your number plus 2 then when you get result add 3 to it if you go over 100 just take away the 100 to get the next box you check .each time you go up to the next prime number...then your chances will be about 50 percent instead of 33 percent.... LOL
if you get the same number box as you already have just add 1 until you get an unopened box
@@2019inuyasha Then you break all the loops. Or rather, every prisoner will face a different set of loops.
I don't see how this would result in 50% chance that they all succeed in finding their number. By adding a different number each time it is no longer a loop. And by not starting with your number, even if it was a loop you aren't garaunteed to be in the loop.
math > computing
interesting
Subbed
Whats your linkedin.
Go to my about page and send me an email and I can show you
I made some trial runs with 10 prisoners. Unfortunately, I has never able to come up with a group of 10 prisoners NOT being executed.
How many runs did you do?
Sooo was watching a Tom Scott video, if I see ur ad anywhere else I’m unsubbing. Buuuut god job
Hmm I thought I put frequency caps on it. How often do you see the ad?
Faust can you give me more info? I have told the ads system to not serve this ad more than once a month to people. How often are you seeing this ad? Are you watching it on the same device each time? I'm worried other people might be having the same problem as you. Thanks
@@DataTime27 no it comes only 1 time a month
Do you see it too? Every month?
Oh cool it does work
nice work!
Thanks!
Brother can you please tell source code
Yeah it's in the video. Do you want to copy and paste it?
@@DataTime27 yes
@@DataTime27 yes
Looks like I can't put code into the description. I'm new to posting code. What is the best way to do that?
Ok I just created a github account for this
github.com/datatime27/videos/blob/main/prisoners/simulator.go
Is it asymptotic?
Yeah basically. As you add more iterations the answer moves closer to the theoretical expectation
Hmm, I wonder if the asymptote is irrational or not? It probably is, But my sciatica keeps me from looking into it right now. I will when I get a chance. @@DataTime27
Well… mistakes does happen
What mistake?
@@DataTime27 math mistake -_-
@@DataTime27 everybody makes mistakes
Can you show me what mistake I made?
@@DataTime27 well I’m not a scientist plus I didn’t actually see all your videos so idk but still everybody makes mistakes even data time. Even the person with the least mistakes has mistakes. When you didn’t make your TH-cam channel you made mistakes no doubt
subscribed :D
Thanks! Glad you're with us!
8:35 *or equal to*
Cool
You keep using this word, "proof", but I don't think it means what you think it means... ;)
Maybe I should use the word evidence or demonstration?