text:
# Strings 2007

Strings 2007 is starting today, and already there seem to be a large number of different laptops connecting to this blog from wlan.uam.es. I’m hoping that some of their owners will write in here with news of how the conference is going. I’ll also try and add links here to any blog and press coverage of the conference that I see or hear about.

Witten’s new 83 page paper entitled Three-Dimensional Gravity Revisited appeared on the arXiv last night and presumably this is the detailed version of what he’ll be talking about in the first of tomorrow’s talks at the conference. It corresponds pretty much to what he talked about here in New York a few weeks ago, which was described here. I assume many of those laptops at the conference are being used to download and read copies of Witten’s paper. At his blog, Clifford Johnson notes that he won’t be at Strings 2007, and hopes that this will ensure that there will be an exciting breakthrough announced there, just like what happened when he decided not to attend Strings 1995.

As I write this, I see that string theorist Jacques Distler is there live-blogging. Here’s the first of his reports.

Update: Some of the slides of the talks are already on-line. The slides for Witten’s talk are available here.

Update: There’s an interesting posting here by Jacques Distler about the Witten talk, and, for those who enjoy such things, quite a rant from Lubos here, prompted by my comment that in this case Witten is investigating quantum gravity using non-perturbative QFT, not strings.

I’ve been reading Witten’s paper a bit more carefully, and it raises all sorts of interesting issues. He makes the point that even in 3d, we really don’t know exactly what “non-perturbative pure quantum gravity” is. He uses the Chern-Simons formulation of 3d gravity in terms of gauge theory to motivate his guess at the correct boundary CFT, and then once he has that he has something much more well-defined to study.

This is a bit reminiscent of the compact, non-gravitational situation. There Chern-Simons theory works fine perturbatively, but to understand the non-perturbative theory one connects it to a CFT on the boundary, in this case the Wess-Zumino model (this is the story that got Witten a Fields medal).

Update: B. Yen has set up a video-blog for Strings 2007, where there will be iTunes podcasts of the conference available.

Update: Latest report from Jacques Distler is that, since Witten’s one, which he got to write about:

there have been some very cool talks

(emphasis in the original), but he can’t tell us even which ones they were since his laptop is malfunctioning. Slides of the talks are available here. I’ve looked through them and, besides Witten’s, don’t see anything I would describe as “very cool”, but maybe that’s just me.

Update: All the talks are on-line now and I just looked through the last of them, and watched the summary talk by Gross. Lisa Randall discussed recent calculations of black-hole production at colliders, with the bottom line being that even in the unlikely event the gravity scale is within reach of the LHC, existing bounds already pretty much rule out the possibility of seeing the kind of dramatic effects from black hole production that have been widely advertised as something that might be seen at the LHC.

Gross noted that the conference was much less mathematical than last year’s, possibly because Yau was not involved in organizing it. He was most enthusiastic about describing the many talks on AdS/CFT, especially the Beisert talk which told about recent progress in getting an exact solution of N-4 SYM. Some talks referred to possible applications of AdS/CFT not just in QCD and heavy-ion physics, but in condensed matter physics (using the duality to get info about relevant CFTs). He told about Polchinski’s speculation that “maybe AdS/CFT will solve high Tc superconductivity”, but dismissed it with “sounds great, but seems unlikely to me.” He dealt with the landscape talks by flashing them by quickly, in a lower and less enthusiastic voice, noting that they made up at least a quarter of the talks at the conference. He dealt similarly with the cosmology/anthropic talks, describing Bousso’s as “an attempt to make the anthropic principle precise if not respectable.”

After the summary, he gave his own take on the state of string theory, saying that one had to be honest about the lack of falsifiable predictions and that now he had a slide headed “The Failures of String Theory”. He continues to feel that the main failure is because we “don’t know what string theory is”, that something is missing, some principle that would pick out not a “vacuum” but a “cosmology”, one perhaps using new ideas about what space and time are. He said he was not too upset by the landscape, because “we don’t know what the rules are” in string theory, so one can’t argue that string theory implies the landscape. He appeared to feel that he is losing the debate, complaining that this used to also be the opinion of his colleagues, but that they were going over to the other side because of the cosmological constant, saying that if another explanation of the CC was found 90% of the anthropicists would come back to his side. He tried to minimize the size of the CC problem, measuring it with respect to a supposed 1 TeV SSYM breaking scale and working in energy, not energy density units, so it is only too small by a factor 1016. He compared this to Dirac’s famous large number problem (which Dirac tried to solve not anthropically, but by time-varying constants, leading to a prediction that was falsified), which was finally “explained” by asymptotic freedom. His message to the anthropocists was “just because you don’t know an explanation doesn’t mean it doesn’t exist”.

Finally he mentioned that Strings 08 will be at CERN, Strings 09 in Rome, and no one has yet agreed to host Strings 10. He argued that the series of Strings conferences “must go on”, because they are “like the canary in the coal mine”, and if they stop that would be a very bad sign for string theory.

I’m curious to know what those in attendance thought of this; it wasn’t exactly a rousingly optimistic portrayal of the state of the subject…

Update: There’s an article in El Pais about the conference and about the state of string theory. My Spanish isn’t perfect, but as far as I can tell the piece was pretty much pure unadulterated hype, of the sort that it is one goal of the Strings XX bashes to generate.

Update: Jacques Distler finally got his computer fixed, and posted about one example of what he considered a “very cool talk” with exciting new ideas. Unfortunately, it seems the ideas are not that new, since a commenter wrote in to his blog to point to papers from four and a half years ago that do pretty much the same thing.

This entry was posted in Strings 2XXX. Bookmark the permalink.

### 80 Responses to Strings 2007

1. Hi Peter,

I wonder why three international conferences dealing with strings one way or another are being held at more or less the same time around the globe. I of course would not have dreamt of going to Strings 07, while I am indeed going to Pascos next week, which has some strings flavor but admittedly is also devoted to particles and cosmology. But die-hard stringers might have had to make a difficult choice.

By the way, I will try to report from there, but I will be there only for a couple of days so I can’t really promise anything…

Cheers,
T.

2. marcus says:

here is a sample exerpt from the talk by Witten, slides 14 – 16:
==quote==
First of all, I am only going to consider the case of negative cosmological constant.
Currently there is some suspicion that quantum gravity with Lambda > 0 doesn’t exist non-perturbatively (in any dimension) with positive cosmological constant. The reason for this is that it does not appear to be possible, with Lambda > 0, to define precise observables. This is natural if it is the case that a world with positive cosmological constant (like the one we may be living in) is always unstable.

If that is so, then a world with Lambda > 0 doesn’t really make sense as an exact theory in its own right but (like an unstable particle) must be studied as part of a larger system.

Whether that is the right interpretation or not, since I don’t know how to define any precise observables, I don’t know what it would mean to try to solve 2+1-dimensional gravity with Lambda > 0, since it isn’t clear what we’d want to compute.
==endquote==

Unfortunately this sounds like a rationalization. Perhaps it is a question of what tools one uses, as you suggested in comment to your previous post:
http://www.math.columbia.edu/~woit/wordpress/?p=570#comment-26394
If one set of tools for studying the world fails to provide observables, then before declaring the world we “may be living in” to be “like an unstable particle” it seems a sensible reaction would be to look around for better technical means. Am I missing some essential part of the message? Maybe others would comment on this passage.
__________________

Marcus,

Witten’s argument is exactly what leads to anthropic principle: if our dS universe is only a metastable vacuum, it is probably an ugly mess from a landscape of possibilities, and there is no beautiful selection principle to guide us. Declare defeat, and work on mathematically nice but physically wrong things, like 3D and AdS.

This is a unavoidable problam if all observables in QG are global, because dS space lacks the right asymptopia where the global observables can live. AFAIU, the only way around this dilemma is if there are local observables in QG after all; then we don’t have to worry about the lack of global observables.

Indeed, we know for sure that there are local observables in classical GR – Rovelli’s GPS coordinates. Now, these are only partial observables, but we could make them complete by reading a local clock. Without leaving my car (if I had one), I could use my fancy GPS equipment to read off my GPS coordinates, and read off the dials of my watch to get proper time, and get a local, complete observable. This observable is local, because I don’t have to visit a holographic screen in an AdS region of the multiverse (i.e. outside our visible dS universe) to make this observation; I can stay in my car.

4. Peter Woit says:

Marcus,

I think this debate over dS observables is completely irrelevant to the Witten paper. All he is doing is referring to that debate and noting that the arguments in his paper involve the AdS case, and don’t apply to the dS case. He’s not making any claims in this paper of any new ideas or understanding about the dS case.

5. Jim Clarage says:

If I were still in theoretical physics I’d eagerly await next year’s Strings 2008. For it will mark the 175th anniversary of Hamilton’s article on optics and planetary motions where he invokes the spirit of Bacon:

In every physical science, we must ascend from facts to laws… and unity arises from variety: and then from unity must re-deduce variety, and force the discovered law to utter its revelations of the future.

Or if I can quote again with inlines relevant to science nearly two centuries later:

In every physical science [even string theory], we must ascend from facts to laws… and unity arises from variety: and then from unity must re-deduce variety [i.e., must reproduce the standard model], and force the discovered law to utter its revelations of the future [i.e., make novel and testable predictions of future experiments].

6. Peter Woit says:

Hi Tommaso,

One reason there are a lot of string theory conferences (20-30 a year) is that there are a lot of string theorists. And conferences are concentrated in the summer months when people don’t have to teach. Typically there are a few smaller “satellite” conferences organized before and after the main Strings conference, at locations not too far away. I gather there are some of these going on around now. Will look forward to your reports from PASCOS!

7. Jim Clarage:

I don’t think that string theory should be blamed exclusively for the stagnation in modern theoretical physics. I think that the fundamental problem was best expressed by Mark Srednicki in his reply to Chris Oakley on Cosmic Variance

And I don’t agree at all with your statement that while “it would be very nice to explain SM parameters, but establishing a mathematical framework free of inconsistencies has to be done first.” Historically, progress in physics has almost never been made this way. It almost always came by somebody futzing around with some not-fully-baked theory, until something interesting popped out.

This “futzing around with some not-fully-baked theory” was very successful until 1960’s. But, apparently, it doesn’t work anymore. I think that the chance that something will “pop out” is close to zero. Maybe it is time to stop relying on random attacks and switch to a methodical and organized siege: Decide which physical principles are truly important (the principle of relativity? laws of quantum mechanics?…) and build a rigorous axiomatic mathematical framework around these principles.

