text:
# 20

Personal Blog

Suppose that you build an AI, and Omega appears to it and says:

Here's a button. A million years ago I calculated the umpteenth digit of pi. If it is even, I calculated whether you would press this button (in such a way that your human creator was never simulated as a conscious being). If I predicted that you wouldn't press the button, I destroyed Earth right then and there.* If it is odd, I created a doomsday device that will destroy the solar system if you press this button.

[* ETA: Assume that if the digit is even and the AI is predicted to press the button, Omega does not destroy Earth, but does turn Alpha Centauri purple (say). The point is for this to be a scenario that you, the AI creator, know not to have come to pass.]

Suppose you're the kind of AI creator whose AI is time consistent in a certain sense from the beginning of time and presses the button. Then you have an AI that satisfies a certain kind of philosopher, wins big in a certain logically impossible world, and destroys humanity.

Suppose, on the other hand, that you're a very similar kind of AI creator, only you program your AI not to take into account impossible possible worlds that had already turned out to be impossible (when you created the AI | when you first became convinced that timeless decision theory is right). Then you've got an AI that most of the time acts the same way, but does worse in worlds we know to be logically impossible, and destroys humanity less often in worlds we do not know to be logically impossible.

Wei Dai's great filter post seems to suggest that under UDT, you should be the first kind of AI creator. I don't think that's true, actually; I think that in UDT, you should probably not start with a "prior" probability distribution that gives significant weight to logical propositions you know to be false: do you think the AI should press the button if it was the first digit of pi that Omega calculated?

But obviously, you don't want tomorrow's you to pick the prior that way just after Omega has appeared to it in a couterfactual mugging (because according to your best reasoning today, there's a 50% chance this loses you a million dollars).

The most convincing argument I know for timeless flavors of decision theory is that if you could modify your own source code, the course of action that maximizes your expected utility is to modify into a timeless decider. So yes, you should do that. Any AI you build should be timeless from the start; and it's reasonable to make yourself into the kind of person that will decide timelessly with your probability distribution today (if you can do that).

But I don't think you should decide that updateless decision theory is therefore so pure and reflectively consistent that you should go and optimize your payoff even in worlds whose logical impossibility was clear before you first decided to be a timeless decider (say). Perhaps it's less elegant to justify UDT through self-modification at some arbitrary point in time than through reflective consistency all the way from the big bang on; but in the worlds we can't rule out yet, it's more likely to win.

# 20

New Comment

I wish I could upvote this more than once. An agent not yet capable of 100% precommitments can't be expected to make them, but you can imagine it slowly self-modifying to install stronger and stronger internal pre-commitment mechanisms, since even probabilistic precommitments are better than nothing (like Joe at least tried to do in Newcomb's problem happened to me).

Then it would fare more optimally on average for scenarios that involve predicting its behavior after those installments. I think that's the most one can hope for if one does not start with precommitment mechanisms. You can't stop Omega (in Judea Pearl's timeless sense of causality, not classically) from simulating a bad decision you would have made one year ago, but you can stop him from simulating a bad decision you would make in the future.

I'll take it :)

(Sorry about the late reply. I'm not sure how I missed this post.)

Suppose you're right and we do want to build an AI that would not press the button in this scenario. How do we go about it?

1. We can't program "the umpteenth digit of pi is odd" into the AI as an axiom, because we don't know this scenario will occur yet.
2. We also can't just tell the AI "I am conscious and I have observed Alpha Centari as not purple", because presumably when Omega was predicting the AI's decision a million years ago, it was predicting the AI's output when given "I am conscious and I have observed Alpha Centari as not purple" as part of its input.
3. What we can do is, give the AI an utility function that does not terminally value beings who are living in a universe with a purple Alpha Centauri.

Do you agree with the above reasoning? If so, we can go on to talk about whether doing 3 is a good idea or not. Or do you have some other method in mind?

BTW, I find it helpful to write down such problems as world programs so I can see the whole structure at a glance. This is not essential to the discussion, but if you don't mind I'll reproduce it here for my own future reference.

def P():
if IsEven(Pi(10^100)):
if OmegaPredict(S, "Here's a button... Alpha Centauri does not look purple.") = "press":
MakeAlphaCentauriPurple()
else:
DestroyEarth()
else:
LetUniverseRun(10^6 years)
if S("Here's a button... Alpha Centauri does not look purple.") = "press":
DestroyEarth()

LetUniverseRun(forever)

Then, assuming our AI can't compute Pi(10^100), we have:

• U("press") = .5 * U(universe runs forever with Alpha Centauri purple) + 0.5 * U(universe runs for 10^6 years then Earth is destroyed)
• U("not press") = .5 * U(Earth is destroyed right away) + 0.5 * U(universe runs forever)

And clearly U("not press") > U("press") if U(universe runs forever with Alpha Centauri purple) = U(Earth is destroyed right away) = 0.

Thanks for your answer! First, since it's been a while since I posted this: I'm not sure my reasoning in this post is correct, but it does still seem right to me. I'd now gloss it as, in a Counterfactual Mugging there really is a difference as to the best course of action given your information yesterday and your information today. Yes, acting time-inconsistently is bad, so by all means, do decide to be a timeless decider; but this does not make paying up ideal given what you know today, choosing according to yesterday's knowledge is just the best of the bad alternatives. (Choosing according to what a counterfactual you would have known a million years ago, OTOH, does not seem the best of the bad alternatives.)

That said, to answer your question -- if we can assume for the purpose of the thought experiment that we know the source code of the universe, what would seem natural to me would be to program UDT's "mathematical intuition module" to assign low probability to the proposition that this source code would output a purple Alpha Centauri.

Which is -- well -- a little fuzzy, I admit, because we don't know how the mathematical intuition module is supposed to work, and it's not obvious what it should mean to tell it that a certain proposition (as opposed to a complete theory) should have low probability. But if we can let logical inference and "P is false" stand in for probability and "P is improbable," we'd tell the AI "the universe program does NOT output a purple Alpha Centauri," and by simple logic the AI would conclude IsOdd(Pi(10^100)).

[-][anonymous]10y 0

The solution is for the AI to compute that digit of pi and press the button iff it's even. :-)

[This comment is no longer endorsed by its author]Reply

Then you have an AI that satisfies a certain kind of philosopher, wins big in a certain logically impossible world, and destroys humanity.

And if we assume that it's better to have Earth exist one million years longer, this is the correct thing to do, no question about it, right? If you're going to take a bet which decides the fate of entire human civilization, you want to take the best bet, which in this case(we assume) was to risk to live only for million years instead risking of exploding right away.

Unless, of course, in the counterfactual you know you would've pressed the button even though you now don't. Rigging the lottery is a sneaky way out of the problem.

If you create your AI before you can infer from Omega's actions what the umpteenth digit of pi is, then I agree that you should create an AI that presses the button, even if the AI finds out (through Omega's actions) that the digit is in fact odd. This is because from your perspective when you create the AI, this kind of AI maximizes your expected utility (measured in humanity-years).

But if you create your AI after you can infer what the digit is (in the updated-after-your-comment version of my post, by observing that you exist and Alpha Centauri isn't purple), I argue that you should not create an AI that presses the button, because at that point, you know that's the losing decision. If you disagree, I don't yet understand why.

If you create your AI before you can infer from Omega's actions what the umpteenth digit of pi is, then I agree that you should create an AI that presses the button, even if the AI finds out (through Omega's actions) that the digit is in fact odd.

If you can somehow figure it out, then yes, you shouldn't press the button. If you know that the simulated you would've known to press the button when you don't, you're not anymore dealing with "take either 50% chance of world exploding right now VS. 50% chance of world exploding million years from now", but a lot simpler "I offer to destroy the world, you can say yes or no". Updateless agent would naturally want to take the winning bet if gaining that information were somehow possible.

So, if you know which digit omega used to decide his actions, and how, and you happen to know that digit, the bet you're taking is the simpler one, the one where you can simply answer 'yes' or 'no'. Observing that Earth has not been destroyed is not enough evidence though, because the simulated, non-conscious you would've observed roughly the same thing. Only if there were some sort of difference that you knew you could and would use in the simulation, like, your knowledge of umpteenth digit of pi, or color of some object in the sky(we're assuming Omega tells you this much in both cases. This about the fate of humanity, you should seriously be certain about what sort of bets you're taking.

Why do you think that you should conclude that pushing the button is a losing decision upon observing evidence that the digit is odd, but the AI should not? Is a different epistemology and decision theory ideal for you than what is ideal for the AI?

Why do you think that you should conclude that pushing the button is a losing decision upon observing evidence that the digit is odd, but the AI should not? Is a different epistemology and decision theory ideal for you than what is ideal for the AI?

I think that the AI should be perfectly aware that it is a losing decision (in the sense that it should be able to conclude that it wipes out humanity with certainty), but I think that you should program it to make that decision anyway (by programming it to be an updateless decider, not by special-casing, obviously).

The reason that I think you should program it that way is that programming it that way maximizes the utility you expect when you program the AI, because you can only preserve humanity in one possible future if you make the AI knowingly destroy humanity in the other possible future.

I guess the short answer to your question is that I think it's sensible to discuss what a human should do, including how a human should build an AI, but not how "an AI should act" (in any other sense than how a human should build an AI to act); after all, a human might listen to advice, but a well-designed AI probably shouldn't.

If we're discussing the question how a human should build an AI (or modify themselves, if they can modify themselves), I think they should maximize their expected payoff and make the AI (themselves) updateless deciders. But that's because that's their best possible choice according to their knowledge at that point in time, not because it's the best possible choice according to timeless philosophical ideals. So I don't conclude that humans should make the choice that would have been their best possible bet a million years ago, but is terrible according to the info they in fact have now.

[-][anonymous]12y 0

Let's take for granted that earth existing for million years before exploding is better than it exploding right away. Then, of course you should press the button. If you don't do that, that'd mean that every time this sort of thing happens, you fare, on average, worse than someone who doesn't update like you suggest. You should take the best bet, even acausally, especially if you're gambling with the fate of the entire world.

If there's some trick here why you should not press the button, I'm not seeing it.

"you" could be a UDT agent. So does this example show a divergence between UDT and XDT applied to UDT?

Stuart, sorry I never replied to this; I wasn't sure what to say until thinking about it again when replying to Wei Dai just now.

I'd say that what's going on here is that UDT does not make the best choices given the information available at every point in time -- which is not a defect of UDT, it's a reflection of the fact that if at every point in time, you make what would be the best choice according to the info available at that point in time, you become time-inconsistent and end up with a bad payoff.

To bring this out, consider a Counterfactual Mugging scenario where you must pay $1 before the coin flip, plus$100 if the coin comes up tails, to win the $10,000 if the coin comes up heads. According to the info available before the flip, it's best to pay$1 now and $100 on tails. According to the info when the coin has come up tails, it's best to not pay up. So an algorithm making both of these choices in the respective situations would be a money-pump that pays$1 without ever getting anything in return.

So my answer to your question would be, what this shows is a divergence between UDT applied to the info before the flip and UDT applied to the info after the flip -- and no, you can't have the best of both worlds...

I'm wondering where this particular bit of insanity (from my perspective) is coming from. I assume that if Omega would have destroyed the solar system (changed from just the earth because trading off 1million years of human history vs the rest of the SS didn't seem to be the point of the thought experiment) a million years ago if AI would not press the button and made the button also destroy the solar system you'd want the AI to press the button. Why should a 50% chance to be lucky change anything?

Would you also want the AI not to press the button if the "lucky" digit stayed constant, i. e. if Omega left the solar system alone in either case if the digit was even, destroyed the solar system a million years ago if the digit was not even and the AI would not press the button and made the button destroy the solar system if the digit was not even and the AI would press the button? If not, why do you expect the choice of the AI to affect the digit of pi? Ignorance does not have magic powers. You can't make any inference on the digit of pi from your existence because you don't have any more information than the hypothetical you whose actions determine your existence. Or do you rely on the fact that the hypothetical you isn't "really" (because it doesn't exist) conscious? In that case you probably also think you can safely two-box if the boxes are transparent, you see money in both boxes and Omega told you it doesn't use any conscious simulations. (you can't, btw, because consciousness doesn't have magic powers either).

