About to make a big bet? Don't crash out, cash in with the power of maths When and how to make change to a successful business or popular website can be a huge risk. Get things right and - at best - nobody notices. Get things wrong, however, and you run the risk of losing business and suffering a damaged reputation. A good recent example is that of film and TV service Netflix, whose fluffed …
I'm the first to admit I'm rubbish at probabilities and such, but at a 'dummy' first-level approach, wouldn't taking many steps in random directions average out in the long run, leaving you pretty much where you started? Based on the article, I suppose not, but why...? Paris, obviously.
Anyway, loved the article!
Because, on average, each single step in a random direction will tend to end up with you further away from your starting point, though the effect diminishes as you go on.
Think of it this way - after the first step, you're one unit from your origin. If you take a second step in a random direction, you'll end up farther away unless your chosen direction lies within ±60° of the origin, so there's a 2/3 chance that you'll increase your distance.
there's a 2/3 chance that you'll increase your distance
Just modelled the setup quickly in SolveSpace - you're absolutely right, outside the +/-60 degrees of the original step, any step takes you further (and subsequent steps tend to increase the angle towards 180 degrees - a 50/50 chance); it makes perfect sense now. Thank you very much - have a virtual one! -->
I was taught at school that the expected result of the drunkard's walk is sqrt(n) - that is, after n paces you'll be sqrt(n) paces away from your starting point.
But that monte carlo simulation seems to indicate that the distance is actually something like 0.9sqrt(n).
So what's going on here?
Me too. It's possible that the 'RAND' function being used is less than perfect - producing a good random number generator on a deterministic computer system is a hard problem, proving that it's a good random number generator is even tougher. But if that were the case, I'd expect to see as many overshoots as undershoots of the expected value.
So I'll go with programmer error :)
This post has been deleted by its author
I was taught at school that the expected result of the drunkard's walk is sqrt(n) - that is, after n paces you'll be sqrt(n) paces away from your starting point.
I believe \sqrt{n} is only an approximation. Wikipedia says that for the one-dimensional random walk,
This hints that E(|S_n|)\,\!, the expected translation distance after n steps, should be of the order of \sqrt n. In fact,[citation needed]\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac 2{\pi}}.
(Apologies for the LaTeX, for those who aren't comfortable reading it; the Reg doesn't give me a lot of latitude for writing math. See the Wikipedia link for the pretty version.)
In other words, for the 1-dimensional case, E(Sn), the expectation for the series, converges on the square root of n times the square root of 2/π. The latter quantity is about 0.8. I can't be bothered to do the math on a Friday night, but that's suspiciously close to what the graph looks like - i.e., the Monte Carlo curve appears to be converging on a large fraction of \sqrt{n}.
Its the disentropic nature of randomness.
Its extraordinarily unlikely you would actually end up exactly where you started. You would need a random sequence that actually 'undid' itself exactly.
I believe this particular problem is known as the 'drunkards walk' problem.
I've used Monte Carlo simulation many times to judge how much a project is likely to cost or how long it will take. As many will know, before a project is started there are 'deterministic' costs (i.e. the bricks will cost £1500, I have a firm quote), however there are uncertain costs (i.e. labour costs could be £1000 to £2000 but most likely £1200) and there are risks (i.e. There's a 25% chance I might need to reinforce the foundations at £800).
If you just added up the cost of the deterministic and the most likely of the uncertain values and budgeted on that amount, what would happen if the labour costs go above the most likely or the risk occurs? - the Budget won't be enough. Conversely, there's no point budgeting way more than is needed, those funds could be invested elsewhere.
So to work out what the best budget figure is, Monte Carlo analysis can be used. It works by modelling the project and running that model thousands of times. For each run of the model, the uncertain values are picked randomly from their distribution and each risk may or may not occur, based on its chance (so a risk with 25% probability will occur on a quarter of the runs). The cost of each run is ploted on a graph and after a thousand runs a nice distribution will be presented. The distribution can be sliced to give median, upper and lower quartile values, all that has to be done is decide where on that graph should be used to pick the budget. Pick an upper quartile figure and it is likely that there will be lots of spare budget, a lower quartile figure is likely to be not enough (while still more than the deterministic) so most pick the median, it could be insufficient but things will have to go badly for that to happen because it does already take into account some risks occuring.
Monte Carlo analysis is a powerful tool and it can be used for time in exactly the same way. But it only works if the modelling is sound, optimism kills it - underestimate the value of risks or fail to identify risks and uncertainties and it will give a false impression.
PS - It isn't degree-level difficult but I have had to explain it to far too many people who were supposed to be the ones qualified
@Nifty - to be honest that was a hypothetical project (the examples work well without explaining the whole background).
However, to take your question seriously (I'm guessing it wasn't). Whether you model such costs depend on what the scope of the project is, specifically in this case - at what point is the project finished?
If the project is just to get the house built then the problems you highlight should not be included. However, if the project is to build and sell the house for a certain return, then such uncertainties as "house market fluctuations" and risks such as the developer attempting to gazump the buyers, should be factored in. In any case you still have to manage these risks when they happen.
This is what I mean about identifying risks properly, if you don't then your project can be derailed, get it right and when bad things happen, the project will stay on track becuase you have anticipated them and have a plan to handle them. Even if that plan is just having some extra money in the budgetbudget, hence modelling the costs.
@unscarred - There are many tools available, mostly extensions of risk management tools (such as www.palisade.com/risk/) - however most recently I have seen massive bespoke Excel monsters because of the need for some organisations to obtain very unique data (not just a single distribution).
It depends on how much data you need and how accurate you need it. It shouldn't be too difficult to build a simple cost model on a spreadsheet. But the problem with spreadsheet based models is they aren't very good for estimating time or handling complex time/cost/risk relationships. Commerical tools are better at giving both time and cost estimates from a single risk register and handling complexity within model (such as do the risks occur sequentially? or do they force other risks to occur?)
I reckon all you'd need for a crude spreadsheet model is 3 sheets - a sheet with definite costs (max/min/most likely for each), a sheet with risks (probability, max/min/ML) and a results sheet. Have a macro (or something better) add a line in the total sheet for each run of the model randomly picking values from the max/min/ML distribution for each cost and risk (but only adding each risk cost if it meets its probability check for that run). Then graph the results, you should get a nice bell curve in most cases giving an obvious median point.
A few years ago, the stories were about people who'd bought 'off plan' complaining that they were being expected to pay what they said they'd pay, not what it was actually worth now. Because it was now worth a lot less.
Now, especially darn sarf in Lunnun, 'off plan' buyers are complaining that both sides were not tied to a price agreed years ago, and they're being asked to pay what it's worth now.
I wonder how many are the same people.
I've messed around with something like this in the past, now tempted to try and put it to more practical use. Do you just use a spreadsheet to do the modelling and presentation of results?
There are many online tutorials for doing Monte Carlo simulations in languages that are actually suitable for that sort of thing, such as R and Julia and Python. A quick search turned up several likely-looking candidates. And a bonus outcome is that you'd know some R or Julia or Python afterward.
Python is not my favorite language for number-crunching, but it is hugely popular in the data-science playground these days, so there's a lot of help available. I think Julia is OK; I've actually never used R, but many people speak well of it.
(Personally, I wouldn't use Excel for anything more ambitious than opening an Excel spreadsheet someone else created. I'd rather spend a day scraping paint off the side of my house than an hour working in Excel. But that's just me.)
Interesting, so it appears my first Python script was a Monte Carlo Simulation, and I didn't even realise! Go me!
After an evening of imbibing some years back, some smartarse posed the Monty Hall Problem to the table. The next day, after much discussion, I wrote a little script to play the game a million times. Turns out you are indeed better off changing your door.
Of course the Monty Hall Problem is not especially difficult to solve deterministically - though it is a bit counter-intuitive, but a nice example to get your head around :)
Also a nice problem to pose to Python beginners on a 101 course - call the rand module, use it to set a couple of variables, simple While loop (n<1000000) and If-Else block and a couple of variables to count win/lose. Doesn't need many lines of code, but there's a few different elements in there to make them think, and they learn a bit of probability at the same time.
For bonus points ask for user input at the start for number of repetitions and whether the player changes their choice or not (rather than hard-coding the logic).
Thats my point its not truly random walking has a weighting to one particular side over the other much like betting at a casino.
In a stunning development, mathematicians have already generalized the random walk problem to non-symmetrical lattices. So your concern has been addressed.
Also, the worldwide shortage of apostrophes ended some time ago, though we thank you for your conservation efforts.
Yes, of course it does. It's not a real person in a real desert - when did you last meet a real person who took successive steps in entirely random directions, even when drunk out of their minds?
It's simply a way of describing an entirely random movement in a way that the reader can relate to.
If I remember rightly, there are at least two interesting (and related) facts about this version of the Drunkard's Walk that don't seem to have been mentioned yet:
1) Given long enough, the drunkard will return to his exact starting point
2) Indeed, given long enough, the drunkard will visit EVERY point in the desert and beyond (in other words, his walk is space-filling).
That despite the fact that his average distance from his starting point grows with time.
Far more interesting than the drunkard's walk is a Lévy flight. This is also a random walk, but now small steps are interspersed with sporadic very long steps.
Wandering albatrosses use this search strategy on their voyages on the largely empty ocean.
Tux because it is also a bird.
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