8. hmmm says:

Decide which physical principles are truly important (the principle of relativity? laws of quantum mechanics?…) and build a rigorous axiomatic mathematical framework around these principles.

Well that’s the whole problem isn’t it. That’s like saying “…to become a gazillionaire we need to decide which business idea is the right one and build a rigorous business around that…”

9. hmmm,

That was my point. I have an impression (please correct me if I am wrong) that there is no much interest in designing a sound plan and building the “business” from ground up. Just look at talks at String 07 or any other similar gathering. People are trying to prove theorems without even knowing what their axioms are. These are conjectures based upon previous conjectures. Using your analogy, they try to become gazillionaires by gambling in a nearby casino. Srednicki thinks this is the way to go. I respectfully disagree.

10. Coin says:

Using your analogy, they try to become gazillionaires by gambling in a nearby casino.

Well, they have to. It’s the only game in town.

11. Coin says:

So I’m afraid a lot of this is beyond my current level of understanding, but I’m trying to figure out– it’s been commented several times that Witten’s Strings 2007 paper here doesn’t seem to have much to do with string theory. However, it does seem like it has a lot to do with AdS/CFT correspondence. In fact, it seems like he’s *using* the AdS/CFT correspondence; as I understand this he’s analyzing black holes in 3-dimensional AdS spacetime by reasoning about the equivalent 2-dimensional conformal field. That’s AdS/CFT, right? So here is basically what I’m trying to figure out:

1. This paper seems to somehow be using AdS/CFT without talking about strings. I didn’t actually realize you could do that. Is there anything “special” about CFTs that correspond to spaces with strings, or is it just a matter of whether you choose to describe the space as containing strings?

2. Although the paper doesn’t explicitly talk about strings, would it make sense for the ideas in this theory to be followed up, in either a later paper by Witten or somebody else, by linking these ideas to string theory or simply adding strings to the toy model described here? If so, what would that look like? Like, would it make any sense to drop strings into the toy model here and analyze their interactions with a BTZ black hole?

12. Peter Woit says:

Just a reminder. If you want to have general philosophical discussions about physics, please find some other forum. If you have something substantive to say specifically about the topic of this posting, String 2007, please do so.

13. Peter Woit says:

Coin,

When people talk about “AdS/CFT” duality, they normally are talking about a relationship between string theory on five-dimensional AdS space (really AdS times a 5-sphere, the strings need 10 dimensions) and a supersymmetric gauge theory on its 4d asymptotic boundary. More generally, one hopes that this string-gauge duality works for different sorts of geometries. One could try and do this with 3d AdS space, and people have worked on that.

But this is just not what Witten is doing. He’s not looking at string theory on the AdS space, he’s looking at pure gravity, and at a Chern-Simons gauge theory, and trying to understand their relation. Pure gravity and string theory on AdS are just two very different theories. What Witten is doing just isn’t a string/gauge duality. I don’t see what you’re going to achieve by adding string theory to this story, and I suspect if Witten thought one could get anything that way, he’d certainly be mentioning it in his paper or talk at the conference. Strings are mentioned zero times in his talk

14. ori says:

Let us leave alone for a moment the question of whether the recent paper of Witten has anything to do with String theory or not.

What it clearly implies, is that variable changes as those promoted by Ashtekar and used in LQG can not be correct, and have nothing to do with the quantum version of gravity (which is expected to have black holes to start with). Thus, in the most well understood situation of 3d gravity, where the variable change is clean and covariant (unlike 4d) Witten shows that this avriable change is menaingless in quantum level.

Should we still expect that 4d LQG tricks do makes sense ? certainly not. This is a complicated non covariant version of the 3d case, and one should not expect any conclusion besides that LQG has no meaning after quantization.

Thus, one of the conclusions of Witten’s paper is that LQG does not make any sense.

15. Peter Woit says:

Ori,

Witten does not claim that using gauge variables and the Chern-Simons action has nothing to do with quantum gravity. He actually uses these to produce the correct central charge of the boundary CFT. Here’s what he actually does say about this:

We know that Chern-Simons gauge theory is useful for perturbation theory, as was explained in that section, and we hope that it is useful for understanding some nonperturbative questions. We used the gauge theory approach to get some hints about the right values of the cosmological constant (or equivalently of the central charge) simply because it was the only tool available.

The variables that do seem to be useless for non-perturbative quantum gravity in 3d are string variables. Witten doesn’t mention strings at all in his talk and gives no indication that he thinks they have anything to do with this problem.

Unfortunately I don’t think this tells us anything one way or another about 4d, but if one could have the kind of success there starting with Ashtekar variables that Witten seems to have starting with Chern-Simons in 3d, that would be quite spectacular.

16. Ori says:

Peter,

I want to avoid misunderstanding and confusion. Forget for a moment how Witten derives whatever he derives, this is a matter of taste. The invariant physical conclusion is that the non perturbative complition of 3d gravity has nothing to do with the gauge theory !

Similar conclusion is expected to hold for the 4d case, where there would not be enough dof in the gauge theory to create black holes, as in the 3d case.

Most of the people here are laymen, and I want to make sure that they understand that Witten’s conclusion is that the gauge theory variables are bad. This was known to Seiberg for some time, apparently. This leaves no hope that any interesting insight can be derived from gauge theory formulation of 4d gravity, for obvious reasons. Thus, LQG seems to have been falsified.

Unrelaed comment for experts : The way Witten derives some central charges does uses gauge theory variables. This is, however, incorrect since the gauge theory variables dont make much sense. Witten admits this is the case, and wishes he had a better way to derive the central charges. He could, as well, guess the correct values by some factorization and absence of gravitational anomalies requirements. This is the second way he motivates these charges, which is much more convincing.

One should not confuse the physics conclusion (which is that the Chern-Simons formulatoins have nothing to do with gravity) with the technical details (which is an incorrect derivation of some central charges, which is as good as a guess). Note that the reason CS has nothing to do with gravity is independent of the ability of disability to derive these central charges.

17. Ori says:

Another comment is that Peter is correct that there are no stringy variables in the story. However, the construction of the paper is a very particular example of something which was well known is string theory : AdS/CFT. This also shows that the results obtained in string theory in this context are much more general, because similar techniques can be applies in non supersymmetric non stringy cases.

18. gunpowder&noodles says:

“Thus, LQG seems to have been falsified.”

Oh, come. It’s extremely clear that all of Witten’s [brilliant] work on this is strictly dependent on the 3D context. There is not a clue about how to extend *any* of this stuff to the enormously different 4D case. I have no time for LQG, but enthusiasts for it could quite legitimately point out that 3D gravity has been studied intensively for years, and so far it has told us exactly nothing about 4D physics. There’s no reason to suspect that this is about to change.

For all my admiration for EW, and gratitude to him for the way he has changed the subject, I have to summarize the situation as follows: he has shown that gravity with the wrong sign of the CC in the wrong dimension is wrongly described by Chern-Simons. Next talk please.

19. Peter Woit says:

Ori,

Your claims that Witten has shown that “gauge theory variables are bad” etc. are directly contradicted by what Witten actually wrote, including the part I quoted above. You’re putting lots of highly tendentious claims in his mouth which are not in his paper and were not in his talk (or in the one I heard here in New York). I think Witten is someone who is very careful to say precisely what he means. In this case he is being very clear that the question of how to properly understand 3d non-perturbative quantum gravity is very much still up in the air. Here’s what he writes:

We make at each stage the most optimistic possible assumption. Decisive arguments in favor of the proposals made here are still lacking. The literature on three-dimensional gravity is filled with claims (including some by the present author [6]) that in hindsight seem less than fully satisfactory. Hopefully, future work will clarify things.

This is very different than claiming that he has shown that “the non perturbative complition of 3d gravity has nothing to do with the gauge theory !” and falsified the whole idea of using gauge theory variables.

20. Ori says:

The conclusion from your comment is that you have misunderstood the paper completely. You have picked some quotations out of context, and that is it.

Witten clearly write that the CS theory can not be the correct non perturbative complition, he said it explicitly in strings and it is written in the paper. This is the whole point of the paper, if you claim otherwise, you have misunderstood the paper and the talk. Let me quote for you :

“There is, however, an even more serious problem with the idea “gauge theory=gravity in 2+1 dimensions”…. ”

He has couple of such arguments against the 3d description via CS theory, which in the overall sum to what I said.

You may keep thinking whatever you want, I am the last to care, I was only willing to make sure that readers of this blog will be aware of the correct statements.

To gunpowder&noodles :

If you had read the paper, you would have understood that the arguments against the gauge theory description are completely general, and can be extended to 4d as well. Witten also says that theories with positive cosmological constant probably have no non perturbative complition (unless embedded in a more complete model), so it is not clear what is the point in trying to quantize de sitter backgrounds, without a stable ads ground state

21. Ori says:

Another way to proceed, is that u answer a question (Instead of putting more and more out of context quotes to defend yourself).

There are BTZ black holes in 3d. If CS is the correct way to quantize gravity than there should be extremely many states in the topological CS theory. What are they ? 🙂

Of course, there are no such states (since CS is a topological theory), which is the main point in Witten’s paper (and the strings talk). This means that CS has nothing to do with the full quantum theory of pure gravity.

I would like to recall ori that is possible to written the BTZ black hole as a solution of CS theory. It was done many years ago by Malrof and other people. Look at ArXives.

Thus, the quantum CS theory also contains BH, as is part of they are part of its classical spectrum.

23. woit says:

Ori,

I certainly don’t claim that Chern-Simons is the “correct way to quantize gravity”. For one thing, as Witten states, non-perturbatively the situation of 3d gravity remains unclear. The problem is not necessarily even well defined: maybe there is more than one consistent non-perturbative theory that has the right classical limit. Witten has made a very interesting proposal about a distinguished boundary CFT that might deserve to be called the “right” boundary CFT for non-perturbative pure gravity. I don’t think he claims at all to know what if any 3d variables and Lagrangian treated non-perturbatively with conventional path integral techniques would lead to this theory.

This problem corresponds to something that has always bothered me in the simpler compact Chern-Simons-Witten theory. The standard thing people say there is that, even non-perturbatively, the theory is defined by “integrating $$e^{ikCS[A]}$$ over the space of connections A”. This is kind of nonsense. Try actually doing this integral, e.g. by putting it on a lattice, and you start to see what the problems are. While the CS action is fine for generating a perturbation theory, non-perturbatively it doesn’t completely define the theory. What Witten does in that case is use the CS action to motivate what the boundary theory is (WZW), and then uses that to actually do computations. Even in that case, the CS action isn’t the full story about the non-perturbative theory, but it definitely is true that you want to be using gauge theory variables.