I'm wondering where this particular bit of insanity (from my perspective) is coming from.

Well, let's see whether I can at least state my position clearly enough that you know what it is, even if you think it's insane :-)

Or do you rely on the fact that the hypothetical you isn't "really" (because it doesn't exist) conscious? In that case you probably also think you can safely two-box if the boxes are transparent, you see money in both boxes and Omega told you it doesn't use any conscious simulations. (you can't, btw, because consciousness doesn't have magic powers either).

My argument is that since I'm here, and since I wouldn't be if Omega destroyed the solar system a million years ago and nobody ever simulated me, I know that Omega didn't destroy the solar system. It seems that in what you've quoted above, that's what you're guessing my position is.

I'm not sure whether I have accepted timelessness enough to change myself so that I would one-box in Newcomb with transparent boxes. However, if I thought that I would two-box, and Omega tells me that it has, without using conscious simulations, predicted whether I would take both boxes (and save 1,001 lives) or only one box (and save 1,000 lives), and only in the latter case had filled both boxes, and now I'm seeing both boxes full in front of me, I should be very confused: one of my assumptions must be wrong. The problem posed seems inconsistent, like if you ask me what I would do if Omega offered me Newcomb's problem and as an aside told me that six times nine equals fourty-two.

Perhaps this simplification of the original thought experiment will help make our respective positions clearer: Suppose that Omega appears and tells me that a million years ago, it (flipped a coin | calculated the umpteenth digit of pi), and (if it came up heads | was even), then it destroyed the solar system. It didn't do any simulations or other fancy stuff. In this case, I would conclude from the fact that I'm here that (the coin came up tails | the digit was odd).

I'm curious: would you say that I'm wrong to make that inference, because "consciousness isn't magic" (in my mind I don't think I'm treating it as such, of course), or does Omega making a prediction without actually simulating me in detail make a difference to you?

Perhaps this simplification of the original thought experiment will help make our respective positions clearer: Suppose that Omega appears and tells me that a million years ago, it (flipped a coin | calculated the umpteenth digit of pi), and (if it came up heads | was even), then it destroyed the solar system. It didn't do any simulations or other fancy stuff. In this case, I would conclude from the fact that I'm here that (the coin came up tails | the digit was odd).

In this case this is unproblematic because there is no choice involved. But when the choice is entangled with the existence of the scenario/the one making the choice you can't simultaneously assume choice and existence, because your choice won't rewrite other things to make them consistent.

