Re: [RESOLVED] Help with math algorithm
@moderator: if you like, it may be the time to move this thread to the algorithm section, as it has nothing to do with vc++ ...
Quote:
Originally Posted by
nuzzle
I don't quite follow your argumentation here.
do you agree that the trajectories of the runner and ( of a point of ) the water front are those in post #9 ?
if yes, then
1) you must agree that there's a dependency on the river bed width, or more specifically, of the ratio of that width with the water front distance at time 0; just consider that you cannot escape from an infinite river bed if the water ( approaching you at a finite distance ) is faster than you ... unless your "optimality" criterion does not depend on the ability of escaping or not; in this case, see 2)
2) you must agree that the probability of escape is given by the disequation in post #9, or more generally: w/d < 2*sin(p)/(q-cos(p)) [1] where q is the ratio of the water/runner speed. So you must agree that the question "to maximize the escape probability" is equivalent to maximizing the probability that [1] holds true.
now, if the runner knows all parameters of the problem exactly ( i.e. w/d, q and p ) then the escape probability can be either 1 or 0, being the former when [1] is satisfied; hence, in this case, the solution of the problem is trivially <any> angle satisfying [1] ( there's no single "optimal" value ).
otherwise, if there is some amount of uncertainty on the parameters ( the runner is just estimating them based on some partial knowledge ) then we need to maximize the probability that [1] is true where w,d,q and p are random variables.
This is easy when q and p are fixed ( as implied by the OP problem statement ): the resulting probability is maximized exactly when p is arccos(1/q).
But in general the result will differ arbitrarily depending on the joint probability distribution of the problem variables.
Quote:
Originally Posted by
nuzzle
I don't understand this either.
if q < sqrt(2) then the optimal angle is less than pi/4 ( ie away from the water front ); hence, in this case the answer C ( or at least to run at ~45° from the water front ) will give a better chance of escape.
Quote:
Originally Posted by Mike Pliam
but a specific solution is not possible
true, but a simplified model ( in this case, linear water front, straight motions, etc... ) can give insights on the qualitative structure of the solution, for example:
Quote:
Originally Posted by Mike Pliam
it is obvious that running away from the water wall at a slight angle to the bank will afford the maximum probability of escape
as said above, this is false when the runner is sure that the water front is slower than ~1.4 times his speed ( as in those action films, the runner could find a motorbike or a ferrari just in the middle of the river bed :); of course, keeping in mind that for p going to 0 the escape time goes to infinity, posing a limit on the escape time would mean posing a bound on the optimal angle towards 0 ) ...
Re: [RESOLVED] Help with math algorithm
actually you all are assuming variables not known...so I will do the same
if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
Vanaj
actually you all are assuming variables not known...so I will do the same
yes, and we can perfectly manage those "unknowns" using statistical methods, there's nothing to assume or guess.
Again, using a simplified model does not mean obtaining wrong results. On the contrary, most successful physical models work ( both theoretically and practically ) by approaching a problem via successive approximations, the reason being that the very idea of "true model" is (nearly always) meaningless theoretically , and often useless or counterproductive in practice. This is especially true when many unknowns of different nature are present and hence the qualitative structure of the solution, rather than the actual numerical values, are important.
Quote:
Originally Posted by
Vanaj
.as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.
nowhere the problem statement states that the decision ( including the logic behind it ) must be taken by the runner while waiting the water, that would be a totally different problem ( and heavily underspecified, being dependent on non trivial previous knowledge of the runner ... ).
If that was the real intent of the examiner then it would be a bad posed problem ( and I wouldn't work for him :) ).
Quote:
Originally Posted by
Vanaj
if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....
again, all this can be proven false, and so what ?
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
1) you must agree that there's a dependency on the river bed width, or more specifically, of the ratio of that width with the water front distance at time 0; just consider that you cannot escape from an infinite river bed if the water ( approaching you at a finite distance ) is faster than you ... unless your "optimality" criterion does not depend on the ability of escaping or not; in this case, see 2)
I don't agree.
It's true that the runner's starting point is defined in relation to the river width (the task says he starts in the middle of the river or at w/2 in your variables). But since the solution is independent of where the runner stands when he starts it will also be independent of the river width. The runner can start wherever he wants including in the middle but that doesn't matter for the solution. There's one optimal runner's angle regardless.
This is easy to see if one changes the problem slightly. Imagine instead the river is very narrow and you're standing at a distance from it. It's dry now but water is coming and you must cross it before it's too late. Essentially that's the same problem with the same solution only it becomes obvious now that the river width doesn't matter.
Further more, I think the problem has a probabilistic component but only in a conceptual way. And the solution supports that. It tells you how to run to have the best chance of survival regardless of how wide the river is, where you stand and where the river front is when you start running. But you won't be able to pin a probability on it so you won't know the likelihood of making it. What you do know is which angle postpones the moment of no return as much as possible. That is you know which angle allows the water to be closest to you and you'll still make it if you run for it. That's the optimal angle to always go for.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
Vanaj
actually you all are assuming variables not known...so I will do the same
if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.
As I've mentioned you don't have to do trigonometry in your head because evolution has hardwired the optimal strategy into our genes. At least that's what I think. You run straight to shore slightly downstream away from the approaching water without even thinking.
But even if the water is 5 miles upstream you still may not make it. It's because the water front may have passed the point of no return for you even if you run for shore at the optimal angle.
If the water hasn't yet passed the point of no return you'll have an interval of opportunity. It will be defined by two end-points on shore. The end-points will be dare-devil points, one upstream and one downstream. If you aim for one of them you'll arrive exactly when the water does. If you aim for a point in-between you'll arrive on shore with a margin before the water.
There will be a distance to the water at which your interval of opportunity shrinks to just one point. That's the optimal point to always aim for because it allows the water to come as close to you as possible and you'll still make it. If the water comes closer it passes the point of no return, the interval of opportunity shuts down and turns imaginary, and you can no longer get in safely.
If I were the reviewer that's the insight I would be looking for together with some quite straightforward high-school math & physics reasoning and calculations.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
nuzzle
the task says he starts in the middle of the river or at w/2 in your variables
no, the middle of the river has x coordinate 0 in the model of post #9
Quote:
Originally Posted by
nuzzle
The runner can start wherever he wants including in the middle but that doesn't matter for the solution.
really? so, a runner standing at the river bank would have the same chance of survival ( and hance take the same decision ) of a runner standing in the middle of the river bed :confused: ?
Quote:
Originally Posted by
nuzzle
Essentially that's the same problem with the same solution only it becomes obvious now that the river width doesn't matter.
no, it's not the same problem; in this reformulated problem the variable w would be equal to 2*d where d is the distance of the runner from the narrow river bed center at time 0.
Quote:
Originally Posted by
nuzzle
That's the optimal angle to always go for. It's independent on your chances of survival.
... uhm, if the "optimal" angle is indipendent on your "chances" of survival, then I wonder what do you mean by "optimal" or "chance" because that looks like a manifest contradiction ...
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
no, the middle of the river has x coordinate 0 in the model of post #9
Okay. That explains the dependency on the river width in your model. The only way to change the distance from the runner's starting position to shore is to get oneself another river. That's a pretty tight coupling isn't it.
Quote:
really? so, a runner standing at the river bank would have the same chance of survival ( and hance take the same decision ) of a runner standing in the middle of the river bed :confused: ?
Not really. A runner standing on shore doesn't have to run at all. But apart from that, regardless of where he stands on the riverbed when he starts running there's exactly one optimal escape angle. It's independent on where he starts, the river width and the distance to the approaching river.
Quote:
no, it's not the same problem; in this reformulated problem the variable w would be equal to 2*d where d is the distance of the runner from the narrow river bed center at time 0.
As I indicated, your model seems to present problems. If you drop it and reconsider the physics you'll realize it's the same problem with the same solution indeed.
It seems your model is hard to interpret physically. And if it gives you a dependency of the river width on the optimal escape angle it's definately wrong.
Quote:
... uhm, if the "optimal" angle is indipendent on your "chances" of survival, then I wonder what do you mean by "optimal" or "chance" because that looks like a manifest contradiction ...
Well, I meant that the chance of survival doesn't enter the calculation of the optimal escape angle as an actual probability measure, only as a concept. But okay I'll remove that last sentense.
Re: [RESOLVED] Help with math algorithm
as already noted in earlier posts, our models give exactly the same results given the problem data ( so I do find an optimal angle that is indipendent from the river bed width, as written in post #9 ).
What we don't agree on is the interpretation of the result ( in what sense that angle is "optimal" and indipendent on the river geometry ) and how it generalizes to different or more realistic problem assumptions.
more specifically, it's false that, in all generality ( eg, for every possible input probability measure on the problem data ), the optimal angle is not a function of the river bed width, as observed by the runner. Second, it's false that the optimal angle is always only slightly pointing against the water direction. For example, for some speed ratios you get optimal angles >45°. Third, you define an "optimal angle" as an angle that maximizes the probability of escape: there can be more than one. For example, when the probability of escape can be 0 or 1 ( as in the case of a runner standing on the river bank ) you'll have infinitely many "optimal" angles ( if one is "more optimal" than the others as you seems suggesting then the escape probability cannot be 0 or 1 ) whose min and max are a function of the river bed width; the fact that you can choose an angle that always stays inside this interval does not make it more "optimal", for the reason just stated above.
BTW
>> The only way to change the distance from the runner's starting position to shore is to get oneself another river. That's a pretty tight coupling isn't it.
the problem statement specifically says that the runner is in the middle of the river bed. How do you define being in the middle of something ?
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
as already noted in earlier posts, our models give exactly the same results given the problem data ( so I do find an optimal angle that is indipendent from the river bed width, as written in post #9 ).
What we don't agree on is the interpretation of the result ( in what sense that angle is "optimal" and indipendent on the river geometry ) and how it generalizes to different or more realistic problem assumptions.
Of course, depending upon the distance of the person from the river bank and the oncoming water, escape may not be possible. But the strategy of running at a slight angle (in this case) towards the river bank is optimal in the following sense: if it is possible to escape from the oncoming water, then this strategy will allow escape.
Quote:
Originally Posted by
superbonzo
more specifically, it's false that, in all generality ( eg, for every possible input probability measure on the problem data ), the optimal angle is not a function of the river bed width, as observed by the runner. Second, it's false that the optimal angle is always only slightly pointing against the water direction. For example, for some speed ratios you get optimal angles >45°. Third, you define an "optimal angle" as an angle that maximizes the probability of escape: there can be more than one. For example, when the probability of escape can be 0 or 1 ( as in the case of a runner standing on the river bank ) you'll have infinitely many "optimal" angles ( if one is "more optimal" than the others as you seems suggesting then the escape probability cannot be 0 or 1 ) whose min and max are a function of the river bed width; the fact that you can choose an angle that always stays inside this interval does not make it more "optimal", for the reason just stated above.
Yes, for most cases there will be many ways to run towards the bank which will allow escape, including routes which aren't straight lines, or ones which double-back upon themselves. Or, if the water is miles upstream, routes which include a tea-break would work also :). But the strategy outlined by nuzzle and others will always work, if any strategy works.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
more specifically, it's false that,
You seem stuck with model-induced corner cases that has nothing to do with generality or physical reality. For example what's this nonsense about the runner having infinitly many escape angles after he's made it safely to shore? Then there's nothing to escape from. What matters is that there's exactly one optimal escape angle (*) when he's in harms way and needs to escape.
This shows I think the importance of not over-extending the results of a mathematical model.
(*) For a specific speed ratio between river and runner. The task stipulates 8 so that's what I've assumed throughout but other values will give other optimal angles.
Quote:
the problem statement specifically says that the runner is in the middle of the river bed. How do you define being in the middle of something ?
Simple. You just set up a more general model than is strictly necessary. It's usually a good idea.
For examply nothing prevents you from expressing the runner's starting position with a free independent variable. You don't have to tie down your model to a starting position in the middle of the river. You could assume an arbitrary starting position and fix to the middle of the river afterwards.
Then you would've realized much earlier that the optimal escape angle is independent of the river width indeed. You also would've realized more readily that the narrow river variation I suggested actually is physically equivalent to the problem at hand and has the same solution.
Well, this is going in circles now so I drop it here. Thanks for the discussion.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
Peter_B
But the strategy outlined by nuzzle and others
... including myself ( our "optimal" angles are exactly the same; please, read carefully post#9 and #10 ).
I'm just saying that there are conditions compatible with the problem data and assumptions ( eg. no strange or alternative strategies ) that give a different optimal( = probability maximing ) angle, and hence that nuzzle's statement that "the optimal angle is indipendent on the probability measure of the model parameters" is just wrong, in general.
More specifically, if 1) you add a source of uncertainty in the angle choosen by the runner as the result of its decision process and the actual angle of the resulting linear motion ( this can happen, for example, if he uses eyesight to orient himself, or a compass, etc... ; note that the problem statement speaks of chance without exactly specifying what are the assumed sources of uncertainty; and I think that the error on the runner estimation of his relative postion is a very reasonable source of error ) and if 2) you add a statistical dependency between the escape angle and the other parameters of the physical model then you'll get a different chance maximizing angle, as choosen by the runner.
If you like and if I have time, I can produce an explicit counterexample.
Alternatively, if you're so sure that nuzzle's statement holds true then you should have no problem to prove it: build a complete physical model of the problem as idealized by the OP; then, for any given probability measure over the model configuration compute the escape probability; finally, prove that it's always equal to the value expected by the naive geometrical model.
Quote:
Originally Posted by nuzzle
Well, this is going in circles
agreed :)
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
as already noted in earlier posts, our models give exactly the same results given the problem data ( so I do find an optimal angle that is indipendent from the river bed width, as written in post #9 ).
What we don't agree on is the interpretation of the result ( in what sense that angle is "optimal" and indipendent on the river geometry ) and how it generalizes to different or more realistic problem assumptions.
Indeed, you do get the same results. I should have read more carefully - apologies for that.
Quote:
Originally Posted by
superbonzo
... including myself ( our "optimal" angles are exactly the same; please, read carefully post#9 and #10 ).
I'm just saying that there are conditions compatible with the problem data and assumptions ( eg. no strange or alternative strategies ) that give a different optimal( = probability maximing ) angle, and hence that nuzzle's statement that "the optimal angle is indipendent on the probability measure of the model parameters" is just wrong, in general.
More specifically, if 1) you add a source of uncertainty in the angle choosen by the runner as the result of its decision process and the actual angle of the resulting linear motion ( this can happen, for example, if he uses eyesight to orient himself, or a compass, etc... ; note that the problem statement speaks of chance without exactly specifying what are the assumed sources of uncertainty; and I think that the error on the runner estimation of his relative postion is a very reasonable source of error ) and if 2) you add a statistical dependency between the escape angle and the other parameters of the physical model then you'll get a different chance maximizing angle, as choosen by the runner.
If you like and if I have time, I can produce an explicit counterexample.
Alternatively, if you're so sure that nuzzle's statement holds true then you should have no problem to prove it: build a complete physical model of the problem as idealized by the OP; then, for any given probability measure over the model configuration compute the escape probability; finally, prove that it's always equal to the value expected by the naive geometrical model.
I wasn't thinking of this problem in terms of any of the complications you mention here, e.g. errors in angle estimation etc., so I won't address them. And I really don't think the original problem was intended to be anything other than a simple idealized situation, for which you yourself have already shown (in post #16) what the optimal strategy is:
Quote:
Originally Posted by
superbonzo
This is easy when q and p are fixed ( as implied by the OP problem statement ): the resulting probability is maximized exactly when p is arccos(1/q).
But in general the result will differ arbitrarily depending on the joint probability distribution of the problem variables.
i.e. the optimal angle only depends upon q, which is the ratio of the water speed to the running speed.
Maybe the difference of opinion other the interpretation of the result arises from differing opinions of the problem you are solving?
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
note that the problem statement speaks of chance without exactly specifying what are the assumed sources of uncertainty;
That's because there are no assumed sources of uncertainity! The problem is meant to be solved under general and total uncertainity. If you start pinning probabilities on the problem you're reducing uncertainity and that's not asked for.
Quote:
If you like and if I have time, I can produce an explicit counterexample.
The problem is to find the direction that gives "the best chance of escape" under 100 percent uncertainity. It can be solved using ordinary high-school math & physics. There is one optimal escape direction dependent only on the river-to-runner speed ratio.
Not that I think the interviewers would've accepted it but if you want to reformulate the problem and seek solutions based on reduced uncertainity by introducing probabilities feel free to do so. It would be interesting to see if, how and why such solutions would deviate. But no unphysical or model induced corner cases please.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
nuzzle
That's because there are no assumed sources of uncertainity! The problem is meant to be solved under general and total uncertainity.
well, you've just entered in a dangerous philosophical minefield, so it's time to prepare the typical VC++ forum reader to an even more boring and lengthy discussion ... :D
ok, let's depict the following hierarchy of uncertainties:
1) no uncertainty: every parameter of the physical model is known exactly; all properties of the model have a well defined and unique value.
say, if the model is the real line, we may consider a specific point.
2) "probabilistic" uncertainty: a probability measure on the space of parameters of the physical model is known exactly; all properties of the model have a well defined and unique probability distribution.
say, if the model is the real line with its natural measure, we may consider a specific probability distribution.
3) "epistemic" uncertainty: a set of probability measures on the space of parameters of the physical model is known exactly; to every property of the model and an element of that set we can map a unique probability distribution.
say, if the model is the real line with its natural measure, we may consider the set of all probability distributions ( as a side note, this is not identical to the set of all possible probabilty measures ).
4) "non epistemic" uncertainty: the model does not describe a statistically regular phenomenon; that is, you cannot generally assume, even in principle, that sampled frequencies converges to a fixed value in any way.
so, what do you mean by "total" or "no assumed" uncertainty ?
I assumed 3) in my reasoning: there's no fixed probability measure, we don't know it, but we can nonetheless assume one exists and insert in the model the probability measure as a yet another free parameter on which our conclusions will eventually depend on.
This is what I did and in this sense I can prove that there are two such probability measures ( ie, different <possible> sources of uncertainty ) that give different probability maximizing angles. This is sufficient to prove that the solution does depend on the probability structure of the problem.
Now, I think 3) is the correct POV for two reasons:
first, the problem specifically speaks of "chances". The word "chance", both historically and in contemporary usage in the statistical community, is a probabilty ( the converse is not true ) hence it's disallowed by definition in the general case 4), where the expression "to maximize chance" has literally no meaning.
That said, I can concede you that the vulgar usage of the word "chance" is as a synonym of "possibility" and so your interpretation of "the best chance of escape" is somehow acceptable. So, you're free to ignore this reason.
second, the hierarchy of uncertainties are inclusive from 1) to 3): 1) is a special case of 2) ( just take a point probability measure ), 2) is a special case for 3) ( just take a point set of probability measures ).
This means that if we can prove that a fixed strategy fails for j) then it must fail for j+1) as well.
Now, if 3) were also a special case of 4) then I can prove that our naive strategy fails for 4) too.
But, one could say that the "true" "non epistemic" uncertainty cannot include lower level of uncertainties, so let's add a
4.1) "total" non epistemic uncertainty: the model describes such an "unknown" phenomenon that not only we can not assume, we also must not expect any statistically regular sampling on the data.
but this definition ( and the like ) is more pathological as it seems:
first, it obtains "more uncertainty" by actually imposing an epistemic condition ( that the phemonenon is not statistically regular ); if uncertainty is a measure of absence-of-knowledge then this looks like a problem.
second, actually 3) already contains "much more" uncertainty than we need ( the set of all possible probability measures over some model is an enormous and highly pathological object ): more specifically, given an eventually huge number of samples of some phenomenon, we can always build a probabilistic model that is compatible with them ( just include correlations between samples ).
This means that there's no empirical way of distinguishing if a phenomenon is in 3) or is in 4.1); you can assume that 4.1) is empty without ever having to regret your choice, at least if your decision is based on empirical data. In no way you can claim that "if this or that is in 4.1) then this or that will happen to you".
So, in conclusion ( well, there would be many other things to say ... but this post is already too long ), 3) ( or at most 4), that includes 3) as a special case ) is the only sensible meaning of the expression "total uncertainty". In this way, I can prove that our naive strategy dependent only on the river-to-runner speed ratio is not optimal in the general "total uncertainty" case.
Quote:
Originally Posted by
nuzzle
It would be interesting to see if, how and why such solutions would deviate. But no unphysical or model induced corner cases please.
well, we already concluded that to any practical use, our solution is correct. So, I'm not fully clear on what you mean by "corner case". Anyway, I'll post a counterexample later when I have time ( at most tomorrow, I think ) ...
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
well, you've just entered in a dangerous philosophical minefield,
Come on, don't be dramatic. There's no dangerous philosophical minefield here.
The problem is stated and can be solved under full uncertainity. You don't have to assume anything about the runner or the river other than what's given in the question. That's the beauty of it and that insight would make you a strong candidate for the job I suppose.
If you assign additional properties to runner and river you're profoundly changing the situation. You can include the runner's ability to accurately measure distances and angles. You can include seasonal variations in the river flow. But you should know that these steps don't introduce uncertainity. On the contrary, they reduce it by pinning down different aspects of the situation. And that is so even if they're probabilistic or statistical in nature. This may give you a more realistic and useful model for sure but it won't be the problem you were asked to solve in the first place.
So please go ahead and modify the problem but as I said I'm not sure the interviewers would be impressed. Still I'm a little curious as to whether you can to come up with something that changes the optimal escape direction. I wouldn't be too shocked if you did though. It's not unusual for different problems to have different solutions.
Quote:
well, we already concluded that to any practical use, our solution is correct. So, I'm not fully clear on what you mean by "corner case". Anyway, I'll post a counterexample later when I have time ( at most tomorrow, I think ) ...
Do we have THE optimal solution to the problem or don't we? If we do then why a counter example? What are you trying to prove? That there are more than one optimal solution?
Well, maybe there is but then it shouldn't be unphysical, model induced or require a reformulation of the problem. All your attempts so far have stumbled on this.