Anyway, there’s a very interesting story going on here, and gauge theory variables are definitely part of it.

24. Peter Woit says:

Thanks dbm,

I was wondering about Distler’s claim that “We would not, for instance, ever see the BTZ blackhole from the gauge theory”, which didn’t seem to make sense since the gauge theory gives the same classical equations and the BTZ black hole is a classical solution.

25. Peter,

your links to lubos’ blog get dumped to a unwelcoming page, you should know this by now, or is it an attitude to ignore the fact ? 😉

This time though I will second the auto-embargo of Lubos. I intended to read his rant, but now I changed my mind… He is probably happier that way.

Cheers,
T.

26. Peter Woit says:

Tommaso,

I’m not ignoring it, just figure it adds to the entertainment value…

27. Aaron Bergman says:

What I think Jacques meant (although I haven’t asked him) is the microstates of the BTZ black hole — it’s hard to imagine where they are in a topological theory.

28. urs says:

microstates of the BTZ black hole — it’s hard to imagine where they are in a topological theory.

The Einstein-Hilbert action functional can be rewritten as a Chern-Simns action functional in 3d. So if the former has an extremum somewhere (like a black hole solution), the latter must have, too. After all, they are equal. No? What am I missing?

29. urs says:

it’s hard to imagine where they are in a topological theory.

One more thing:

consider pure gravity in any dimension d. Consider a d-dimensional topological space, possibly wtih boundary. Suppose you could make sense of the EH path integral over all metrics on that space, possibly with prescribed boundary data. Shouldn’t the answer depend solely on the topology of the chosen space? Shouldn’t it in fact give you a functor from d-dimensional topological cobordisms to some flavor of vector spaces? Wouldn’t that be exactly as for Chern-Simons theory?

The only real distinction which I can see between the EH formulation and the corresponding gauge theoretic (Palatini) formulation of gravity is that the former vaguely suggests not to include degenerate metrics, while the latter vaguely suggests to include them.

30. Aaron Bergman says:

No? What am I missing?

Microstates. You’re thinking about the classical solution which is a macrostate.

31. urs says:

No? What am I missing?

Microstates. You’re thinking about the classical solution which is a macrostate.

Hm.

Suppose I did the CS path integral over connections with the constraint that the vielbein be invertible.

What would be the difference between using the EH action functional in the path integral from using the CS action functional? Both are equal. Both are defined on the same domain. What’s the difference?

32. urs says:

(Sorry, there is a blockquote missing. The comment preview did correctly show the nested quotation which I did include.)

33. Aaron Bergman says:

Isn’t that question aking to, suppose I did the path integral for the EH action in 4D? Do you know how to quantize CS theory with that constraint?

34. urs says:

Do you know how to

Right, of course I don’t.

The only thing I really know here (beyond knowledge of folk lore and plausibility arguments that all get so confusing after a while) is this:

for every modular tensor category, I can construct

A) a 3-dimensional TQFT

B) a 2-dimensional rational CFT

C) such that they are holographically related.

If that tensor category happens to be the representation category of loops in G, then

A) is G-Chern-Simons theory

B) is the WZW model on G

C) is the fact that states of Chern-Simons are conformal blocks (precorrelators) of WZW.

It is strongly assumed that this can be extended beyond rational CFTs. But only for rational CFTs this has been done in detail.

In any case, there should be other modular tensor categories, or variations thereof, and there should be other realizations of A,B,C. I would like to see if what Witten is talking about could be (classes of) other realizations of this. It ought to be, since he is in effect arguing that A should be defined in terms of B.

35. joe says:

The videos seem to be working for me (USA, west coast). Somewhere else, someone mentioned some download bandwidth issues.

I need to contact the program chair (name & email) to get permission to do some tests with their videos. Can’t find it on the Strings ’07 website, just the webmaster emails. Help? (I went to the IFT sponsor site, but the Miembros section has a generic list of staff.)

36. ori says:

You seem to completely misunderstand the point. It is correct that the classical BTZ solution was written long time ago, as any other classical solution (eg gravitons near the boundary). However, the BTZ entropy can not be accounted for by the quantum CS theory in any reasonable way (and here Witten says “although there were some attempts in the past…”).

Thus, the CS theory does not appreciate the thermodynamics of black holes and can not explain their entropy. Hence, CS can not describe in the quantum level anything like gravity (this is a correct invariant physical conclusion which means that the gauge theory variables are meaningless after quantization and can at best serve for some unmotivated guesses).

A similar thing happens in 4d as well, where the gauge theory variables of LQG dont make sense after quantization.

37. ori says:

Urs,

>”The only real distinction which I can see between the EH >formulation and the corresponding gauge theoretic (Palatini) >formulation of gravity is that the former vaguely suggests not to >include degenerate metrics, while the latter vaguely suggests to >include them.”

You are correct, and this difference is very very crucial !! if not this difference the theories were equivalent. In all known examples in string theory the non perturbative formualtion has never included degenerate metrics. Also here, this is the fundamental reason for the failure of CS variables in the quantum level. Similarly, in 4d, the gauge theory variables (and LQG) break down for the same reason.

38. Arun says:

In 4D, LQG has enough degrees of freedom to account for black hole entropy, therefore I do not buy Ori’s A similar thing happens in 4d as well, where the gauge theory variables of LQG dont make sense after quantization..

It may very well be that LQG does not make sense for other reasons.

39. dbm says:

hi uri,

I think that despite phylosphical considerations, facts are facts.

And the first fact is that you don need to consider the CS formulation of GR to admit configurations wih a degenerated vielbein, is enough to consider the first order formalism in which the vielbein and the spin connection are regarded independent fields, this theory, automatically, admits a solution where all the fields are zero. Furthermore this first order formulation of GR can be done in any dimension.

The second fact is that it has been proved, long ago, that the first order formalism, is off shell equivalent to the usual metric formulation, that is: the set of configurations where the vielbein is not inverible is of measure zero.

I would say that all this bla bla, of witten and the degrees of freedom of GR, and that in string theory the invertibility of the metric is a serious thing, contradict not only his paper on the soulbility of GR, but also his papers on topological quantum field theory, and topological gravity of the 80’s.

I really dont like his arguments and I even think that his last paper deserve further analysis, for instance is no possible that the guy doesnt obtain the right value for the entropy for BH of mass=2 and says, ok, for larger k a better agreement will be obtained.

Come on!

40. Carol says:

I want to live in the dimension where a story can earn you a Fields medal, and shouting loud enough releases a graviton.

41. ori says:

dear dbm,

The entropy for k=1 is not expected to match since you compare a semi-classical entropy given by the BH formula to an exact calculation of microstates.

In this regime, semi classical analysis makes no sense since the black hole is very small and gravity is strongly curved. Therefore, the fact the results are similar is a good surprise.

The fact that for larger k there is a better and better agreement is a strong indication that what Witten did is correct.

Of course, this is correct regardless of you liking or disliking this.

42. Arun says:

How do black holes form in 2+1 classical gravity? (i.e., with no gravitational radiation)?

43. dbm says:

Dear ori,

So, please explain me, why in every realistic situation in which we can actually compute the entropy beginning with the microscopical description it COINCIDE with our thermodynamical result.

Thanks!

44. ori says:

Dear ori,

>So, please explain me, why in every realistic >situation in which we can actually compute the >entropy beginning with the microscopical >description it COINCIDE with our >thermodynamical result.

>Thanks!

I assume you refer to systems which are not gravitational. The explanation is trivial : The result coincides with the thermodynamic result in the limit where the system is large. For example, even in the system of free spins which contains N spins the result will not coincide with the thermodynamic result for finite N, there are logarithmic corrections (Stirling’s formula) etc.

Note that to count states correctly one also needs to have a weakly coupled description of the degrees of freedom, and for the word thermodynamics to make sense there needs to be a classical description of the system.

In the case k=1 the black hole is very small, so it is not a macroscopic system and also the system has no good classical description. Thus, you basically extrapolate formulas illegaly and you should not be surprised that you get a somewhat different result.

I don’t have any idea what you meant by your comment, anyone who has ever studied statistical physics know that there is never agreement with thermodynamics beyond the strict limit of infinite number of dof, sorry.

45. dbm says:

Ori,

You are right, in the theormodynamic limit.

However, I still insist in my point of the offshell equivalence of CS theory, and 2+1 GR, I mean the facts that I previously mentioned.

The first fact is that you don need to consider the CS formulation of GR to admit configurations wih a degenerated vielbein, is enough to consider the first order formalism in which the vielbein and the spin connection are regarded independent fields, this theory, automatically, admits a solution where all the fields are zero. Furthermore this first order formulation of GR can be done in any dimension.

The second fact is that it has been proved, long ago, that the first order formalism, is off shell equivalent to the usual metric formulation, that is: the set of configurations where the vielbein is not inverible is of measure zero.

46. ori says:

I am happy you agree (and you should withdraw your “come on” comment).

The mistake in your other statement is the sentence

“the set of configurations where the vielbein is not inverible is of measure zero.”

Nobody knows how to formulate the non perturbative gravity path integral (it is not necessarily the naive one with Haar measures)
and hence, you can not deduce the measure of degenerate metrics correctly, sorry.

In fact the work of Witten CLEARLY shows that the effect is not a measure zero one, and leads to substantial non perturbative differences in the two theories (which naively differ by measure zero).

47. ori says:

btw, one should expect this set of non invertible metrics to be very important also in higher dimensions.

48. dbm says:

But, consider the paper gr-qc/0303113. My argument is as follows, if the first order, palatini, formalism admit naturally a degenerated viebein, and these people has shown that it coincide, off shell, with the second order metric formalism. ..

There is some level of tension between that paper and your last setence!

btw, thanks for the discussion, is fun.


text:
# Markov Decision Processes and Optimal Control

## Introduction

Goal of this notebook is to introduce Markov Decision Processes (MDPs) and how to solve them by dynamic programming. MDPs model the interaction between an agent and the environment.

In the full reinforcement learning problem the environment-agent model is unknown. However, an understanding of MDPs is fundamental for reinforcement learning.

## Requirements

### Python Modules