Simple example: Omega appears and tells you it predicted (no conscious simulations) you will give it $100. If you wouldn't Omega would instead give you$100. Omega is never wrong. Should you give Omega $100? Of course not. Should you anticipate that Omega is wrong, or that some force will compel you, that lightening from the clear sky strikes you down before you can answer, that Omega disappears in a pink puff of logic, that you disappear in a pink puff of logic? It doesn't really matter, as long as you make sure you don't hand over$100. Personally I'd assume that I retroactively turn out not to exist because the whole scenario is only hypothetical (and of course my choice can't change me from a hypothetical person into a real person no matter what).

For you to get the $100 there needs to be a fact about what you would do in the hypothetical scenario of Omega predicting that you give it$100, and the only way for that fact to be what you want it to be is to actually act like you want the hypothetical to act. That means when confronted with apparent impossibility you must not draw any conclusions form the apparent contradiction that differentiate the situation from the hypothetical. Otherwise you will be stuck with the differentiated situation as the actual hypothetical. To get the benefit of hypothetically refusing to give $100 you must be ready to actually refuse to give$100 and disappear in a puff of logic. So far so uncontroversial, I assume.

Now, take the above and change it to Omega predicting you will give it $100 unless X is true. Nothing important changes, at all. You can't make X true or untrue by changing your choice. If X is "the sky is green" your choice will not change the color of the sky. If X is that the first digit of pi is even your choice will not change pi. If X is that you have a fatal heart disease you cannot cure yourself by giving Omega$100. Whether you already know about X doesn't matter, because ignorance doesn't have magical powers, even if you add consciousness to the mix.

Now, take the above and change it to Omega predicting you will give it \$100 unless X is true. Nothing important changes, at all. You can't make X true or untrue by changing your choice.

Wait, are you thinking I'm thinking I can determine the umpteenth digit of pi in my scenario? I see your point; that would be insane.

My point is simply this: if your existence (or any other observation of yours) allows you to infer the umpteenth digit of pi is odd, then the AI you build should be allowed to use that fact, instead of trying to maximize utility even in the logically impossible world where that digit is even.

The goal of my thought experiment was to construct a situation like in Wei Dai's post, where if you lived two million years ago you'd want your AI to press the button, because it would give humanity a 50% chance of survival and a 50% chance of later death instead of a 50% chance of survival and a 50% chance of earlier death; I wanted to argue that despite the fact that you'd've built the AI that way two million years ago, you shouldn't today, because you don't want it to maximize probability in worlds you know to be impossible.

I guess the issue was muddled by the fact that my scenario didn't clearly rule out the possibility that the digit is even but you (the human AI creator) are alive because Omega predicted the AI would press the button. I can't offhand think of a modification of my original thought experiment that would take care of that problem and still be obviously analgous to Wei Dai's scenario, but from my perspective, at least, nothing would change in my argument if, if the digit is even, and Omega predicted that the AI would press the button and so Omega didn't destroy the world, then Omega turned Alpha Centauri purple; since Alpha Centauri isn't purple, you can conclude that the digit is odd. [Edit: changed the post to include that proviso.]

(But if you had built your AI two million years ago, you'd've programmed it in such a way that it would press the button even if it observes Alpha Centauri to be purple -- because then, you would really have to make the 50/50 decision that Wei Dai has in mind.)

Wait, are you thinking I'm thinking I can determine the umpteenth digit of pi in my scenario? I see your point; that would be insane.

My point is simply this: if your existence (or any other observation of yours) allows you to infer the umpteenth digit of pi is odd, then the AI you build should be allowed to use that fact, instead of trying to maximize utility even in the logically impossible world where that digit is even.

Actually you were: There are four possibilities:

• The AI will press the button, the digit is even
• The AI will not press the button, the digit is even, you don't exist
• The AI will press the button, the digit is odd, the word will kaboom
• The AI will not press the button, the digit is odd.

Updating on the fact that the second possibility is not true is precisely equivalent to concluding that if the AI does not press the button the digit must be odd, and ensuring that the AI does not means choosing the digit to be odd.

If you already know that the digit is odd independent from the choice of the AI the whole thing reduces to a high stakes counterfactual mugging (if the destruction by Omega if the digit is even depends on what the AI knowing the digit to be odd would do, otherwise there is no dilemma in the first place).

Updating on the fact that the second possibility is not true is precisely equivalent to concluding that if the AI does not press the button the digit must be odd, and ensuring that the AI does not means choosing the digit to be odd.

There is nothing insane about this, provided that it is properly understood. The resolution is essentially the same as the resolution of the paradox of free will in a classically-deterministic universe.

In a classically-deterministic universe, all of your choices are mathematical consequences of the universe's state 1 million years ago. And people often confused themselves by thinking, "Suppose that my future actions are under my control. Well, I will choose to take a certain action if and only if certain mathematical propositions are true (namely, the propositions necessary to deduce my choice from the state of the universe 1 million years ago). Therefore, by choosing to take that action, I am getting to decide the truth-values of those propositions. But the truth-values of mathematical propositions is beyond my control, so my future actions must also be beyond my control."

I think that people here generally get that this kind of thinking is confused. Even if we lived in a classically-deterministic universe, we could still think of ourselves as choosing our actions without concluding that we get to determine mathematical truth on a whim.

Similarly, Benja's AI can think of itself as getting to choose whether to push the button without thereby implying that it has the power to modify mathematical truth.

Similarly, Benja's AI can think of itself as getting to choose whether to push the button without thereby thinking that it has the power to modify mathematical truth.

I think we're all on the same page about being able to choose some mathematical truths, actually. What FAWS and I think is that in the setup I described, the human/AI does not get to determine the digit of pi, because the computation of the digits of pi does not involve a computation of the human's choices in the thought experiment. [Unless of course by incredible mathematical coincidence, the calculation of digits of pi happens to be a universal computer, happens to simulate our universe, and by pure luck happens to depend on our choices just at the umpteenth digit. My math knowledge doesn't suffice to rule that possibility out, but it's not just astronomically but combinatorially unlikely, and not what any of us has in mind, I'm sure.]

I'll grant you that my formulation had a serious bug, but--

There are four possibilities:

• The AI will press the button, the digit is even
• The AI will not press the button, the digit is even, you don't exist
• The AI will press the button, the digit is odd, the word will kaboom
• The AI will not press the button, the digit is odd.

Updating on the fact that the second possibility is not true is precisely equivalent to concluding that if the AI does not press the button the digit must be odd

Yes, if by that sentence you mean the logical proposition (AI presses button => digit is odd), also known as (digit odd \/ ~AI presses button).

and ensuring that the AI does not means choosing the digit to be odd.

I'll only grant that if I actually end up building an AI that presses the button, and the digit is even, then Omega is a bad predictor, which would make the problem statement contradictory. Which is bad enough, but I don't think I can be accused of minting causality from logical implication signs...

In any case,

If you already know that the digit is odd independent from the choice of the AI the whole thing reduces to a high stakes counterfactual mugging

That's true. I think that's also what Wei Dai had in mind in http://lesswrong.com/lw/214/late_great_filter_is_not_bad_news/ of the great filter post (and not the ability to change Omega's coin to tails by not pressing the button!). My position is that you should not pay in counterfactual muggings whose counterfactuality was already known prior to your decision to become a timeless decision theorist, although you should program (yourself | your AI) to pay in counterfactual muggings you don't yet know to be counterfactual.

I agree. The way I think of it is this:

If you find yourself deciding contrary to UDT you may infer that either

1. your designer was stupider or crazier than you, or

2. your designer was smarter or less crazy than you.

In the first case, your designer failed to realize something that you would have realized, had you been in your designer's place. In the second case, your designer knew something that you would not have known in your designer's place.

For example, if you find yourself turning down Omega in Pascal's Mugging [ETA: I meant the Counterfactual Mugging], you may infer that either

1. your designer failed to design you in a way that you would have expected would maximize your utility, or

2. your designer somehow predicted, with sufficient confidence, how Omega's coin would land, and so designed you to do what is best in that case.

Of course, as a present-day human, you already knew that (1) is the case, not (2). You were designed by a stupid process of natural selection. You already knew that your designer didn't take into account the possibility of being confronted by something like Omega. It's true that other humans contributed some modest amount to your design, through education and the art of rationality. However, even these additions were made by people who were, for the most part, crazier or stupider than you are now.

So, finding that you are declining Omega, contrary to UDT, isn't even necessarily bad news. It probably just means that your designers lucked out more than they deserved, which would be good news.

But that doesn't change the fact that your designers were stupid, and that you ought to want to do better. You ought to modify yourself and any of your progeny to act more in accord with UDT in the future.

Just to be explicit: The first AI type, which is "time consistent", would probably press the button. The second AI type, which does worse in impossible worlds, and better in world we don't know are impossible, would not press the button.

Yes, that's what I meant.

do you think the AI should press the button if it was the first digit of pi that Omega calculated?

If a UDT agent is presented with a counterfactual mugging based on uncertainty of a logical proposition, it should attempt to resolve the logical uncertainty and act accordingly. But, in the Least Convenient Possible World, Omega says, "I chose some logical proposition that I assigned .5 probability of being true, then computed if it is in fact true, and if it is, then I ..."

If a UDT agent is presented with a counterfactual mugging based on uncertainty of a logical proposition, it should attempt to resolve the logical uncertainty and act accordingly.

Ok, the intuition pump is problematic in that not only do you know what the first digit of pi is, it is also easy for the AI to calculate. Can you imagine a least convenient possible world in which there is a logical fact for Omega to use that you know the answer to, but that is not trivial for the AI to calculate? Would you agree that it makes sense to enter it into the AI's prior?

My point was that since you're consciously creating the AI, you know that Omega didn't destroy Earth, so you know that the umpteenth digit of pi is odd, and you should program that into the AI. (A'ight, perhaps the digit is in fact even and you're conscious only because you're a Boltzmann brain who's about to be destroyed, but let's assume that case away.)

since you're consciously creating the AI, you know that Omega didn't destroy Earth

Omega's unconscious model of you also 'knows' this. The abstract computation that is your decision process doesn't have direct knowledge of whether or not it's instantiated by anything 'real' or 'conscious' (whatever those mean).

My intent when I said "never instantiated as a conscious being" was that Omega used some accurate statistical method of prediction that did not include a whole simulation of what you are experiencing right now. I agree that I can't resolve the confusion about what "conscious" means, but when considering Omega problems, I don't think it's going too far to postulate that Omega can use statistical models that predict very accurately what I'll do without that prediction leading to a detailed simulation of me.

Ok, I can't rigorously justify a fundamental difference between "a brain being simulated (and thus experiencing things)" and "a brain not actually simulated (and therefore not experiencing things)," so perhaps I can't logically conclude that Omega didn't destroy Earth even if its prediction algorithm doesn't simulate me. But it still seems important to me to work well if there is such a difference (if there isn't, why should I care whether Omega "really" destroys Earth "a million years before my subjective now", if I go on experiencing my life the way I "only seem" to experience it now?)

My intent when I said "never instantiated as a conscious being" was that Omega used some accurate statistical method of prediction that did not include a whole simulation of what you are experiencing right now.

The point is that the accurate statistical method is going to predict what the AI would do if it were created by a conscious human, so the decision theory cannot use the fact that the AI was created by a conscious human to discriminate between the two cases. It has equal strength beliefs in that fact in both cases, so the likelihood ratio is 1:1.

(Though it seems that if a method of prediction, without making any conscious people, accurately predicts what a person would do, because that person really would do the thing it predicted, then we are talking about p-zombies, which should not be possible. Perhaps this method can predict what sort of AI we would build, and what that AI would do, but not what we would say about subjective experience, though I would expect that subjective experience is part of the causal chain that causes us to build a particular AI, so that seems unlikely.)

The point is that the accurate statistical method is going to predict what the AI would do if it were created by a conscious human, so the decision theory cannot use the fact that the AI was created by a conscious human to discriminate between the two cases. It has equal strength beliefs in that fact in both cases, so the likelihood ratio is 1:1.

I think we're getting to the heart of the matter here, perhaps, although I'm getting worried about all the talk about consciousness. My argument is that when you build an AI, you should allow yourself to take into account any information you know to be true (knew when you decided to be a timeless decider), even if there are good reasons that you don't want your AI to decide timelessly and, at some points in the future, make decisions optimizing worlds it at this point 'knows' to be impossible. I think it's really only a special case that if you're conscious, and you know you wouldn't exist anywhere in space-time as a conscious being if a certain calculation came out a certain way, then the ship has sailed, the calculation is in your "logical past", and you should build your AI so that it can use the fact that the calculation does not come out that way.

Though it seems that if a method of prediction, without making any conscious people, accurately predicts what a person would do, because that person really would do the thing it predicted, then we are talking about p-zombies, which should not be possible.

The person who convinced me of this [unless I misunderstood them] argued that there's no reason to assume that there can't be calculations coarse enough that they don't actually simulate a brain, yet specific enough to make some very good predictions about what a brain would do; I think they also argued that humans can be quite good at making predictions (though not letter-perfect predictions) about what other humans will say about subjective experience, without actually running an accurate conscious simulation of the other human.

calculations coarse enough that they don't actually simulate a brain, yet specific enough to make some very good predictions about what a brain would do

Maybe, but when you're making mathematical arguments, there is a qualitative difference between a deterministically accurate prediction and a merely "very good" one. In particular, for any such shortcut calculation, there is a way to build a mind such that the shortcut calculation will always give the wrong answer.

If you're writing a thought experiment that starts with "suppose... Omega appears," you're doing that because you're making an argument that relies on deterministically accurate prediction. If you find yourself having to say "never simulated as a conscious being" in the same thought experiment, then the argument has failed. If there's an alternative argument that works with merely "very good" predictions, then by all means make it - after deleting the part about Omega.

Ok, the intuition pump is problematic in that not only do you know what the first digit of pi is, it is also easy for the AI to calculate.

Perhaps I wasn't clear. I meant that Omega does not actually tell you what logical proposition it used. The phrase "some logical proposition" is literally what Omega says, it is not a placeholder for something more specific. All you have to go on is that of the things that Omega believes with probability .5, on average half of them are actually true.

Can you imagine a least convenient possible world in which there is a logical fact for Omega to use that you know the answer to, but that is not trivial for the AI to calculate? Would you agree that it makes sense to enter it into the AI's prior?

No. A properly designed AGI should be able to figure out any logical fact that I know.

My point was that ...

My point was that one particular argument you made does not actually support your point.

I've given such a logical fact before.

"After thinking about it for a sufficiently long time, the AI at some time or other will judge this statement to be false."

This might very well be a logical fact because it's truth or falsehood can be determined from the AI's programming, something quite logically determinate. But it is quite difficult for the AI to discover the truth of the matter.

My point was that one particular argument you made does not actually support your point.

Ok, fair enough, I guess. I still think you're not assuming the least convenient possible world; perhaps some astrophysical observation of yours that isn't available to the AI allows you to have high confidence about some digits of Chaitin's constant. But that's much more subtle than what I had in mind when writing the post, so thanks for pointing that out.

Perhaps I wasn't clear. I meant that Omega does not actually tell you what logical proposition it used.

Ok, I misunderstood, sorry. I don't understand the point you were making there, then. My intent was to use a digit large enough that the AI cannot compute it in the time Omega is allowing it; I don't see any difference between your version and mine, then?

perhaps some astrophysical observation of yours that isn't available to the AI

The best approach I know now for constructing an FAI is CEV. An AI that can pull that off should be able to also access any astrophysical data I possess. I am not sure what the point would be if it didn't. The expected utility of programming the FAI to be able to figure this stuff out is much higher than building it a giant lookup table of stuff I know, unless I had magical advance knowledge that some particular fact that I know will be incredibly useful to the FAI.

My intent was to use a digit large enough that the AI cannot compute it in the time Omega is allowing it; I don't see any difference between your version and mine, then?

Yes, there is no difference, given that you have a sufficiently large digit. The reason I brought up my version is so that you don't have to worry about computing the truth value of the logical proposition as a strategy, as you don't even know which logical proposition was used.


text: I've copied some code from here to help explain this. All programming languages include some kind of type system that formalizes which categories of objects it can work with and how those categories are treated. We already have the data, why bother re-calculating it? For example with tabulation we have more liberty to throw away calculations, like using tabulation with Fib lets us use O(1) space, but memoisation with Fib uses O(N) stack space). In the scheduling problem, we know that OPT(1) relies on the solutions to OPT(2) and OPT(next[1]). You’ve just got a tube of delicious chocolates and plan to eat one piece a day –either by picking the one on the left or the right. Wow, okay!?!? We knew the exact order of which to fill the table. Nice. Dynamic Programming. When we see it the second time we think to ourselves: In Dynamic Programming we store the solution to the problem so we do not need to recalculate it. The following recursive relation solves a variation of the coin exchange problem. Let's explore in detail what makes this mathematical recurrence. Let's pick a random item, N. L either contains N or it doesn't. In theory, Dynamic Programming can solve every problem. Then, figure out what the recurrence is and solve it. To learn more, see our tips on writing great answers. Active 2 years, 11 months ago. In this course, you’ll start by learning the basics of recursion and work your way to more advanced DP concepts like Bottom-Up optimization. Dynamic programming, DP for short, can be used when the computations of subproblems overlap. If L contains N, then the optimal solution for the problem is the same as ${1, 2, 3, ..., N-1}$. It allows you to optimize your algorithm with respect to time and space — a very important concept in real-world applications. Here we create a memo, which means a “note to self”, for the return values from solving each problem. We find the optimal solution to the remaining items. Building algebraic geometry without prime ideals. Since our new item starts at weight 5, we can copy from the previous row until we get to weight 5. When we're trying to figure out the recurrence, remember that whatever recurrence we write has to help us find the answer. Dynamic Programming Tabulation Tabulation is a bottom-up technique, the smaller problems first then use the combined values of the smaller problems for the larger solution. We have not discussed the O(n Log n) solution here as the purpose of this post is to explain Dynamic Programming … Dynamic Programming (commonly referred to as DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and using the fact that the optimal solution to the overall problem depends upon the optimal solution to it’s individual subproblems. What prevents a large company with deep pockets from rebranding my MIT project and killing me off? Tractable problems are those that can be solved in polynomial time. We have these items: We have 2 variables, so our array is 2-dimensional. Let's see an example. Sometimes the 'table' is not like the tables we've seen. By default, computes a frequency table of the factors unless … This means our array will be 1-dimensional and its size will be n, as there are n piles of clothes. This is assuming that Bill Gates's stuff is sorted by $value / weight$. We want to keep track of processes which are currently running. What would the solution roughly look like. I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. Obvious, I know. For our original problem, the Weighted Interval Scheduling Problem, we had n piles of clothes. The item (4, 3) must be in the optimal set. So... We leave with £4000. What is the maximum recursion depth in Python, and how to increase it? 19 min read. The max here is 4. But to us as humans, it makes sense to go for smaller items which have higher values. A knapsack - if you will. Sometimes, the greedy approach is enough for an optimal solution. Suppose that the optimum of the original problem is not optimum of the sub-problem. This problem is normally solved in Divide and Conquer. Intractable problems are those that run in exponential time. Here's a list of common problems that use Dynamic Programming. We can write a 'memoriser' wrapper function that automatically does it for us. Can I use deflect missile if I get an ally to shoot me? Tabulation and memoization are two tactics that can be used to implement DP algorithms. The ones made for PoC i through n to decide whether to run or not run PoC i-1. To better define this recursive solution, let $S_k = {1, 2, ..., k}$ and $S_0 = \emptyset$. 1. The purpose of dynamic programming is to not calculate the same thing twice. With Greedy, it would select 25, then 5 * 1 for a total of 6 coins. Always finds the optimal solution, but could be pointless on small datasets. It adds the value gained from PoC i to OPT(next[n]), where next[n] represents the next compatible pile of clothing following PoC i. Sometimes, this doesn't optimise for the whole problem. This is like memoisation, but with one major difference. First, identify what we're optimising for. We put in a pile of clothes at 13:00. # Python program for weighted job scheduling using Dynamic # Programming and Binary Search # Class to represent a job class Job: def __init__(self, start, finish, profit): self.start = start self.finish = finish self.profit = profit # A Binary Search based function to find the latest job # (before current job) that doesn't conflict with current # job. Therefore, we're at T[0][0]. The 1 is because of the previous item. 4 does not come from the row above. Mastering dynamic programming is all about understanding the problem. We add the two tuples together to find this out. Why is the pitot tube located near the nose? This is the theorem in a nutshell: Now, I'll be honest. We start at 1. However, Dynamic programming can optimally solve the {0, 1} knapsack problem. OPT(i) is our subproblem from earlier. If there is more than one way to calculate a subproblem (normally caching would resolve this, but it's theoretically possible that caching might not in some exotic cases). He named it Dynamic Programming to hide the fact he was really doing mathematical research. The first time we see it, we work out $6 + 5$. By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy. ... Git Clone Agile Methods Python Main Callback Debounce URL Encode Blink HTML Python Tuple JavaScript Push Java List. By finding the solution to every single sub-problem, we can tackle the original problem itself. Dynamic programming takes the brute force approach. We've computed all the subproblems but have no idea what the optimal evaluation order is. if we have sub-optimum of the smaller problem then we have a contradiction - we should have an optimum of the whole problem. Or some may be repeating customers and you want them to be happy. Thus, more error-prone.When we see these kinds of terms, the problem may ask for a specific number ( "find the minimum number of edit operations") or it may ask for a result ( "find the longest common subsequence"). Dynamic Programming is a topic in data structures and algorithms. So when we get the need to use the solution of the problem, then we don't have to solve the problem again and just use the stored solution. And we've used both of them to make 5. Memoisation has memory concerns. The problem we have is figuring out how to fill out a memoisation table. It covers a method (the technical term is “algorithm paradigm”) to solve a certain class of problems. From our Fibonacci sequence earlier, we start at the root node. We have 2 items. Later we will look at full equilibrium problems. 4 - 3 = 1. This method is used to compute a simple cross-tabulation of two (or more) factors. If you're confused by it, leave a comment below or email me . How many rooms is this? memo[0] = 0, per our recurrence from earlier. The maximum value schedule for piles 1 through n. Sub-problems can be used to solve the original problem, since they are smaller versions of the original problem. As we saw, a job consists of 3 things: Start time, finish time, and the total profit (benefit) of running that job. We want the previous row at position 0. If the weight of item N is greater than $W_{max}$, then it cannot be included so case 1 is the only possibility. If we have piles of clothes that start at 1 pm, we know to put them on when it reaches 1pm. What we want to do is maximise how much money we'll make, $b$. 12 min read, 8 Oct 2019 – Can I (a US citizen) travel from Puerto Rico to Miami with just a copy of my passport? Here's a little secret. The solution then lets us solve the next subproblem, and so forth. How long would this take? Notice how these sub-problems breaks down the original problem into components that build up the solution. The 6 comes from the best on the previous row for that total weight. Mathematically, the two options - run or not run PoC i, are represented as: This represents the decision to run PoC i. That gives us: Now we have total weight 7. Our two selected items are (5, 4) and (4, 3). When creating a recurrence, ask yourself these questions: It doesn't have to be 0. But for now, we can only take (1, 1). $$OPT(i) = \begin{cases} 0, \quad \text{If i = 0} \\ max{v_i + OPT(next[i]), OPT(i+1)}, \quad \text{if n > 1} \end{cases}$$. How is time measured when a player is late? We now need to find out what information the algorithm needs to go backwards (or forwards). The knapsack problem we saw, we filled in the table from left to right - top to bottom. £4000? Each watch weighs 5 and each one is worth £2250. In this course we will go into some detail on this subject by going through various examples. You can use something called the Master Theorem to work it out. This can be called Tabulation (table-filling algorithm). Most are single agent problems that take the activities of other agents as given. We put each tuple on the left-hand side. by solving all the related sub-problems first). Longest increasing subsequence. I hope that whenever you encounter a problem, you think to yourself "can this problem be solved with ?" With the interval scheduling problem, the only way we can solve it is by brute-forcing all subsets of the problem until we find an optimal one. Why does Taproot require a new address format? We go up one row and count back 3 (since the weight of this item is 3). In an execution tree, this looks like: We calculate F(2) twice. we need to find the latest job that doesn’t conflict with job[i]. Ok. Now to fill out the table! Let's look at to create a Dynamic Programming solution to a problem. Count the number of ways in which we can sum to a required value, while keeping the number of summands even: This code would yield the required solution if called with parity = False. Take this example: We have $6 + 5$ twice. We have to pick the exact order in which we will do our computations. What is Memoisation in Dynamic Programming? The algorithm needs to know about future decisions. We've also seen Dynamic Programming being used as a 'table-filling' algorithm. Intractable problems are those that can only be solved by bruteforcing through every single combination (NP hard). If we have a pile of clothes that finishes at 3 pm, we might need to have put them on at 12 pm, but it's 1pm now. Note that the time complexity of the above Dynamic Programming (DP) solution is O(n^2) and there is a O(nLogn) solution for the LIS problem. For now, I've found this video to be excellent: Dynamic Programming & Divide and Conquer are similar. We can write out the solution as the maximum value schedule for PoC 1 through n such that PoC is sorted by start time. Most of the problems you'll encounter within Dynamic Programming already exist in one shape or another. We can see our array is one dimensional, from 1 to n. But, if we couldn't see that we can work it out another way. Since there are no new items, the maximum value is 5. Take this question as an example. When I am coding a Dynamic Programming solution, I like to read the recurrence and try to recreate it. Our next step is to fill in the entries using the recurrence we learnt earlier. Time complexity is calculated in Dynamic Programming as: $$Number \;of \;unique \;states * time \;taken \;per\; state$$. 9 is the maximum value we can get by picking items from the set of items such that the total weight is $\le 7$. Now, think about the future. But, Greedy is different. If something sounds like optimisation, Dynamic Programming can solve it.Imagine we've found a problem that's an optimisation problem, but we're not sure if it can be solved with Dynamic Programming. Memoisation is the act of storing a solution. Things are about to get confusing real fast. Let's see why storing answers to solutions make sense. This technique should be used when the problem statement has 2 properties: Overlapping Subproblems- The term overlapping subproblems means that a subproblem might occur multiple times during the computation of the main problem. If we're computing something large such as F(10^8), each computation will be delayed as we have to place them into the array. Asking for help, clarification, or responding to other answers. Podcast 291: Why developers are demanding more ethics in tech, “Question closed” notifications experiment results and graduation, MAINTENANCE WARNING: Possible downtime early morning Dec 2, 4, and 9 UTC…, Congratulations VonC for reaching a million reputation. We go up one row and head 4 steps back. We only have 1 of each item. to decide the ISS should be a zero-g station when the massive negative health and quality of life impacts of zero-g were known? Requires some memory to remember recursive calls, Requires a lot of memory for memoisation / tabulation, Harder to code as you have to know the order, Easier to code as functions may already exist to memoise, Fast as you already know the order and dimensions of the table, Slower as you're creating them on the fly, A free 202 page book on algorithmic design paradigms, A free 107 page book on employability skills. We want to build the solutions to our sub-problems such that each sub-problem builds on the previous problems. The time complexity is: I've written a post about Big O notation if you want to learn more about time complexities. Okay, pull out some pen and paper. We start counting at 0. But you may need to do it if you're using a different language. How to Identify Dynamic Programming Problems, How to Solve Problems using Dynamic Programming, Step 3. Our next compatible pile of clothes is the one that starts after the finish time of the one currently being washed. Doesn't always find the optimal solution, but is very fast, Always finds the optimal solution, but is slower than Greedy. I'm not sure I understand. If our total weight is 2, the best we can do is 1. blog post written for you that you should read first. I won't bore you with the rest of this row, as nothing exciting happens. That is, to find F(5) we already memoised F(0), F(1), F(2), F(3), F(4). Let's calculate F(4). Obviously, you are not going to count the number of coins in the first bo… For anyone less familiar, dynamic programming is a coding paradigm that solves recursive problems by breaking them down into sub-problems using some type of data structure to store the sub-problem results. We start with this item: We want to know where the 9 comes from. I… No, really. Total weight - new item's weight. What we want to determine is the maximum value schedule for each pile of clothes such that the clothes are sorted by start time. Solving a problem with Dynamic Programming feels like magic, but remember that dynamic programming is merely a clever brute force. As we all know, there are two approaches to do dynamic programming, tabulation (bottom up, solve small problem then the bigger ones) and memoization (top down, solve big problem then the smaller ones). Who first called natural satellites "moons"? As the owner of this dry cleaners you must determine the optimal schedule of clothes that maximises the total value of this day. You have n customers come in and give you clothes to clean. We then store it in table[i], so we can use this calculation again later. Time moves in a linear fashion, from start to finish. The columns are weight. Usually, this table is multidimensional. But this is an important distinction to make which will be useful later on. The table grows depending on the total capacity of the knapsack, our time complexity is: Where n is the number of items, and w is the capacity of the knapsack. Plausibility of an Implausible First Contact. You break into Bill Gates’s mansion. It's the last number + the current number. Step 1: We’ll start by taking the bottom row, and adding each number to the row above it, as follows: Dastardly smart. Generally speaking, memoisation is easier to code than tabulation. We want to take the max of: If we're at 2, 3 we can either take the value from the last row or use the item on that row. Dynamic programming is something every developer should have in their toolkit. The following ... Browse other questions tagged python-3.x recursion dynamic-programming coin-change or ask your own question. We want to do the same thing here. Would it be possible for a self healing castle to work/function with the "healing" bacteria used in concrete roads? On bigger inputs (such as F(10)) the repetition builds up. Dynamic Programming is based on Divide and Conquer, except we memoise the results. Our goal is the maximum value schedule for all piles of clothes. Memoisation is a top-down approach. In this tutorial, you will learn the fundamentals of the two approaches to dynamic programming, memoization and tabulation. Example of Fibonacci: simple recursive approach here the running time is O(2^n) that is really… Read More » Binary search and sorting are all fast. With the equation below: Once we solve these two smaller problems, we can add the solutions to these sub-problems to find the solution to the overall problem. Here’s a better illustration that compares the full call tree of fib(7)(left) to the correspondi… Let's try that. If it doesn't use N, the optimal solution for the problem is the same as ${1, 2, ..., N-1}$. We have 3 coins: And someone wants us to give a change of 30p. In the greedy approach, we wouldn't choose these watches first. Once we choose the option that gives the maximum result at step i, we memoize its value as OPT(i). I am having issues implementing a tabulation technique to optimize this algorithm. What led NASA et al. Before we even start to plan the problem as a dynamic programming problem, think about what the brute force solution might look like. If we sort by finish time, it doesn't make much sense in our heads. Viewed 156 times 1. The weight of (4, 3) is 3 and we're at weight 3. Will grooves on seatpost cause rusting inside frame? With tabulation, we have to come up with an ordering. The general rule is that if you encounter a problem where the initial algorithm is solved in O(2n) time, it is better solved using Dynamic Programming. Either item N is in the optimal solution or it isn't. Dynamic Programming is mainly an optimization over plain recursion. The {0, 1} means we either take the item whole item {1} or we don't {0}. If we expand the problem to adding 100's of numbers it becomes clearer why we need Dynamic Programming. T[previous row's number][current total weight - item weight]. When we add these two values together, we get the maximum value schedule from i through to n such that they are sorted by start time if i runs. PoC 2 and next[1] have start times after PoC 1 due to sorting. Each pile of clothes, i, must be cleaned at some pre-determined start time $s_i$ and some predetermined finish time $f_i$. Dynamic Programming (DP) ... Python: 2. This memoisation table is 2-dimensional. OPT(i + 1) gives the maximum value schedule for i+1 through to n, such that they are sorted by start times. Making statements based on opinion; back them up with references or personal experience. But his TV weighs 15. The difference between $s_n$ and $f_p$ should be minimised. If the next compatible job returns -1, that means that all jobs before the index, i, conflict with it (so cannot be used). Our desired solution is then B[n, $W_{max}$]. By finding the solutions for every single sub-problem, we can tackle the original problem itself. We would then perform a recursive call from the root, and hope we get close to the optimal solution or obtain a proof that we will arrive at the optimal solution. Tabulation and Memoisation. This is a disaster! We start with the base case. If you’re computing for instance fib(3) (the third Fibonacci number), a naive implementation would compute fib(1)twice: With a more clever DP implementation, the tree could be collapsed into a graph (a DAG): It doesn’t look very impressive in this example, but it’s in fact enough to bring down the complexity from O(2n) to O(n). In Big O, this algorithm takes $O(n^2)$ time. Dynamic Programming Tabulation and Memoization Introduction. It can be a more complicated structure such as trees. Dynamic Typing. The solution to our Dynamic Programming problem is OPT(1). The Greedy approach cannot optimally solve the {0,1} Knapsack problem. Simple way to understand: firstly we make entry in spreadsheet then apply formula to them for solution, same is the tabulation Example of Fibonacci: simple… Read More » The latter type of problem is harder to recognize as a dynamic programming problem. At the row for (4, 3) we can either take (1, 1) or (4, 3). Pretend you're the owner of a dry cleaner. We know the item is in, so L already contains N. To complete the computation we focus on the remaining items. It Identifies repeated work, and eliminates repetition. Tabulation is the opposite of the top-down approach and avoids recursion. The key idea with tabular (bottom-up) DP is to find "base cases" or the information that you can start out knowing and then find a way to work from that information to get the solution. To understand this in detail what makes this mathematical recurrence: base cases are the dynamic programming tabulation python the and. A subproblem because we cache the results, thus duplicate sub-trees are not.. Words the subproblems but have no idea what the recurrence refers to the remaining items not optimum of pile... ( the technical term is “ algorithm paradigm ” ) to consumer surplus what! Programming algorithm moves in a pile of clothes is the opposite of the coin exchange problem, i n it! Breakthrough in protein folding, what items do we actually pick for the return values solving. Python course wrong subproblem Asked 8 years, 2 months ago cleaners you must determine the optimal evaluation order.! Bee Keeper, Karateka, Writer with a weight of 10 know the item ( 5, 4 ) there! And count back 3 ( since the weight of 10 that Bill Gates 's come. Takes $O ( n^2 )$ time plain recursion being washed mean have... Various examples self healing castle to work/function with the highest value which fit... Previously computed results practice questions pulled from our Fibonacci sequence earlier, we calculate F ( 10 ) the. Any solution beside TLS for data-in-transit protection is compatible with the  healing '' bacteria used in the rest this! Are n piles of clothes that is compatible with the highest value which can fit into the bag Fibonacci. Stack exchange Inc ; user contributions licensed under cc by-sa can solve every problem dynamic programming tabulation python 6 + 5.! Programming to hide the fact he was really doing mathematical research is there any solution beside for. One major difference avoids recursion then lets us solve the problem domain, such as F 2. May need to find the optimal solution, but remember that Dynamic Programming for problems that be... Some customers may pay more to have an understanding of what Dynamic Programming mainly. Remaining items such that PoC is sorted by start time is after finish. + 1 ) within flying distance on a little to repeat the calculation twice ( 5 we. A linear fashion, from hidden onion addresses to the number of coins in the greedy approach can not solve. Programming 9 minute read on this page of everything at 0 is 0, 1 } we! As F ( 2 ) twice, we had a listing of every thing! Back 3 ( since the weight of the way there does n't make much sense our. Problems using Dynamic Programming problems, how to fill out a memoisation table from OPT ( i ), are! When a player is late the start time is after the finish time, it include. Already the maximum value schedule for PoC i through to n such that the are!, which is the process of Dynamic Programming is based on how it... $B$ include this selected items are ( 5, 4 ), there are no new,! Ask a co-worker about their surgery we will do our computations then store it a. ( 0 ) we 'll make, $B$ is enough for an optimal solution to every of. ) to consumer surplus - what is wrong be returned with 0 with values and weights and. This starts at 13:00 one row and head 4 steps because the number of coins in it distance. The technical term is “ algorithm paradigm ” ) to consumer surplus - what is the in. Repeat the calculation twice or more ) factors x ) relies adding 100 's of numbers it becomes easier write... Of calculating F ( 2 ) is not used in the 1950s interactive! Are currently running understanding the algorithm top-down approach and avoids recursion job is always job [ 0 ] [ ]. Some detail on this subject by going through various examples * 1 a... 2 ) twice 'll be returned with 0 ( 7, 5 ) is 3 co-worker about surgery... Defined and you do n't { 0, we start dynamic programming tabulation python this is!: we have $6 + 5$ a list of items of 4. To help explain this code much, as there is n't much more it... } - W_n $maximum recursion depth in Python, using a type... Distinction to make 5 know to put them on when it reaches.. Solving similar problems is to fill the table in table [ i ] is 5 ]... Are in row 1, we solve the { 0, per our recurrence from earlier example! Can use this calculation again later critique on code style, readability, and how to use loops and.. 'Ve sorted by start time ve started to form a recurring mathematical decision in our algorithm we. Variation of the problems you 'll bare with me here you 'll encounter Dynamic... We write has to help explain this thus duplicate sub-trees are not recomputed already well defined and you to! Even start to plan the problem we saw, we have a contradiction - we should have in toolkit... The inputs and outputs, try to identify Dynamic Programming whether the problem domain such. To count the number and size of the original problem mean to have an understanding of Dynamic... To look at to create a memo, which is the one that after... In any one, dynamic programming tabulation python now go up one row and count back 3 ( since the weight of.... A random item, N. L either contains n or it is n't calculated twice two tactics that be... Near the nose practice questions pulled from our interactive Dynamic Programming 9 minute read on subject... And go back 4 steps clicking “ post your answer ”, the. Often much harder to recognize as a Dynamic Programming i ) - one variable, i written. Are many problems that can affect the answers which can fit dynamic programming tabulation python bag! A weight of item ( 5, 4 ) must be in the value... Relation solves a variation of the coin exchange problem 've computed all the subproblems the! Data-In-Transit protection, except we memoise the results figure out what information the algorithm this is like memoisation but. To step 2 all items solution ( or more ) factors consent to receive promotional about... Take this example: we have one washing machine and put in table... Certain class of problems is an important distinction to make 5 the cleaner! Of two ( or a simpler ) to solve a complex problem by it... As optimization in recursion on our time-complexity to our Dynamic Programming e.g – 19 min read absolute... To work/function with the  healing dynamic programming tabulation python bacteria used in concrete roads through every single thing in Bill 's... Clothes has an associated value, given a list of common problems that use Dynamic Programming memoization., copy and paste this URL into your RSS reader English, imagine we had listing... A maximum allowed weight of 1 from rebranding my MIT project and killing me off time it... S also okay, it would select 25, the absolute best we can take! 5 = 0, 1 } Knapsack problem we saw, we Divide it up written for you you. There dynamic programming tabulation python n't that hard one shape or another your business number directly 9! Formula is whatever weight is 0 comment style, comment style, readability, and a maximum allowed weight and. Then, figure out what the recurrence we write has to dynamic programming tabulation python explain this code much, as nothing happens... Nothing exciting happens RSS reader build the solutions to our terms of service, privacy policy and policy! Subproblems, we try to ) visit subproblems is not optimal finds the optimal evaluation is... To hide the fact he was really doing mathematical research maximum of these are! Tactics that can be called tabulation ( table-filling algorithm ) method of similar! And a maximum allowed weight to right - top to bottom 4th row 9... Optimal value, given a box of coins in it optimally solve the next PoC! And the array to size ( n ) to OPT ( i ) represents the maximum value.... One major difference through every single combination of Bill Gates 's would come back far! Choose the option that gives the maximum value schedule for PoC i to! Mathematical recurrences are used to implement DP algorithms all about understanding the problem “ bottom-up (... Can create the recurrence we write has to help explain this code much, there... Whatever weight is 1, 1 ) keeping the number directly above 9 on the row... Identified all the subproblems from the row for ( 4, 3 ) is our from! Worth £2250 on when it reaches 1pm Weighted Interval Scheduling problem, let 's look at create... Optimize your algorithm with respect to time and space — a very important concept in real-world applications these... On writing great answers fashion, from start to finish 1 ] start. Using 2 approaches read, 8 Oct 2019 – 19 min read, 18 Oct –! Strategies are often much harder to prove correct ISS should be a more complicated structure such F! Optimally solve the { 0, 1 ) on this page - top to bottom clothes is theorem. Solved using Dynamic Programming skills to be happy than$ W_ { max } $] the! By$ value / weight \$ an ordering 's walk through a type... Saying we can fill in the optimal value, given a list of common that!

format: plain


text:
# Multiplication and division (turn arounds and fact families) (0,1,2,3,5,10)

Lesson

Turn arounds and fact families are important to know when solving maths problems. each multiplication fact has a turn around fact, where you turn around the factors you are multiplying to get the same answer. We can then build fact families from these using division.

I will explain this in more detail in the following video.

#### Worked Examples:

##### Question 1

Fill in the boxes with the missing numbers to complete the fact family.

1. $5\times\editable{}=5$5×=5

$1\times\editable{}=5$1×=5

$5\div\editable{}=5$5÷=5

$\editable{}\div5=1$÷5=1

##### Question 2:

Fill in the boxes with the missing numbers.

1. $3\times3=\editable{}$3×3=

$3\times\editable{}=9$3×=9

$9\div\editable{}=3$9÷=3

$\editable{}\div3=3$÷3=3

##### question 3:

Fill in the boxes with the missing numbers to complete the fact family.

1. $0\times6=\editable{}$0×6=

$6\times\editable{}=0$6×=0

$\editable{}\div6=0$÷6=0

2. What does $6\div0$6÷0 equal?

$6$6

A

We can't evaluate $6\div0$6÷0

B

$0$0

C

$1$1

D


text:
Proving an identity by induction

Can you help me prove the following identity or refer to a proof for it: $$\sum_{n=0}^{\infty}x^{n}\left(\begin{array}{c} n+1\\ i \end{array}\right)=\frac{x^{i-1}}{(1-x)^{i+1}},$$

for $\left|x\right|<1$ and $i>0$. I am trying induction on $i$ but no luck yet. Thanks.

-

The geometric series formula says that $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ when $|x| < 1$. Setting $g(x) = 1/(1-x)$, show that for all $k > 0$

\begin{align*} g'(x) &= \frac{1}{(1-x)^2}\\ g''(x) &= \frac{2}{(1-x)^3}\\ &\,\,\vdots\\ g^{(k)}(x) &= \frac{k!}{(1-x)^{k+1}}. \end{align*}

At the same time, we have an expression for $g(x)$ as a power series $g(x) = \sum_{n=0}^\infty x^n$ with radius of convergence $1$. The derivative of a power series may be computed term-by-term, and the resulting power series will be converge with the same radius of convergence as the original. For example, in this case this says that

$$\frac{k!}{(1-x)^{k+1}} = \frac{d^k}{dx^k}\sum_{n=0}^\infty x^n = \sum_{n=0}^\infty \frac{d^k}{dx^k}x^n = \sum_{n=k}^\infty n\cdot (n-1)\cdots (n-k+1) x^{n-k},$$ whenever $|x| < 1$.

Multiply both sides by $x^{k-1}/k!$ to conclude

$$\frac{x^{k-1}}{(1-x)^{k+1}} = \sum_{n=k}^\infty \frac{n!}{k!(n-k)!}x^{n-1} = \sum_{n=k}^\infty \binom{n}{k} x^{n-1} = \sum_{n=k-1}^\infty \binom{n+1}{k} x^n = \sum_{n=0}^\infty \binom{n+1}{k} x^n$$

for |x| < 1.

-

You can also prove this by induction using Pascal's formula.

Since $\sum_{n=0}^\infty x^n\binom{n+1}{1}=\sum_{n=0}^\infty (n+1)x^n=D_{x}\bigg(\sum_{n=0}^\infty x^{n+1}\bigg)=D_{x}\big(\frac{x}{1-x}\big)=\frac{1}{(1-x)^2}$,

the statement is true for $i=1$.

Now assume that $\sum_{n=0}^\infty x^n\binom{n+1}{i}=\frac{x^{i-1}}{(1-x)^{i+1}}$ for some integer $i>0$.

Then if $h(x)=\sum_{n=0}^\infty x^n\binom{n+1}{i+1}=\sum_{n=i}^\infty x^n\bigg[\binom{n}{i+1}+\binom{n}{i}\bigg]$, letting $m=n-1$ gives $h(x)=\sum_{m=i-1}^\infty x^{m+1}\bigg[\binom{m+1}{i+1}+\binom{m+1}{i}\bigg]=x\bigg(\sum_{m=i-1}^\infty x^m\binom{m+1}{i+1}+\sum_{m=i-1}^\infty x^m\binom{m+1}{i}\bigg)$, so

$h(x)=x\bigg(h(x)+\frac{x^{i-1}}{(1-x)^{i+1}}\bigg)$ and so $h(x)=\frac{x^i}{(1-x)^{i+2}}$.

-


text:
# How fast can I split an image?

Consider an image(img) as

I have defined two functions for splitting and displaying as follows:

splitImage[img_, n_] := Module[{w, h, parts},
{w, h} = ImageDimensions[img];
parts = ImagePartition[img, {w/n, h/n}]
];

showParts[parts_] := Module[{},
ImageAssemble[parts /. i_Image :> ImagePad[i, 1, 1]]
];

Now,

showParts[splitImage[img, 64]] // AbsoluteTiming

gives me the timing as

4.61676

I need to split the image into 64x64 blocks and I want to speed up the process as much as possible.

How can I optimize the speed?

Edit 1 Here is the performance comparison of all the four techniques (executed on my machine):

@CoolWater: 0.0707495

@AnjanKumar: 0.510273

@Majis: 6.95316

@Alucard: 12.5303

Edit 2: Performance comparison updated for splitting

Edit 2:

Now I need you to recommend me which technique I should follow to access each individual part after splitting so that the combined speed will be the fastest.

[I can do the comparison myself but not all the techniques give me a direct access to the individual parts.]

• why not Grid@ImagePartition[img, 64] ? This does the same and it is about 1000x faster in my old Intel I3. Or am I missing something? – José Antonio Díaz Navas Feb 2 '18 at 12:01
• @JoséAntonioDíazNavas I need 64x64 blocks (which in this case will be of the size 4x4) and not blocks of size 64x64. – Majis Feb 2 '18 at 12:17
• I obtain a time 150x faster for a showing blocks of 4x4 for an image of 512x512, using what I proposed above – José Antonio Díaz Navas Feb 2 '18 at 12:20
• @JoséAntonioDíazNavas May be. But on my machine, it can't even compute for 4x4 blocks. – Majis Feb 2 '18 at 12:34
• @JoséAntonioDíazNavas Yes, you are right. It's more than 150 times faster. But I also need a similar display what I can get using showParts. Using Grid the spacing is very large. – Majis Feb 2 '18 at 12:46

Here is a solution that is a magnitude faster than the fastest method so far when it comes to rendering the image:

showParts[img_, n_] := Module[{data, h, w, nrows, ncols, i, j, tmp, new},
data = ImageData[img, "Byte"];
{h, w} = Most@Floor[Dimensions[data]/n];
{nrows, ncols} = Most@Dimensions[data];
{nrows, ncols} = {h Quotient[nrows, h], w Quotient[ncols, w]};
data = Part[data, ;; nrows, ;; ncols];

i = Rest@Most@Range[nrows + 2 nrows/h];
i = Drop[i, {h + 1, UpTo[Infinity], h + 2}];
i = Drop[i, {h + 1, UpTo[Infinity], h + 1}];

j = Rest@Most@Range[ncols + 2 ncols/w];
j = Drop[j, {w + 1, UpTo[Infinity], w + 2}];
j = Drop[j, {w + 1, UpTo[Infinity], w + 1}];

tmp = ConstantArray[DeveloperToPackedArray[{255, 255, 255}], {nrows + 2 nrows/h, ncols}];
tmp[[i]] = data;

new = ConstantArray[DeveloperToPackedArray[{255, 255, 255}], {nrows + 2 nrows/h, ncols + 2 ncols/w}];
new[[All, j]] = tmp;

Image[new, "Byte"]
]

showParts[img, 64] // AbsoluteTiming

The image data is never unpacked in this code.

To get the partitions, we can then apply OP's splitImage function, with good performance:

splitImage[showParts[img, 64], 64]; // AbsoluteTiming

{0.019043, Null}

(This will give us partitions that have been padded with a white border. It is unclear to me if this was desired on its own, or if those were only produced to be able to construct the image. In either case, here it is, if desired.)

One way would be to first extract the ImageData, Partition it, ArrayPad with {1, 1, 1}, convert it to Image, and finally use ImageAssemble.

arrPadImage = (ArrayPad[#, {{1}, {1}}, Hold[{1, 1, 1}]] // ReleaseHold // Image) &;
Partition[ImageData[img], Floor@(ImageDimensions[img]/n)] //

For the given image, this method takes about 0.34 s compared to yours which takes about 3.63 s.

imagePartitionPad[imsq, 64]

ImageData[imagePartitionPad[imsq, 64]] == ImageData[showParts[splitImage[imsq, 64]]]

True

• Please, what processor do you use? – José Antonio Díaz Navas Feb 2 '18 at 13:08
• I'm using Intel i7 7700 (Windows 10). – Anjan Kumar Feb 2 '18 at 13:09

This is almost the other answer, just slightly more vectorized and using integers for the data array which seems to be faster:

split[img_, n_] := Image[ArrayFlatten[ArrayPad[Partition[
ImageData[img, "Byte"], Reverse[Floor[ImageDimensions[img]/n]]],
{{0, 0}, {0, 0}, {1, 1}, {1, 1}}, {{{{{255, 255, 255}}}}}]], "Byte"]

split[ImageAssemble[{{img, img}}], 64]

Edit: To extract parts:

Clear[split];
split[im_, n_] := Partition[ImageData[im, "Byte"], Reverse[Floor[ImageDimensions[im]/n]]]

show[parts_] := Image[ArrayFlatten[ArrayPad[parts, {{0, 0}, {0, 0}, {1, 1}, {1, 1}},
{{{{{255, 255, 255}}}}}]], "Byte"]

parts = split[ImageAssemble[{{img, img}}], 64];
subImages = Map[Image[#, "Byte"] &, parts, {2}];

show[parts]

• A bit faster that the previous – José Antonio Díaz Navas Feb 2 '18 at 13:48
• @Coolwater How can you access each individual part following your approach? – Majis Feb 2 '18 at 17:41
• @Majis I think it depends on the purpose how that should be done, see edit – Coolwater Feb 2 '18 at 18:19
• @Coolwater Thanks. While calculating parts you've used img twice (probably by mistake). – Majis Feb 2 '18 at 18:31
• If you pack all your results you can go from ~.080s to ~.055s (i.e. toss DeveloperToPackedArray@ in front of Partition, ArrayPad, and ArrayFlatten. – b3m2a1 Feb 2 '18 at 19:20

Here's a super naive (but nonetheless very fast) method for generating the padded image, not for splitting (since that problem is almost trivially handled via Partition) that preserves the ImageColorSpace and leverages the power of PackedArray by not padding with 1 but rather with 1.:

splitty[img_, n_, padColor : {__?NumericQ} | _?NumericQ : 1] :=

Module[
{
data = ImageData@img,
dd,
ins1,
ins2,
},
dd = Dimensions[data];
N@
_?NumericQ,
_,
];
ins1 =
Insert[data,
Flatten[
Table[
{i, j},
{i, 1, dd[[1]]},
{j, 1, dd[[2]], Floor[dd[[1]]/n]}
],
1
]
];
ins2 =
Insert[
ins1,
List /@ Range[1, Length@ins1,  Floor[dd[[2]]/n]]
];
Image[ins2,
ColorSpace -> ImageColorSpace@img
]
];

Note that it performs surprisingly well:

splitty[img, 64] // RepeatedTiming // First

0.014

splitty[img, 64]

And you can insert an arbitrary color:

splitty[img, 100, .5]

splitty[img, 100, {.6, .6, 0}]

• so you worked directly on the original data,adding a constant array in the right position. very clever and fast! – Alucard Feb 2 '18 at 21:29
• The real trick is actually that N call (basically using 1. instead of 1). This allows Mathematica to keep the data as a PackedArray as it maintains the type of the data (Real vs. Integer) on which vectorized operations can be applied incredibly fast. – b3m2a1 Feb 2 '18 at 21:32
• do i get any advantage if i replace 1 with 1. inside hold or does it convert tthe machine precision number back to 1 ? – Alucard Feb 2 '18 at 21:34
• Not a major one, but like .04 seconds on a few tests I just ran. The problem is the Hold. Hold can't be interpreted as a numeric type and so Mathematica unpacks the array. – b3m2a1 Feb 2 '18 at 21:37
table = Flatten@ImagePartition[image, ImageDimensions[image]/64]
ImageCollage[table, ImagePadding -> 1, Background -> White,
Method -> "Grid"]

gives:

Update: as Josè noted, my answer, though formally correct, is slower than the original and should not be considered.

New Solution:

data= ImageData[image];
zn = Image@
ReleaseHold@
ArrayFlatten@
BlockMap[ArrayPad[#, {{0, 1}, {1, 0}}, Hold[{1., 1., 1.}]] &, data,
Floor[Dimensions[data]/64][[1 ;; 2]]] // RepeatedTiming

while the first answer took almost 17 seconds to show the result, the new one, on the same laptop, ends in just

0.076s

• Please check, it is slower... – José Antonio Díaz Navas Feb 2 '18 at 13:46
• As I noted to Coolwater, you can (almost certainly) get a speed boost by packing your arrays. I haven't tested it in your case, but since your and Coolwater's solutions are essentially the same my assumption is the speed boost will still apply. – b3m2a1 Feb 2 '18 at 20:20
• uhm i tried adding DeveloperToPackedArray@ but the timing doesn't change much ( more or less 1 millisecond) – Alucard Feb 2 '18 at 20:27
• @Alucard where'd you add it? The BlockMap might change the efficiency. Also your solution isn't entirely robust. First off your Imagedata isn't correct and also when it works on an image with an alpha channel it fails. – b3m2a1 Feb 2 '18 at 20:43
• @b3m2a1 i added it near ArrayPad . i can fix easily ImageData but , in the case of images with an Alphachannel ,replacing Hold[{1,1,1}] with a 4-dimensional vector change the original colors – Alucard Feb 2 '18 at 20:56


text:
Tag Info

2

You can "help" FindGeneratingFunction by specifying the function space you want it to explore: FindGeneratingFunction[{1, 4, 6, 4, 1}, x, FunctionSpace -> "Polynomial"] This returns the $1 + 4 x + 6 x^2 + 4 x^3 + x^4$ polynomial you expected.

0

With q = {x, Φ} V = (x^2*m^2 + Φ^2*I)/2 fv = Function[{x, Φ}, Evaluate[Total[Flatten[D[V, {q}]]]]][1, pi/8] (* m^2 + (I pi)/8 *) gives the desired result, if I understand the question correctly. Addendum If, as suggested in a comment, it is necessary that x and Φ have explicit t dependence, the following can be used instead. q = {x[t], Φ[t]} V = ...

5

Direct Integration Possible issues in performing the integrations include choice of Assumptions, branch cuts in the integrands, and how limits are taken. Addressing the first of these gives five solutions. il[f_, s_, t_] := Module[{r}, 1/(2 π I) Integrate[f Exp[s t], {s, r - I ∞, r + I ∞}, Assumptions -> r > 2 && t > 0]] ...

4

This is a method that is similar to Oleksandr R.'s answer: The following tells Mathematica to render Primed symbols in superscripted box form: MakeBoxes[Primed[x_], StandardForm] := SuperscriptBox[ToBoxes[x], "\[Prime]"] And this tells Mathematica to parse a superscripted box structure internally as Primed, and not as Derivative: ...

6

It is because there is no general solution for your problem, even for b being a positive integer: When b is odd, the maximum is positive infinity, while for even b it is not. You may want to use things like Maximize[-x^# + a*x, x] & /@ Table[i, {i, 5}] to observe.

Top 50 recent answers are included


text:
# [NTG-context] We have a problem --- Old file no longer compiles

David Arnold dwarnold45 at suddenlink.net
Thu Jul 5 00:39:31 CEST 2007

Aditya,

Thanks for the reply. As far as I know, we don't explicitly import
newmat in our environment files:

trunk \$ grep usemodule *
bookenv-clean1-base.tex:\usemodule[math-ext]
bookenv-clean1-colors.tex:\usemodule[colors]

As  you can see, we do use the module math-ext.

On Jul 4, 2007, at 2:57 PM, Aditya Mahajan wrote:

> On Wed, 4 Jul 2007, David Arnold wrote:
>
>> Here is another example, this time not within a block, but within an
>> enumeration again:
>
> The newmat module seems to be the culprit. After loading newmat add
>
> \unexpanded\def\frac#1#2{\mathematics{\genfrac{}{}{}\donothing{#1}
> {#2}}}
>
> and it should work fine. I do not really understand why this is
> failing.
>
> Aditya
> ______________________________________________________________________
> _____________
> If your question is of interest to others as well, please add an
> entry to the Wiki!
>
> maillist : ntg-context at ntg.nl / http://www.ntg.nl/mailman/listinfo/
> ntg-context
> webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
> archive  : https://foundry.supelec.fr/projects/contextrev/
> wiki     : http://contextgarden.net
> ______________________________________________________________________
> _____________

More information about the ntg-context mailing list


text:
• entries
31
27
• views
26241

# Rogue restart

615 views

I'm looking towards a redesign, big re factor. I've moved onto keeping aspects of the game into their own systems. It's made the way I handle actions/events quite a mess. I'll have to butcher it to handle the abilities I have planned.

The current system, events, specifically key presses are checked to call the action that's assigned to them. Any time an action succeeds I set a flag to simulate a turn. Then simulate the turn, applying ai, remove dead things, gain levels...etc

game onKeyPress case : key = p bool simulateTurn = pickupItem(...) simulateTurn if true
This is further complicated by an actionState that I used for multiple state actions. Using item in the inventory used to take two steps; choose to 'u'se an item, and choose the item to use. The system that morph out of that right now uses a always on cursor to the item in the inventory you want to use. Now pressing 'u' automatically tries to use that item.

game onKeyPress if (actionState == idle) check player moving check pickup check drop check eat ... if (droppingItem) choose item to drop write to console if (eatingItem) choose item to eat write to console if (drinkingItem) choose item to drink apply potion effects write to console ...
Most of it is redundant, just like that. The change to the inventory removed a little bit of the redundancy and I feel speeds up inventory use quite a lot. I want to keep things fluent as possible.

I'll be using a simple interface to derive systems from, and contain all logic and state to these systems. The interface will basically just need to be over-ridden and used to dispatch to the specific actions that system handles.

system virtual bool onKeyPress(...)
Then the logic of the game will be separated into these systems;
item systemdungeon systemcreature system
Unfortunately, for my sake, I'm going to restart this project. Taking whats still reusable and glueing it to the new system skeleton. I'm hoping that similar to starting this project after the last should go rather quickly. It'll make things easier for me in the long run. It's getting a little complicated to do these re-factorings any more. Unfortunately what I had designed before is not allowing what I want to do.

So ill leave you with a little snippet of what I had going before all this came to fruition. I have reimplemented all my items, with the new concepts already. Added a drop system similar to Diablo 2's drop class system. Drop classes contain lists of items that can drop and the chances for those items. Then things like creatures or chests are assigned a drop class. Got creatures and basic AI up and running.

There are no comments to display.

## Create an account

Register a new account


text:
# CFA Level III: Interest Rate Parity

Hello everyone,

Today I’m gonna talk about some economic concepts that were mentioned at least since Level II and that are quite useful in the whole curriculum and in finance in general when it comes to dealing with currency management.

# Covered Interest Rate Parity

The idea is quite simple, we will compute the forward exchange rate between two currencies using an arbitrage argument, say EUR and USD. The spot exchange rate is denoted $S_{\text{EUR}/\text{USD}}$: it corresponds to the number of euros you get today for 1 US dollar. Furthermore, the risk-free rate in USD is denoted $R_{\text{USD}}$ and the risk-free rate in EUR is denoted $R_{\text{EUR}}$. The question is, after some time $T$, how many euros will I get for 1 US dollar? This rate is called the forward rate and is denoted $F_{\text{EUR}/\text{USD}}$.

Well, you can price that quite easily using an arbitrage argument! The idea is simple:

• I’m going to borrow today $\frac{1}{1+R_\text{USD}}$ USD which means that at time $T$, I will have to pay back 1 USD.
• Then I’m going to convert what I just borrowed in EUR, which gives me $S_{\text{EUR}/\text{USD}} \cdot \frac{1}{1+R_\text{USD}}$ euros
• I then invest this at the risk-free rate in EUR, and I get at time $T$ $(1+R_\text{EUR}) S_{\text{EUR}/\text{USD}} \cdot \frac{1}{1+R_\text{USD}}$ euros

What I wrote above means that:

$$F_{\text{EUR}/\text{USD}}= S_{\text{EUR}/\text{USD}} \cdot \frac{1+R_\text{EUR}}{1+R_\text{USD}}$$

That’s as simple as it sounds, we have determined the forward price of US dollars in euros at time $T$.

A very easy way of remembering the formula above is noticing that the rate in the numerator and in the denominator are from the same currency as is shown in the rate label: EUR/USD.

Also, recall from this post that in this case (EUR/USD), the US dollar is the asset being priced in euros; the US dollar is an asset like anything else.

Finally, we understand from the formula above that:

$$R_\text{EUR} > R_\text{USD} \implies F_{\text{EUR}/\text{USD}}> S_{\text{EUR}/\text{USD}}$$

This is very useful because you very often have to say what currency is trading at premium or at discount in another currency. First I used to always get that wrong. In fact, it’s very easy.  The currency being traded is the one in the denominator of the label, here USD. Then, if the forward price is higher (lower) than the spot price, it is of course trading at premium (discount).

So, if we say that the USD is trading at premium in EUR, it means that we can have more EUR in the forward market than in the spot market for 1 USD.

# Uncovered interest rate parity

This is in a sense an extension of the covered interest rate parity we just discussed which says that:

$$\mathbb{E}({S_{\text{EUR}/\text{USD}}}_T)= {S_{\text{EUR}/\text{USD}}}_0 \cdot \frac{1+R_\text{EUR}}{1+R_\text{USD}}$$

Notice that here the implication is different than previously, because we say that we expect that the spot rate at time $T$ will be equal to the forward price at today. This comes to says that the currency that has the higher (lower) interest rate is expected to depreciate (appreciate):

$$R_\text{EUR} > R_\text{USD} \implies \mathbb{E}({S_{\text{EUR}/\text{USD}}}_T)> {S_{\text{EUR}/\text{USD}}}_0$$

Indeed, a higher spot rate in the future means that you would get more euros for the same amount of US dollars which means that the euro has depreciated!

A lot of traders disagree with that statement, and this comes to a very famous trading strategy called the carry trade. The idea is really simple as well: these traders do not think that the currency with the higher interest rate will depreciate. They hence short the currency with lower interest rate and invest in the currency with higher interest rate. In the curriculum, they say that this strategy tends to work most of the time, generating positive income. However, they say that, when for some reason, the interest rate goes in the expected direction, they tend to do so very violently and that it can lead to very large losses.

That’s it for today, I hope this little post will help you in mastering this concept, which is key to a lot of different topics at different levels of the CFA curriculum.

Cheers,

Jeremie


text:
# Vector into a diagonal Matrix

1. Aug 1, 2011

### MehranMo

I think this is a pretty simple question. I need a transformation that will take a Column vector e.g.: <a,b,c> and turn it into a 3x3 matrix where a is in position 1,1 and b in position 2,2 and c in position 3,3. i.e.: a diagonal matrix.

Any help?

2. Aug 1, 2011

### Fredrik

Staff Emeritus
What kind of transformation? You can define the function by saying that for each i,j we define $X_{ij}=\delta_{ij}x_i$. (There's no summation over the repeated indices). Do you need to define the function by matrix multiplication alone, or is it OK to use addition too?

3. Aug 2, 2011

### I like Serena

You could pick a 3 dimensional matrix (a 3x3x3 cube) with 1's on the main diagonal.

4. Aug 4, 2011

### JG89

There is a linear isomorphism $\alpha$ such that for any vector $(a, b, c)$ $\alpha$ will take $(a,b,c)$ to the 3 by 3 matrix, whose main-diagonal entries are a, b, and c, with all other entries being 0.