With the deep.TEACHING convention, all python modules needed to run the notebook are loaded centrally at the beginning.

# Python Standard Library
import os

# External Modules
import numpy as np
import matplotlib.pyplot as plt
import mpl_toolkits.mplot3d

from scipy.stats import poisson

## Markov Decision Processes

Markov decision processes (MDP) are a model of the agent-enviroment interaction.

In this notebook key elements of MDPs are introduced.

### Definition

A countable MDP is defined as a triple$\mathcal M = (\mathcal{S, A, P_{0}})$ with

• A countable not-empty set of states$s \in \mathcal S$.
• Countable not-empty set of actions$a \in \mathcal A$.
• Transition probability kernel$\mathcal P_0$:$\mathcal P_0$ describes the (stochastic) reaction of the enviroment to the agents action. For each state-action pair$(S=s, A=a) \in \mathcal S \times \mathcal A$ there is a probability distribution over$\mathcal S \times \mathbb R$:$P_0(\cdot \mid s, a)$ with the following semantics: For$U \in \mathcal S \times \mathbb R$ is$P_0(U \mid s, a)$ the probability that the next states and the reward$R$ belongs to the set$U$ given that the current state is$s$ and the action taken is$a$.

MDPs are models of the interaction between the enviroment and the agent.

### Agent and Environment

An agent takes an action in the given environment with the goal to maximize the long-term received reward (cumulative reward). This principle can be seen in figure 1 as an infinite loop.

At timestep$t$ the agent receives a state$S_{t}=s$ (for example a camera image) and performs an action$A_{t}=a$. In the next timestep$t+1$, a reward$R_{t+1}=r$ and the resulting new state$S_{t+1}=s'$ from the taken action$A_{t}=a$ of timestep$t$, is given to the agent. Notice, that the state and reward which are received in$t+1$ are a result of an action taken at timestep$t$, so the reward is not instantaneous but delayed.

If the random variable$S_t$ takes value$s$ we use the abbreviation$s_t$.

The MDP and agent together give rise to a sequence called trajectory that begins like this:

### Reward Function

From the definition we also have a reward function$\mathcal R(s,a)$ which is the expected reward for taking action$a$ in state$s$:

$\mathcal R(s,a) = \mathbb E [R \mid S = s, A =a]=\int_{\mathbb R} \sum_{\mathcal s' \in S} r \cdot P_0(s',r \mid s,a) dr$

We will explicit represent the function as matrix, so we will use the notation$\mathcal R_s^a$.

Analog we also have a function (of three variables) if the next state$S_{t+1}=s'$ at time$t+1$ is also given:

$\mathcal R(s, a, s') = \mathcal R_{s,s'}^a =\mathbb E [R_{t+1} \mid S_t = s, A_t =a, S_{t+1}=s'] = \int_{\mathbb R} r \cdot P_0(s', r \mid s,a) dr$

### Markov Property

A state$S_t=s$ includes all information about the past to predict future states. Additional information about the past such as previous states and actions doesn't give more information about future states.

In other word the states are Markovian, i.e.:

$\mathbb P[S_{t+1}, R_{t+1} \mid S_t, A_t] = \mathbb P[S_{t+1}, R_{t+1} \mid S_1, A_1 \dots , S_{t-1}, A_{t-1}, S_{t}, A_{t}]$

### State transition probability kernel

From$\mathcal P_0$ we can derive the state transition probability kernel$\mathcal P$ which for any$(s, a, s') \in \mathcal S \times \mathcal A \times \mathcal S$ triple gives the probability of moving from state$s$ to some other state$s'$ provided that action$a$ was chosen in$s$:

$P(s,a,s') = P_0(\{s'\} \times \mathbb R \mid a, s)$

## Example: Jacks Car Rental

(from [SUT98])

"Jack manages two locations for a nationwide car rental company. Each day, some number of customers arrive at each location to rent cars. If Jack has a car available, he rents it out and is credited$\$1$by the national company. If he is out of cars at that location, then the business is lost. Cars become available for renting the day after they are returned. To help ensure that cars are available where they are needed, Jack can move them between the two locations overnight, at a cost of SINGLESINGLE 2$ per car moved. We assume that the number of cars requested and returned at each location are Poisson random variables with mean$\lambda$. Suppose$\lambda$ is 3 and 4 for rental requests at the first and second locations and 3 and 2 for returns. To simplify the problem slightly, we assume that there can be no more than 20 cars at each location (any additional cars are returned to the nationwide company, and thus disappear from the problem) and a maximum of five cars can be moved from one location to the other in one night. We take the discount rate to be and formulate this as a continuing finite MDP, where the time steps are days, the state is the number of cars at each location at the end of the day, and the actions are the net numbers of cars moved between the two locations overnight."

• if more cars should be moved from a location as available, then it will charged the full action but only the available cars are moved.
• cars can be rent and returned at each location at all nationwide locations.
• We call the first location A and the second location B

We want to answer the following question:

• What is the optimal transfer policy of cars between branches?
REQUEST_RATE = (3., 4.)
RETURN_RATE  = (3., 2.)

GAMMA = 0.9
RENTAL_INCOME = 10
TRANSFER_COST = 2
TRANSFER_MAX  = 5
MAX_CAPACITY  = 20

# location indicies
A = 0
B = 1

### States

Question:

• What are the valid states of the Jacks car rental enviroment?

• Number of cars in each location ready for rent (e.g. the tuple (3,5) means 3 cars in location A and 5 cars in location B).

### Probability to be in a state

The probability for the states can be represented as a vector. For Jacks Car Rental:

$p(\vec s) = \begin{pmatrix} p(S=s_0) \\ p(S=s_1) \\ p(S=s_2) \\ \dots \\ p(S=s_{21}) \\ p(S=s_{22}) \\ \dots \\ p(S=s_{440}) \end{pmatrix} \begin{matrix}(0,0) \\ (0,1) \\ (0,2)\\ \dots \\ (1,0) \\ (1,1) \\ \dots \\ (20,20) \end{matrix}$

For the Jacks Car Rental problem it's sometimes easier to work with a state probability matrix:

$P(\hat S) = \begin{pmatrix} P(S=s_{0}) & P(S=s_{1})& \dots & P(S=s_{20}) \\ P(S=s_{21}) & P(S=s_{22}) & \dots & P(S=s_{41})\\ \vdots & \vdots & \ddots & \vdots\\ . & . & \dots & p(S=s_{440}) \end{pmatrix}$

The indices of$P(\hat S)$ correspond directly to the probability of the number of cars at each location.
Note that we can use np.reshape to switch between the different representations.

state_ = np.zeros([MAX_CAPACITY+1, MAX_CAPACITY+1])
state_[11, 15] = 1. # 11 cars at A and 15 cars at B
state_.shape
# Print all content of state_
state_
# TODO
state = state_.reshape(-1)
print(state.shape)
state_11_15 = state

We define a function to get the most probable location of a given state:

def get_most_probable_location(state):
i = state.argmax()
return (i//(MAX_CAPACITY+1), i%(MAX_CAPACITY+1))
get_most_probable_location(state)

We define a function to get the state vector for given$a$ and$b$, where$a$ is the amount of cars at$A$ and$b$ is the amount of cars at$B$.

def get_state_vector(a, b):
s = np.zeros((MAX_CAPACITY+1)**2)
s[a*(MAX_CAPACITY+1)+b] = 1
return s
assert get_most_probable_location(get_state_vector(11,12)) == (11,12)

### Actions

Actions are the nightly movements of the cars. We encode them as a number between -5 to 5, e.g.

• Action +3: move three cars from A to B.
• Action -1: move one car from B to A.
action_space = np.arange(-TRANSFER_MAX, TRANSFER_MAX+1)
print(action_space)  # cars moved
print(np.arange(11)) # action indices

### State transition probability kernel for Jacks Car Rental

Definition $\vec s' = P \vec s$

with

$\vec s$: probabilities for the states at time$t$ $\vec s'$: probabilities for the states at time$t+1$ *$P = \mathcal P$: State Transition Probability Kernel

In the following we construct the (transpose of the) state transition probability kernel. First note that the kernel decomposes as

$P = P_{ret} P_{req} P_{move}$

with

$P_{move}$: The kernel for the nightly moves according to the actions. $P_{req}$: The kernel for the requests of cars. *$P_{ret}$: The kernel for the returns of cars.

Note: for$P_{req}$ and$P_{ret}$ we don't have actions.

Form of the Transition Matrix:

• for earch old state we have a column
• for each new states we have a row

Note:
Here we have 441 possible states (for the old and new ones). So the transition matrix has dimension (441, 441). Each column of the transition matrix describes how a states is transformed.

### Request State Transition Probability Kernel

We define a function that calculates the transitions for one given location. Therefore, the Poisson probability mass function (PMF) is used. For further information about Poisson distribution in general, see e.g. here.

# construct request transitions for one location:
# e.g. state_1 = ((0,*), (1,*), ... (20,*))
#     are only the probabilities for location 1

MAX_PMF = 30

def get_request_transitions_for_one_location(loc):
"""
Construct transition matrix P_{to, from} for one location only for requests.
The matrix has form (21, 21).

Parameters
----------
loc : int
Location: 0 or 1

Returns
-------
numpy.ndarray
request transition matrix

"""
assert(loc==A or loc==B)
# transition matrix P_{to, from} for one location only requests
transition_matrix = np.zeros([MAX_CAPACITY+1, MAX_CAPACITY+1])

request_pmf = poisson.pmf(np.arange(MAX_PMF), REQUEST_RATE[loc])
np.testing.assert_almost_equal(request_pmf[-1], 0., decimal=12)
for i in range(MAX_CAPACITY+1):
for j in range(MAX_CAPACITY+1):
if j==0:
transition_matrix[i,j] = request_pmf[i:].sum()
elif j<=i:
transition_matrix[i,j] = request_pmf[i-j]
return transition_matrix.T
P_request_A_one_loc = get_request_transitions_for_one_location(A)
# all colums should sum to one
np.testing.assert_allclose(P_request_A_one_loc.sum(axis=0), 1.)
P_request_A_one_loc.shape

If we have e.g. eight cars at location A, after the renting the requested cars we get the following distribution:

plt.plot(np.arange(MAX_CAPACITY+1), P_request_A_one_loc[:,8], '*b')
plt.xticks(np.arange(0, 21, step=1))
plt.xlabel("number of cars")
plt.ylabel("probability");
P_request_A_one_loc[:,0]
P_request_A_one_loc[:,1]
# for testing the one location transition matricies
s = np.zeros(MAX_CAPACITY+1)
s[3] = 1
a = np.dot(P_request_A_one_loc, s)
np.testing.assert_almost_equal(a.sum(), 1.)
a

Note that the defined matrix has shape 21x21. So the index considers only the location A. A full state is given by the pair "(location A, location B)". So we must extend the matrix to a "full" transition matrix 441x441.

We define a function to retrieve the "full" transition matrix A for a given location.

def full_transition_matrix_A(transition_one_loc):
block_size = MAX_CAPACITY+1 # for convenience
transition_matrix = np.zeros([block_size**2, block_size**2])
for i in range(block_size):
transition_matrix[i:block_size**2: block_size,
i:block_size**2: block_size] = transition_one_loc
return transition_matrix
P_request_A = full_transition_matrix_A(P_request_A_one_loc)
P_request_A#.shape
# should mix only states of A:
np.testing.assert_almost_equal(np.dot(P_request_A, state_11_15).reshape(MAX_CAPACITY+1,-1).sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_request_A, state_11_15).reshape(MAX_CAPACITY+1,-1)[:,15].sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_request_A, state_11_15).reshape(MAX_CAPACITY+1,-1)[:12,15].sum(), 1.)

We define a function to retrieve the full transition matrix B for a given location. Note, that the positions of equal B locations in the full state vector a different a for location A.

Full state vector: $\begin{bmatrix}(0,0) \\ (0,1) \\ (0,2)\\ \dots \\ (1,0) \\ (1,1) \\ \dots \\ (20,20) \end{bmatrix}$

e.g.

• indices for location A=0:$0,1, \dots, 20$
• indices for location B=0:$0,21,42, \dots, 420$
def full_transition_matrix_B(transition_one_loc):
block_size = MAX_CAPACITY+1 # for convenience
transition_matrix = np.zeros([block_size**2, block_size**2])
for i in range(block_size):
transition_matrix[i*block_size:(i*block_size)+block_size,
i*block_size:(i*block_size)+block_size] = transition_one_loc
return transition_matrix
P_request_B_one_loc = get_request_transitions_for_one_location(1)
P_request_B = full_transition_matrix_B(P_request_B_one_loc)
# should mix only states of B:
np.testing.assert_almost_equal(np.dot(P_request_B, state_11_15).reshape(MAX_CAPACITY+1,-1).sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_request_B, state_11_15).reshape(MAX_CAPACITY+1,-1)[11].sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_request_B, state_11_15).reshape(MAX_CAPACITY+1,-1)[11,:16].sum(), 1.)
# with the two request matricies for each location we can construct the full request matrix
P_request = np.dot(P_request_A, P_request_B)
# The order of application shouldn't matter, so the commutator should be zero:
np.testing.assert_allclose(np.dot(P_request_A, P_request_B), np.dot(P_request_B, P_request_A))

### Return State Transition Probability Kernel

Similar to the requests, we define the return state transition probability kernel.

MAX_PMF = 30

def get_return_transition_matrix_one_location(loc):
"""
Construct transition matrix P_{to, from} for one location only for returns

Parameters
----------
loc : int
Location: 0 or 1

Returns
-------
numpy.ndarray
transition matrix

"""
assert(loc==0 or loc==1)
transition_matrix = np.zeros([MAX_CAPACITY+1, MAX_CAPACITY+1])

return_pmf = poisson.pmf(np.arange(MAX_PMF), RETURN_RATE[loc])
np.testing.assert_almost_equal(return_pmf[-1], 0., decimal=12)
for i in range(MAX_CAPACITY+1):
for j in range(MAX_CAPACITY+1):
if j==MAX_CAPACITY:
transition_matrix[i,j] = return_pmf[j-i:].sum()
elif j>=i and j<MAX_CAPACITY:
transition_matrix[i,j] = return_pmf[j-i]
return transition_matrix.T

P_return_A_one_loc = get_return_transition_matrix_one_location(0)
np.testing.assert_almost_equal(P_return_A_one_loc.sum(axis=0), 1.)
P_return_A = full_transition_matrix_A(P_return_A_one_loc)

# should mix only states of A:
np.testing.assert_almost_equal(np.dot(P_return_A, state_11_15).reshape(MAX_CAPACITY+1,-1).sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_return_A, state_11_15).reshape(MAX_CAPACITY+1,-1)[:,15].sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_return_A, state_11_15).reshape(MAX_CAPACITY+1,-1)[11:,15].sum(), 1.)
s = np.zeros(MAX_CAPACITY+1)
s[17] = 1
a = np.dot(P_return_A_one_loc, s)
st = np.dot(P_return_A , get_state_vector(17, 5))
np.testing.assert_almost_equal(a,st.reshape(MAX_CAPACITY+1,-1)[:,5])
P_return_B_one_loc = get_return_transition_matrix_one_location(B)
P_return_B = full_transition_matrix_B(P_return_B_one_loc)

# should mix only states of B:
np.testing.assert_almost_equal(np.dot(P_return_B, state_11_15).reshape(MAX_CAPACITY+1,-1).sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_return_B, state_11_15).reshape(MAX_CAPACITY+1,-1)[11].sum(), 1.)
np.testing.assert_almost_equal(np.dot(P_return_B, state_11_15).reshape(MAX_CAPACITY+1,-1)[11,15:].sum(), 1.)
P_return = np.dot(P_return_B, P_return_A)

np.testing.assert_allclose(np.dot(P_return_B, P_return_A), np.dot(P_return_A, P_return_B))

The combinations of requests and returns is given by the dot product:

$P_{ret/req} = P_{ret} P_{req}$

P_return_request = np.dot(P_return, P_request)

### Nightly Moves State Transition Probability Kernel

We implement$P_{move}$ as a 3d numpy array with indices [to_state_index, from_state_index, action_index].

def get_moves(a, b, action):
if action > 0: # from A to B
return min(a, action)
else:
return max(-b, action)

def get_nightly_moves():
transition_matrix = np.zeros([(MAX_CAPACITY+1)**2, (MAX_CAPACITY+1)**2, action_space.shape[0]])
for a in range(MAX_CAPACITY+1):
for b in range(MAX_CAPACITY+1):
for i, action in enumerate(action_space):
old_state_index = a*(MAX_CAPACITY+1)+b
moves = get_moves(a, b, action)
new_a = min(a - moves, MAX_CAPACITY)
new_b = min(b + moves, MAX_CAPACITY)
new_state_index = new_a *(MAX_CAPACITY+1) + new_b
transition_matrix[new_state_index, old_state_index, i] = 1.
return transition_matrix

Note:
actions and indices for actions differ, e.g. action 2 has index 2+5.

P_move = get_nightly_moves()

np.testing.assert_allclose(P_move.sum(axis=0), 1.)

# check some moves
# assert P_move[:,21*car_at_A+cars_at_B,action+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[new_cars_at_A, new_cars_at_B] == 1.
assert P_move[:,0,0].reshape(MAX_CAPACITY+1, -1)[0,0] == 1.

# e.g. from state [1,0] and action 1 => new state should be  [0,1]
assert P_move[:,21*1+0,1+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[0,1] == 1.

assert P_move[:,21*1+1,-2+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[2,0] == 1.
assert P_move[:,21*9+5,0+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[9,5] == 1.
assert P_move[:,21*9+5,3+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[6,8] == 1.
assert P_move[:,21*9+5,-3+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[12,2] == 1.
assert P_move[:,21*20+20,5+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[15,20] == 1.
assert P_move[:,21*20+20,-4+TRANSFER_MAX].reshape(MAX_CAPACITY+1, -1)[20,16] == 1.
P_move.shape

Construct the full transition probability kernel (request, returns and nightly shifts):

# this is the transpose of the state transition probability kernel
P = np.ndarray(((MAX_CAPACITY+1)**2, (MAX_CAPACITY+1)**2, action_space.shape[0]))
for i in range(action_space.shape[0]): # TODO: without a loop?
P[:,:,i] = np.dot(P_return_request, P_move[:,:,i])
P.shape

$P$ is the full state transition probability kernel for the Jack's car rental problem. $P$ has the following indices:$(s', s, a)$

np.testing.assert_almost_equal(P.sum(axis=0), 1.)
for s_a in range(21):
for s_b in range(21):
for a in range(11):
s_ = np.dot(P[:,:,a], get_state_vector(s_a, s_b))
np.testing.assert_almost_equal(s_.sum(), 1.0)
np.testing.assert_almost_equal(P.sum(axis=0), 1.)
def plot3d_over_states(f, zlabel="", ):
A = np.arange(0, MAX_CAPACITY+1)
B = np.arange(0, MAX_CAPACITY+1)
# B, A !!!
B, A = np.meshgrid(B, A)
V = f.reshape(MAX_CAPACITY+1,-1)
fig = plt.figure(figsize=(10,10))
#ax = fig.gca(projection='3d')
#surf = ax.plot_surface(A, B, V, rstride=1, cstride=1, cmap=cm.coolwarm,
#                   linewidth=0, antialiased=False)
#fig.colorbar(surf, shrink=0.5, aspect=5)
ax.scatter(A, B, V, c='b', marker='.')
ax.set_xlabel("cars at A")
ax.set_ylabel("cars at B")
ax.set_zlabel(zlabel)

ax.set_xticks(np.arange(0,21,1))
ax.set_yticks(np.arange(0,21,1))
#plt.xticks(np.arange(0,1,21))
#ax.view_init(elev=10., azim=10)

plt.show()
# do action 3 in cars_at_loc (10,5), i.e move three car from A to B:
s_ = np.dot(P[:,:,3+TRANSFER_MAX], get_state_vector(10, 5))
plot3d_over_states(s_, 'probability')
s_ = state_11_15
for i in range (500):
s_ = np.dot(P[:,:, 1 + TRANSFER_MAX], s_)

print (get_most_probable_location(s_))

### Reward Function

Let's construct the expected reward aka reward function

$\mathcal R(s,a) = \mathcal R_s^a = \mathbb E[R \mid s, a]$

def get_reward():

po = (poisson.pmf(np.arange(MAX_CAPACITY+1), REQUEST_RATE[A]),
poisson.pmf(np.arange(MAX_CAPACITY+1), REQUEST_RATE[B]))
for loc in (A,B):
for i in range(MAX_CAPACITY+1):
# the poisson mask contains the probability distribution for renting x cars (x column)
# in each row j, with j the number of cars available at the location

reward = np.zeros([MAX_CAPACITY+1, MAX_CAPACITY+1, 2*TRANSFER_MAX+1])
for a in range(MAX_CAPACITY+1):
for b in range(MAX_CAPACITY+1):
for action in range(-TRANSFER_MAX, TRANSFER_MAX+1):
moved_cars = min(action, a) if action>=0 else max(action, -b)
a_ = a - moved_cars
a_ = min(MAX_CAPACITY, max(0, a_))
b_ = b + moved_cars
b_ = min(MAX_CAPACITY, max(0, b_))
reward[a, b, action+TRANSFER_MAX] = (
(reward_a + reward_b) * RENTAL_INCOME -
np.abs(action) * TRANSFER_COST )
#if a==20 and b==20 and action==0:
#    print (a_,b_, action)
#    print (reward_a, reward_b)
#    print (reward[a, b, action+TRANSFER_MAX])

return reward
Reward = get_reward()
Reward = Reward.reshape(441,11)

### Policy

A policy$\pi$ is the behaviour of an agent. It maps states$s$ to actions$a$:

• Deterministic Policies:$a = \pi(s)$
• Stochastic Policies:$\pi(a\mid s) = P(a\mid s)$

### Markov Reward Process

A stationary policy$\pi$ and a MDP induce a MRP. Choose always the action$a$ according to the policy$\pi$.

A Markov Reward Process (MRP) is a tuple$\langle \mathcal{S}, \mathcal P_0'\rangle$ with

$\mathcal S$: finite set of states$s$ $\mathcal P'_0$: state transition Kernel matrix:$\mathcal P'_0$ assigns to each state$(S=s) \in \mathcal S$ a probability measure over$\mathcal S \times \mathbb R$:$P'_0(\cdot \mid s)$ with the following semantics: For$U \in \mathcal S \times \mathbb R$ is$P'_0(U \mid s)$ the probability that the next states and the reward$R$ belongs to the set$U$ given that the current state is$s$.

This implies again a reward function$\mathcal R^\pi(s)$ resp.$\mathcal R^\pi_s$ as for the MDP.

#### State Transition Probability Matrix for the MRP

$\mathcal P_{ss'}^\pi = \mathbb P [S_{t+1} = s' \mid S_t = s , a = \pi(s)]$

$\mathcal P^\pi = \begin{pmatrix} \mathcal P_{11} & \dots & \mathcal P_{1n} \\ \vdots & & \\ \mathcal P_{n1} & \dots & \mathcal P_{nn} \end{pmatrix}$

Note that the indicies of the matrix are$ss'$ in contrast to the above constructed state transition kernel which has the indicies$s'sa$.

Given a MDP$\langle \mathcal{S, A, \mathcal P_o} \rangle$ and a policy$\pi$:

• The state sequence$s_1, s_2, \dots$ is a Markov process
• The state and reward sequence$s_1, r_2, s_2, \dots$ is a Markov Reward Process where $\mathcal P^\pi_{s,s'} = \sum_{a\in \mathcal A} \pi(a \mid s) \mathcal P^a_{s,s'}$ $\mathcal R^\pi_{s} = \sum_{a\in \mathcal A} \pi(a \mid s) \mathcal R^a_{s}$
# choose in each state action 2 (move two cars from A to B)
policy = np.ones((MAX_CAPACITY+1)**2, dtype=int) * 2
policy.shape
def get_transition_kernel_for_policy(policy):
# use advanced indexing to get the entiers
return P[:, range((MAX_CAPACITY+1)**2), policy+TRANSFER_MAX]
P_pi = get_transition_kernel_for_policy(policy)
np.testing.assert_allclose(P_pi.sum(axis=0), 1.)
Reward.shape
def get_P_reward_for_policy(policy):
P_pi = get_transition_kernel_for_policy(policy)
return P_pi, Reward[range((MAX_CAPACITY+1)**2), policy+TRANSFER_MAX]
get_P_reward_for_policy(policy)[1].shape
policy = np.ones((MAX_CAPACITY+1)**2, dtype=int) * 5
P_pi, reward = get_P_reward_for_policy(policy)
plot3d_over_states(reward, 'avg reward')

### Total Discounted Reward

The return$G_t$ is defined as the total discounted reward:

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$

#### Sum of discounted rewards is finite

Note that with all rewards$R_t>0$

$\sum_{t=0}^\infty R_t = \infty$

Independent of the actual values of$R_t$. So we can't compare the (expected) reward of different states respectivly policies (which cases the state sequence).

But $\sum_{t=0}^\infty \gamma^t R_t$

with the discount$\gamma$ $0<\gamma<1$

has as result a finite number, because with the maximum reward$R_{max} = \max_t (R_t)$ in the serie it is bounded by

$\sum_{t=0}^\infty \gamma^t R_t \leq \sum_{t=0}^\infty \gamma^t R_{max} = \frac{R_{max}}{1-\gamma}$

#### Proof of$\sum_i \gamma^i = 1/(1-\gamma)$

$x = \gamma^0 +\gamma^1 + \gamma^2 + \dots$

$\gamma^0 +\gamma^1 + \gamma^2 + \dots = \gamma^0 + \gamma (\gamma^0 +\gamma^1 + \gamma^2 + \dots)$

$x = \gamma^0 + \gamma x = 1 + \gamma x$

$x(1-\gamma) = 1$

$x = \frac{1}{1-\gamma}$

### Value functions

The state-value function$v_\pi (s)$ of an MDP is the expected return starting from state$s$, and then follow policy$\pi$

$v_\pi (s) = \mathbb E_\pi[G_t \mid S_t=s] = \mathbb E \left[ \sum_{t'=t}^\infty \gamma^{t'-t} R_{t'+1} \mid S_t=s \right], s \in \mathcal S$

The value function can be decomposed into an immediate part and the discounted value function of the successor states:

$v_\pi(s) = \mathbb E[G_t \mid S_t =s] \\ = \mathbb E [R_{t+1}+γR_{t+2}+\gamma^2 R_{t+3} + \dots \mid S_t =s] \\ = \mathbb E [R_{t+1} + \gamma (R_{t+2}+\gamma R_{t+3} + \dots ) \mid S_t = s] \\ = \mathbb E [R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ = \mathbb E [ R_{t+1} \mid S_t = s]+ \gamma v_\pi(S_{t+1} )$

so, we have the Bellmann Equation (for deterministic policies):

$v_\pi(s) = \mathcal R_s^\pi + \gamma \sum_{s'\in \mathcal S} P_{ss'}^\pi v_\pi (s')$

Note:$v(s')$ are the values of the successor states of$s$, so in$\sum_{s'\in \mathcal S} P_{ss'} v(s')$ the weights$P_{ss'}$ of the values$v(s')$ are the transitions back in time.

#### Bellman Equation

also for non deterministic policies:

$v_\pi(s) = \sum_a \pi(a \mid s) \left( \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} v_\pi(s')\right)$

Bellmann equations in vector-matrix form:

$\vec v = \mathcal R^{\pi} + \gamma P^{\pi} \vec v$

Here, we can directly solve the Bellmann equation:

$\vec v = (I - \gamma \mathcal P^\pi)^{-1} \mathcal R^\pi$

def evaluate_policy(policy):
P_pi_transpose, reward = get_P_reward_for_policy(policy)

### Here we must use P_pi_transpose.T - transformation back in time to the previous state!
values = np.dot(np.linalg.inv(np.eye((MAX_CAPACITY+1)**2) - GAMMA * P_pi_transpose.T), reward)
return values
policy_ = np.zeros(((MAX_CAPACITY+1)**2), dtype=int)
values = evaluate_policy(policy_)
plot3d_over_states(values, 'v')

For large state spaces computing the inverse is costly in terms of space and time. However, the bellman equation can be solved by an iteration:

### Policy Evaluation

Computing the state-value function$v^\pi(s)$ for an arbitrary policy by an iterative application of Bellman expectation backup is called policy evaluation:

*$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow \dots \rightarrow v_\pi$

• loop until convergence (using synchronous backups)

• at each iteration$k+1$
• for all states$s \in \mathcal S$
• update$v_{k+1}(s)$ from$v_k(s')$, where$s'$ is a successor state of$s$

$\vec v_{k+1} = \vec {\mathcal R}^\pi + \gamma {\mathcal P}^\pi \vec v_{k}$

def evaluate_policy_by_iteration(policy, values = np.zeros((MAX_CAPACITY+1)**2)):
P_pi, reward = get_P_reward_for_policy(policy)
converged = False
while not converged:
new_values = reward + GAMMA * np.dot (P_pi.T, values)
if np.allclose(new_values, values, rtol=1e-07, atol=1e-10):
converged = True
values = new_values
return values
values_ = evaluate_policy_by_iteration(policy_)
np.testing.assert_almost_equal(values, values_, decimal=3)

### Optimal Value Function

$v^* (s) = \max_\pi v_\pi(s)$

The optimal value$v^*(s)$ of state$s \in \mathcal S$ is defined as the highest achievable expected return when the process is started from state$s$. The function$v^* : \mathcal S \rightarrow \mathbb R$ is called the optimal value function.

### Policy Iteration

• Starting with an arbitrary policy
• Iteration until the values converge (to the optimal policy). Alternating sequence of

• Policy Evaluation : Compute the values of the policy
• Greedy Policy Improvement: Use the "best" action in each state, i.e. chose the action which result in the highest return for each state.

#### Greedy Policy Improvement

For greedy policy improvement we need the model (transition probabilities) if we are using the value function$v(s)$: For each action$a$ we compute the probabilities of the next states and calculate the average value of the discounted return.

If we start from state$s$ with action$a$, and then follow policy$\pi$ we get as expected return

$q_\pi (s,a) = \mathbb E \left[ R\mid s,a \right]+ \mathbb E \left[ \gamma \sum_{s'\in \mathcal S} P_{ss'}^\pi v_\pi (s') \right]$ $q_\pi (s,a)$ is called the action-value function$q_\pi (s,a)$.

Here, we compute$q$ explicitly for each state$s$ and action$a$ (respectivly in matrix form). For each state we chose the action that results in the highest value.

To understand why Greedy Policy Improvement works read the section of Sutton's book about the policy improvement.

def greedy_improve(values, P=P):
P_ = P.transpose(1, 0, 2) # we used the model for improvement
all_pure_states = np.eye((MAX_CAPACITY+1)**2)
new_states = np.dot(all_pure_states, P_)
q = np.dot(new_states.transpose(2,1,0), values)
q = q.T + Reward
policy_indices = np.argmax(q, axis=1)
policy = policy_indices - TRANSFER_MAX
return policy
def improve_policy(policy):
values = evaluate_policy_by_iteration(policy)
not_converged = True
while not_converged:
print (values.mean())
new_policy = greedy_improve(values)
#new_values = evaluate_policy(new_policy)
new_values = evaluate_policy_by_iteration(new_policy, values)
if np.allclose(new_values, values, rtol=1e-02):
not_converged = False
values = new_values
return new_policy
def plot_policy(policy):
A = np.arange(0, MAX_CAPACITY+1)
B = np.arange(0, MAX_CAPACITY+1)
A, B = np.meshgrid(A, B)
Po = policy.reshape(MAX_CAPACITY+1,-1)
levels = range(-5,6,1)
plt.figure(figsize=(7,6))
CS = plt.contourf(A, B, Po, levels)
cbar = plt.colorbar(CS)
cbar.ax.set_ylabel('actions')
#plt.clabel(CS, inline=1, fontsize=10)
plt.title('Policy')
plt.xlabel("cars at B")
plt.ylabel("cars at A")
policy = improve_policy(policy)
values_ = evaluate_policy_by_iteration(policy)
plot3d_over_states(values_, 'v')
plot_policy(policy)

## Q-Function

The action-value function$q_\pi (s,a)$ of an MDP is the expected return starting from state$s$ with action$a$, and then follow policy$\pi$

$q^\pi (s,a) = \mathbb E_\pi[G_t \mid S_t=s, A_t=a]$

### Optimal action-value function

$q^* (s, a) = \max_\pi q^\pi(s, a)$

The optimal action-value$q^*(s, a)$ of state-action pair$(s,a) \in \mathcal S \times \mathcal A$ gives the highest achievable expected return when the process is started from state$s$, and the first action chosen is$a$. The function$q^* : \mathcal S \times \mathcal A \rightarrow \mathbb R$ is called the optimal action-value function.

### Connection between optimal value- and action-value function

$v^*(s) = \max_{a \in \mathcal A} q^*(s,a), s \in \mathcal S$

$q^*(s,a) = \mathcal R_s^a + \gamma\sum_{s' \in \mathcal S} P(s,a,s')v^*(s') ; s \in \mathcal S, a \in \mathcal A$

### Bellman Equation for Q

$q_\pi(s, a) = \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} \left( \sum_{a'\in \mathcal A} \pi(a' \mid s') q_\pi(s',a') \right)$

for a deterministic policy:

$q_\pi(s, a) = \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} q_\pi(s',\pi(s'))$

$\hat Q^\pi = \hat R + \gamma \mathcal P \vec Q^\pi_\pi$

with

*$\vec \pi$: Policy vector

• Matricies$\hat Q^\pi, \hat R$ with entries$\cdot_{sa}$
• 3d Array$\mathcal P$ with entries$\cdot_{sas'}$ *$\vec Q^\pi_\pi = \vec v^\pi$

### Policy Evaluation for Q

Computing the state-action-value function$q^\pi(s, a)$ for an arbitrary policy by an iterative application of Bellman expectation backup is also called policy evaluation:

*$q_1 \rightarrow q_2 \rightarrow q_3 \rightarrow \dots \rightarrow q_\pi$

• using synchronous backups

• at each iteration$k+1$
• for all states$s \in \mathcal S$ and$a \in \mathcal A$
• update$q_{k+1}(s, a)$ from$q_k(s', \cdot)$, where$s'$ is a successor state of$s$.

$\hat Q^{k+1} = \hat R + \gamma \mathcal P \vec Q^k_{k}$

# Iterative update of the bellmann equation for Q
def evaluate_policy_Q_by_iteration(policy, Q = np.zeros([(MAX_CAPACITY+1)**2, 2*TRANSFER_MAX+1])):
converged = False
P_ = P.transpose(1,2,0)
while not converged:
policy_index = policy + TRANSFER_MAX
Q_pi = Q[np.arange((MAX_CAPACITY+1)**2), policy_index]
new_Q = Reward + GAMMA * np.dot(P_, Q_pi)
if np.allclose(new_Q, Q):
converged = True
Q = new_Q
return Q

### Policy Iteration for Q

• Starting with an arbitrary policy
• Iteration until the values converge (to the optimal policy). Alternating sequence of

• Policy Evaluation : Compute the values of the policy
• Greedy Policy Improvement: *$\pi'(s) = \text{arg} \max_{a \in \mathcal A} q^\pi(s,a)$

• Note: Here we don't use the (transition) model.
def greedy_improve_Q(Q):
return np.argmax(Q, axis=1) - TRANSFER_MAX

policy = np.ones((MAX_CAPACITY+1)**2, dtype=int) * 0
Q = np.zeros([(MAX_CAPACITY+1)**2, 2*TRANSFER_MAX+1])

converged=False
while not converged:
new_Q = evaluate_policy_Q_by_iteration(policy, Q)
policy = greedy_improve_Q(Q)
if np.allclose(new_Q, Q):
converged = True
Q = new_Q

plot_policy(policy)

### Bellman Optimality Equation

$v^*(s) = \max_a \mathbb E \left[ R_{t+1} + \gamma v^*(S_{t+1}) \mid S_t = s, A_t = a\right] \\ = \max_a \left(\mathcal R^a_{s} + \gamma \sum_{s'} P_{ss'}^a \mathcal v^*(S_{t+1}=s')\right)$

$q^*(s, a) = \mathbb E \left[ R_{t+1} + \gamma \max_{a'} q^*(S_{t+1},A_{t+1}=a') \mid S_t = s, A_t = a\right] \\ = \mathcal R^a_{s} + \gamma \sum_{s'} P_{ss'}^a \mathcal \max_{a'} q^*(S_{t+1}=s',A_{t+1}=a')$

### Value Iteration

From the Bellmann optimality equation we can derive an iterative method to find the optimal value function:

$v_{k+1}(S_t = s) = \max_a \mathbb E[R_{t+1} + \gamma v_k(S_{t+1}=s') \mid S_t=s, A_t=a] \\ = \max_a \left( \mathcal R_{s}^a + \gamma \sum_{s'} \mathcal P_{ss'}^a v_k(s')\right)$

converged = False
values = np.zeros((MAX_CAPACITY+1)**2)
P_ = P.transpose(1,2,0)
while not converged:
rs = Reward + GAMMA * np.dot(P_, values)
new_values = np.max(rs, axis = 1)
if np.allclose(values, new_values):
converged = True
values = new_values
policy = np.argmax(Reward + GAMMA * np.dot(P_, values) , axis=1) - TRANSFER_MAX
plot_policy(policy)

## Summary and Outlook

Here we introduced MDPs as a model of the agent-environment interaction. We showed how to construct an explicit transition model on an example of R. Suttons Book "Introduction to Reinforcement Learning".

We also showed how to solve the corresponding optimization problem by dynamic programming.

In the next section no explicit transition kernel will be given. However, the interaction of the environment and the agent is also defined by a MDP. However, without the explicit transition kernel only tranjectories (as data) from the interaction are known. Such problems can not be solved by dynamic programming. Here, techniques from reinforcement learning are needed.

## Literature

The following license applies to the complete notebook, including code cells. It does however not apply to any referenced external media (e.g., images).

Introduction to Reinforcement Learning

format: plain


text:
I have forgotten

• https://me.yahoo.com
COST (GBP)
3.74
6.12
0

# beta reg

viewed 1935 times and licensed 120 times
The regularized incomplete Beta integral
Controller: CodeCogs

C++
Excel

## Overview

These function compute the regularized incomplete beta integral of the arguments, evaluated from zero to x. This is occasionally also called the beta function ratio, given that it returns the probability that a random variable drawn from a beta distribution with parameters a and b will be less that or equal to x.

This ratio (or regularization) function is calculated by dividing the incomplete beta integral by the complete beta integral, i.e.

If the incomplete beta integral is defined by:

and the complete beta integral is defined by:

where  is the Maths/Special/Gamma/Gamma function.

Therefore the regularized beta integral is:

where .

All the functions are only valid in the range 0 <= x <= 1. In this implementation a and b are restricted to positive values.

The integral from x to 1 may be obtained by the symmetry relation, i.e.
1 - beta_reg( x, a, b )  =  beta_reg( 1-x, a, b ).

## Example:

The following example evaluates the upper regularized incomplete beta integral for 10 points equally spaced in the interval from 0 to 1.
#include <stdio.h>
#include <codecogs/maths/special/gamma/beta_reg.h>
void main()
{
for (double x=0; x<1; x+=0.1)
{
double y = Maths::Special::Gamma::beta_reg(x, 2, 1, true);
printf("beta_reg(2, %.1lf, 1, true) = %lf\n", x,y);
}
}
Output:
beta_reg(2, 0.0, 1, true) = 1.000000
beta_reg(2, 0.1, 1, true) = 0.990000
beta_reg(2, 0.2, 1, true) = 0.960000
beta_reg(2, 0.3, 1, true) = 0.910000
beta_reg(2, 0.4, 1, true) = 0.840000
beta_reg(2, 0.5, 1, true) = 0.750000
beta_reg(2, 0.6, 1, true) = 0.640000
beta_reg(2, 0.7, 1, true) = 0.510000
beta_reg(2, 0.8, 1, true) = 0.360000
beta_reg(2, 0.9, 1, true) = 0.190000
beta_reg(2, 1.0, 1, true) = 0.000000

## Fraction Exp

 doublefraction_exp( double x double a double b bool inverse = false )
Computes using continued fraction expansion that main term need to compute the incomplete Beta integral at the extremes.

Methodolgy

### Parameters

 x upper limit of integration. (0
##### Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

## BetaLower Reg Pow

 doublebetaLower_reg_pow( double x double a double b )
Power series for the regularized incomplete beta integral,, Use when  is little and x is not too close to 1.

### Parameters

 x upper limit of integration (0

### Authors

Stephen L.Moshier. Copyright 1984, 1987, 1989, 1992, 2000
##### Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

## Beta Reg

 doublebeta_reg( double x double a double b bool upper = false )
Computes the regularize beta integral using a variety of method depending on the input values:
• When b*x<=1 and x<0.95 then the function is calculated using the power series expansion defined in betaLower_reg_pow.
• If x is greater than the mean of the beta function, i.e.

Then the values of a and b are reversed and the calculation proceeds as before only with x=1-x.
• A second attempt is then made to use the power series expansion within the range b*x<=1 and x<0.95.
• Failing this a fractional expansion is used within the tails of this function.

### Parameters

 x the value at which to evaluate the function, must be in range 0..1 a the 1st number of degrees of freedom, must be strictly positive b the 2nd number of degrees of freedom, must be strictly positive upper Default value = false

### Authors

Stephen L.Moshier. Copyright 1984, 1987, 1989, 1992, 2000
##### Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.


text:
# Math Help - Please help me answer the querry #1 i have posted. (order relation)

1. ## Please help me answer the querry #1 i have posted. (order relation)

1. Let A be the family of all subsets A of the natural numbers N where A has the following properties: A is finite and the greatest common divisor of the elements of A is 1.

a. State whether or not each of the following subsets of N belongs to A: (2,3,8),(2,3,5,8),(2,5),2,3,4,5,...),(4,6,8) and (2,3).

b. Order A by set inclusion, that is, X precedes Y if X is a subset of Y, and let B be the subfamily of A which consists of the sets in (a) which belongs to A. Construct a diagram of B.

2. ## Re: Please help me answer the querry #1 i have posted. (order relation)

Originally Posted by jakeshinryu
1. Let A be the family of all subsets A of the natural numbers N where A has the following properties: A is finite and the greatest common divisor of the elements of A is 1.

a. State whether or not each of the following subsets of N belongs to A: (2,3,8),(2,3,5,8),(2,5),2,3,4,5,...),(4,6,8) and (2,3).
Set elements should be surrounded by curly braces, not by parentheses.

Let's consider the set {2, 3}. Are you really asking if this set is finite and the greatest common divisor of its elements is 1? If so, then do you know what the the greatest common divisor is? If so, then what exactly is your difficulty? If you know whether {2, 3} is in A, then which set from (a) presents a problem?


text:
SPSS TUTORIALS BASICS ANOVA REGRESSION FACTOR CORRELATION

# Chi-Square Goodness-of-Fit Test – Simple Tutorial

A chi-square goodness-of-fit test examines if a categorical variable
has some hypothesized frequency distribution in some population.
The chi-square goodness-of-fit test is also known as

• one-sample chi-square test (SPSS) or
• multinomial test (JASP).

A car manufacturer wants to launch a campaign for a new car. They'll show advertisements -or “ads”- in 4 different sizes. For ad each size, they have 4 ads that try to convey some message such as “this car is environmentally friendly”. They then asked N = 80 people which ad they liked most. The data thus obtained are in this Googlesheet, partly shown below.

So which ads performed best in our sample? Well, we can simply look up which ad was preferred by most respondents: the ad having the highest frequency is the mode for each ad size.

So let's have a look at the frequency distribution for the first ad size -ad1- as visualized in the bar chart shown below.

## Observed Frequencies and Bar Chart

The observed frequencies shown in this chart are

1. Safe and Family Friendly: 6
2. Luxurious and Masculine: 29
3. Environmentally Friendly: 16
4. Spacious and Convenient: 29

Note that ad1 has a bimodal distribution: ads 2 and 4 are both winners with 29 votes. However, our data only hold a sample of N = 80. So can we conclude that ads 2 and 4
also perform best in the entire population?
The chi-square goodness-of-fit answers just that. And for this example, it does so by trying to reject the null hypothesis that all ads perform equally well in the population.

## Null Hypothesis

Generally, the null hypothesis for a chi-square goodness-of-fit test is simply

$$H_0: P_{01}, P_{02},...,P_{0m},\; \sum_{i=0}^m\biggl(P_{0i}\biggr) = 1$$

where $$P_{0i}$$ denote population proportions for $$m$$ categories in some categorical variable. You can choose any set of proportions as long as they add up to one. In many cases, all proportions being equal is the most likely null hypothesis.
For a dichotomous variable having only 2 categories, you're better off using

Anyway, for our example, we'd like to show that some ads perform better than others. So we'll try to refute that our 4 population proportions are all equal and -hence- 0.25.

## Expected Frequencies

Now, if the 4 population proportions really are 0.25 and we sample N = 80 respondents, then we expect each ad to be preferred by 0.25 · 80 = 20 respondents. That is, all 4 expected frequencies are 20. We need to know these expected frequencies for 2 reasons:

• computing our test statistic requires expected frequencies and
• the assumptions for the chi-square goodness-of-fit test involve expected frequencies as well.

## Assumptions

The chi-square goodness-of-fit test requires 2 assumptions2,3:

1. independent observations;
2. for 2 categories, each expected frequency $$Ei$$ must be at least 5.
For 3+ categories, each $$Ei$$ must be at least 1 and no more than 20% of all $$Ei$$ may be smaller than 5.

The observations in our data are independent because they are distinct persons who didn't interact while completing our survey. We also saw that all $$Ei$$ are (0.25 · 80 =) 20 for our example. So this second assumption is met as well.

## Formulas

We'll first compute the $$\chi^2$$ test statistic as

$$\chi^2 = \sum\frac{(O_i - E_i)^2}{E_i}$$

where

$$\chi^2 = \frac{(16 - 20)^2}{20} + \frac{(29 - 20)^2}{20} + \frac{(9 - 20)^2}{20} + \frac{(29 - 20)^2}{20} = 18.7$$

If all assumptions have been met, $$\chi^2$$ approximately follows a chi-square distribution with $$df$$ degrees of freedom where

$$df = m - 1$$

for $$m$$ frequencies. Since we have 4 frequencies for 4 different ads,

$$df = 4 - 1 = 3$$

for our example data. Finally, we can simply look up the significance level as

$$P(\chi^2(3) > 18.7) \approx 0.00032$$

We ran these calculations in this Googlesheet shown below.

So what does this mean? Well, if all 4 ads are equally preferred in the population, there's a 0.00032 chance of finding our observed frequencies. Since p < 0.05, we reject the null hypothesis. Conclusion: some ads are preferred by more people than others in the entire population of readers.

Right, so it's safe to assume that the population proportions are not all equal. But precisely how different are they? We can express this in a single number: the effect size.

## Effect Size - Cohen’s W

The effect size for a chi-square goodness-of-fit test -as well as the chi-square independence test- is Cohen’s W. Some rules of thumb1 are that

• Cohen’s W = 0.10 indicates a small effect size;
• Cohen’s W = 0.30 indicates a medium effect size;
• Cohen’s W = 0.50 indicates a large effect size.

Cohen’s W is computed as

$$W = \sqrt{\sum_{i = 1}^m\frac{(P_{oi} - P_{ei})^2}{P_{ei}}}$$

where

• $$P_{oi}$$ denote observed proportions and
• $$P_{ei}$$ denote expected proportions under the null hypothesis for
• $$m$$ cells.

For ad1, the null hypothesis states that all expected proportions are 0.25. The observed proportions are computed from the observed frequencies (see screenshot below) and result in

$$W = \sqrt{\frac{(0.2 - 0.25)^2}{0.25} +\frac{(0.3625 - 0.25)^2}{0.25} +\frac{(0.075 - 0.25)^2}{0.25} +\frac{(0.3625 - 0.25)^2}{0.25} } =$$

$$W = \sqrt{0.234} = 0.483$$

We ran these computations in this Googlesheet shown below.

For ad1, the effect size $$W$$ = 0.483. This indicates a large overall difference between the observed and expected frequencies.

## Power and Sample Size Calculation

Now that we computed our effect size, we're ready for our last 2 steps. First off, what about power? What's the probability demonstrating an effect if

• we test at α = 0.05;
• we have a sample of N = 80;
• df = 3 (our outcome variable has 4 categories);
• we don't know the population effect size $$W$$?

The chart below -created in G*Power- answers just that.

Some basic conclusions are that

• power = 0.98 for a large effect size;
• power = 0.60 for a medium effect size;
• power = 0.10 for a small effect size.

These outcomes are not too great: we only have a 0.60 probability of rejecting the null hypothesis if the population effect size is medium and N = 80. However, we can increase power by increasing the sample size. So which sample sizes do we need if

• we test at α = 0.05;
• we want to have power = 0.80;
• df = 3 (our outcome variable has 4 categories);
• we don't know the population effect size $$W$$?

The chart below shows how required sample sizes decrease with increasing effect sizes.

Under the aforementioned conditions, we have power ≥ 0.80

• for a large effect size if N = 44;
• for a medium effect size if N = 122;
• for a small effect size if N = 1091.

## References

1. Cohen, J (1988). Statistical Power Analysis for the Social Sciences (2nd. Edition). Hillsdale, New Jersey, Lawrence Erlbaum Associates.
2. Siegel, S. & Castellan, N.J. (1989). Nonparametric Statistics for the Behavioral Sciences (2nd ed.). Singapore: McGraw-Hill.
3. Warner, R.M. (2013). Applied Statistics (2nd. Edition). Thousand Oaks, CA: SAGE.

# Tell us what you think!

*Required field. Your comment will show up after approval from a moderator.

# THIS TUTORIAL HAS 9 COMMENTS:

• ### By Olorunfemi Adebayo on April 9th, 2020

Good explaination

• ### By Manuel on April 14th, 2020

I understand the theory, but, I miss an explanation about why this test is a one-tailed test, namely, with a right-sided tail. Wouldn't it be possible to work as a two-sided test?
Thank you

• ### By Ruben Geert van den Berg on April 15th, 2020

Hi Manuel!

Great question!

The basic answer is that for a t-distribution and a standard normal distribution, very low or very high outcomes are both unlikely: they both indicate large differences between the null hypothesis and the data. Both distributions are symmetrical around zero which indicates no deviation from the null hypothesis at all.

Now, the f-distribution and chi-square distribution are basically squared distributions. So very low values -after squaring- become very high values. That's why both have a minimum of zero which indicates no deviation from the null hypothesis at all and p = 1.000.

As a result, larger deviations -in whatever direction- from the null hypothesis always result in larger chi-square or F-values. So for these distributions we always report right-tailed significance.

This was also explained in Statistical Significance - What Does It Really Mean?

Hope that helps!

SPSS tutorials

• ### By Muhammed Tahir Muhammed on April 6th, 2022

This analysis and explanation are of standard. Please I will like to be receiving mail from you mentor.