text:
# Theoretical Uncertainty and Uncertain Theory

Yesterday, Fermilab’s Muon g-2 experiment announced a new measurement of the magnetic moment of the muon, a number which describes how muons interact with magnetic fields. For what might seem like a small technical detail, physicists have been very excited about this measurement because it’s a small technical detail that the Standard Model seems to get wrong, making it a potential hint of new undiscovered particles. Quanta magazine has a great piece on the announcement, which explains more than I will here, but the upshot is that there are two different calculations on the market that attempt to predict the magnetic moment of the muon. One of them, using older methods, disagrees with the experiment. The other, with a new approach, agrees. The question then becomes, which calculation was wrong? And why?

What does it mean for a prediction to match an experimental result? The simple, wrong, answer is that the numbers must be equal: if you predict “3”, the experiment has to measure “3”. The reason why this is wrong is that in practice, every experiment and every prediction has some uncertainty. If you’ve taken a college physics class, you’ve run into this kind of uncertainty in one of its simplest forms, measurement uncertainty. Measure with a ruler, and you can only confidently measure down to the smallest divisions on the ruler. If you measure 3cm, but your ruler has ticks only down to a millimeter, then what you’re measuring might be as large as 3.1cm or as small as 2.9 cm. You just don’t know.

This uncertainty doesn’t mean you throw up your hands and give up. Instead, you estimate the effect it can have. You report, not a measurement of 3cm, but of 3cm plus or minus 1mm. If the prediction was 2.9cm, then you’re fine: it falls within your measurement uncertainty.

Measurements aren’t the only thing that can be uncertain. Predictions have uncertainty too, theoretical uncertainty. Sometimes, this comes from uncertainty on a previous measurement: if you make a prediction based on that experiment that measured 3cm plus or minus 1mm, you have to take that plus or minus into account and estimate its effect (we call this propagation of errors). Sometimes, the uncertainty comes instead from an approximation you’re making. In particle physics, we sometimes approximate interactions between different particles with diagrams, beginning with the simplest diagrams and adding on more complicated ones as we go. To estimate the uncertainty there, we estimate the size of the diagrams we left out, the more complicated ones we haven’t calculated yet. Other times, that approximation doesn’t work, and we need to use a different approximation, treating space and time as a finite grid where we can do computer simulations. In that case, you can estimate your uncertainty based on how small you made your grid. The new approach to predicting the muon magnetic moment uses that kind of approximation.

There’s a common thread in all of these uncertainty estimates: you don’t expect to be too far off on average. Your measurements won’t be perfect, but they won’t all be screwed up in the same way either: chances are, they will randomly be a little below or a little above the truth. Your calculations are similar: whether you’re ignoring complicated particle physics diagrams or the spacing in a simulated grid, you can treat the difference as something small and random. That randomness means you can use statistics to talk about your errors: you have statistical uncertainty. When you have statistical uncertainty, you can estimate, not just how far off you might get, but how likely it is you ended up that far off. In particle physics, we have very strict standards for this kind of thing: to call something new a discovery, we demand that it is so unlikely that it would only show up randomly under the old theory roughly one in a million times. The muon magnetic moment isn’t quite up to our standards for a discovery yet, but the new measurement brought it closer.

The two dueling predictions for the muon’s magnetic moment both estimate some amount of statistical uncertainty. It’s possible that the two calculations just disagree due to chance, and that better measurements or a tighter simulation grid would make them agree. Given their estimates, though, that’s unlikely. That takes us from the realm of theoretical uncertainty, and into uncertainty about the theoretical. The two calculations use very different approaches. The new calculation tries to compute things from first principles, using the Standard Model directly. The risk is that such a calculation needs to make assumptions, ignoring some effects that are too difficult to calculate, and one of those assumptions may be wrong. The older calculation is based more on experimental results, using different experiments to estimate effects that are hard to calculate but that should be similar between different situations. The risk is that the situations may be less similar than expected, their assumptions breaking down in a way that the bottom-up calculation could catch.

None of these risks are easy to estimate. They’re “unknown unknowns”, or rather, “uncertain uncertainties”. And until some of them are resolved, it won’t be clear whether Fermilab’s new measurement is a sign of undiscovered particles, or just a (challenging!) confirmation of the Standard Model.

# Is Outreach for Everyone?

Betteridge’s law applies here: the answer is “no”. It’s a subtle “no”, though.

As a scientist, you will always need to be able to communicate your work. Most of the time you can get away with papers and talks aimed at your peers. But the longer you mean to stick around, the more often you will have to justify yourself to others: to departments, to universities, and to grant agencies. A scientist cannot survive on scientific ability alone: to get jobs, to get funding, to survive, you need to be able to promote yourself, at least a little.

Self-promotion isn’t outreach, though. Talking to the public, or to journalists, is a different skill from talking to other academics or writing grants. And it’s entirely possible to go through an entire scientific career without exercising that skill.

That’s a reassuring message for some. I’ve met people for whom science is a refuge from the mess of human interaction, people horrified by the thought of fame or even being mentioned in a newspaper. When I meet these people, they sometimes seem to worry that I’m silently judging them, thinking that they’re ignoring their responsibilities by avoiding outreach. They think this in part because the field seems to be going in that direction. Grants that used to focus just on science have added outreach as a requirement, demanding that each application come with a plan for some outreach project.

I can’t guarantee that more grants won’t add outreach requirements. But I can say at least that I’m on your side here: I don’t think you should have to do outreach if you don’t want to. I don’t think you have to, just yet. And I think if grant agencies are sensible, they’ll find a way to encourage outreach without making it mandatory.

I think that overall, collectively, we have a responsibility to do outreach. Beyond the old arguments about justifying ourselves to taxpayers, we also just ought to be open about what we do. In a world where people are actively curious about us, we ought to encourage and nurture that curiosity. I don’t think this is unique to science, I think it’s something every industry, every hobby, and every community should foster. But in each case, I think that communication should be done by people who want to do it, not forced on every member.

I also think that, potentially, anyone can do outreach. Outreach can take different forms for different people, anything from speaking to high school students to talking to journalists to writing answers for Stack Exchange. I don’t think anyone should feel afraid of outreach because they think they won’t be good enough. Chances are, you know something other people don’t: I guarantee if you want to, you will have something worth saying.

# Redefining Fields for Fun and Profit

When we study subatomic particles, particle physicists use a theory called Quantum Field Theory. But what is a quantum field?

Some people will describe a field in vague terms, and say it’s like a fluid that fills all of space, or a vibrating rubber sheet. These are all metaphors, and while they can be helpful, they can also be confusing. So let me avoid metaphors, and say something that may be just as confusing: a field is the answer to a question.

Suppose you’re interested in a particle, like an electron. There is an electron field that tells you, at each point, your chance of detecting one of those particles spinning in a particular way. Suppose you’re trying to measure a force, say electricity or magnetism. There is an electromagnetic field that tells you, at each point, what force you will measure.

Sometimes the question you’re asking has a very simple answer: just a single number, for each point and each time. An example of a question like that is the temperature: pick a city, pick a date, and the temperature there and then is just a number. In particle physics, the Higgs field answers a question like that: at each point, and each time, how “Higgs-y” is it there and then? You might have heard that the Higgs field gives other particles their mass: what this means is that the more “Higgs-y” it is somewhere, the higher these particles’ mass will be. The Higgs field is almost constant, because it’s very difficult to get it to change. That’s in some sense what the Large Hadron Collider did when they discovered the Higgs boson: pushed hard enough to cause a tiny, short-lived ripple in the Higgs field, a small area that was briefly more “Higgs-y” than average.

We like to think of some fields as fundamental, and others as composite. A proton is composite: it’s made up of quarks and gluons. Quarks and gluons, as far as we know, are fundamental: they’re not made up of anything else. More generally, since we’re thinking about fields as answers to questions, we can just as well ask more complicated, “composite” questions. For example, instead of “what is the temperature?”, we can ask “what is the temperature squared?” or “what is the temperature times the Higgs-y-ness?”.

But this raises a troubling point. When we single out a specific field, like the Higgs field, why are we sure that that field is the fundamental one? Why didn’t we start with “Higgs squared” instead? Or “Higgs plus Higgs squared”? Or something even weirder?

That kind of swap, from Higgs to Higgs squared, is called a field redefinition. In the math of quantum field theory, it’s something you’re perfectly allowed to do. Sometimes, it’s even a good idea. Other times, it can make your life quite complicated.

The reason why is that some fields are much simpler than others. Some are what we call free fields. Free fields don’t interact with anything else. They just move, rippling along in easy-to-calculate waves.

Redefine a free field, swapping it for some more complicated function, and you can easily screw up, and make it into an interacting field. An interacting field might interact with another field, like how electromagnetic fields move (and are moved by) electrons. It might also just interact with itself, a kind of feedback effect that makes any calculation we’d like to do much more difficult.

If we persevere with this perverse choice, and do the calculation anyway, we find a surprise. The final results we calculate, the real measurements people can do, are the same in both theories. The field redefinition changed how the theory appeared, quite dramatically…but it didn’t change the physics.

You might think the moral of the story is that you must always choose the right fundamental field. You might want to, but you can’t: not every field is secretly free. Some will be interacting fields, whatever you do. In that case, you can make one choice or another to simplify your life…but you can also just refuse to make a choice.

That’s something quite a few physicists do. Instead of looking at a theory and calling some fields fundamental and others composite, they treat every one of these fields, every different question they could ask, on the same footing. They then ask, for these fields, what one can measure about them. They can ask which fields travel at the speed of light, and which ones go slower, or which fields interact with which other fields, and how much. Field redefinitions will shuffle the fields around, but the patterns in the measurements will remain. So those, and not the fields, can be used to specify the theory. Instead of describing the world in terms of a few fundamental fields, they think about the world as a kind of field soup, characterized by how it shifts when you stir it with a spoon.

It’s not a perspective everyone takes. If you overhear physicists, sometimes they will talk about a theory with only a few fields, sometimes they will talk about many, and you might be hard-pressed to tell what they’re talking about. But if you keep in mind these two perspectives: either a few fundamental fields, or a “field soup”, you’ll understand them a little better.

# Black Holes, Neutron Stars, and the Power of Love

What’s the difference between a black hole and a neutron star?

When a massive star nears the end of its life, it starts running out of nuclear fuel. Without the support of a continuous explosion, the star begins to collapse, crushed under its own weight.

What happens then depends on how much weight that is. The most massive stars collapse completely, into the densest form anything can take: a black hole. Einstein’s equations say a black hole is a single point, infinitely dense: get close enough and nothing, not even light, can escape. A quantum theory of gravity would change this, but not a lot: a quantum black hole would still be as dense as quantum matter can get, still equipped with a similar “point of no return”.

A slightly less massive star collapses, not to a black hole, but to a neutron star. Matter in a neutron star doesn’t collapse to a single point, but it does change dramatically. Each electron in the old star is crushed together with a proton until it becomes a neutron, a forced reversal of the more familiar process of Beta decay. Instead of a ball of hydrogen and helium, the star then ends up like a single atomic nucleus, one roughly the size of a city.

Now, let me ask a slightly different question: how do you tell the difference between a black hole and a neutron star?

Sometimes, you can tell this through ordinary astronomy. Neutron stars do emit light, unlike black holes, though for most neutron stars this is hard to detect. In the past, astronomers would use other objects instead, looking at light from matter falling in, orbiting, or passing by a black hole or neutron star to estimate its mass and size.

Now they have another tool: gravitational wave telescopes. Maybe you’ve heard of LIGO, or its European cousin Virgo: massive machines that do astronomy not with light but by detecting ripples in space and time. In the future, these will be joined by an even bigger setup in space, called LISA. When two black holes or neutron stars collide they “ring” the fabric of space and time like a bell, sending out waves in every direction. By analyzing the frequency of these waves, scientists can learn something about what made them: in particular, whether the waves were made by black holes or neutron stars.

One big difference between black holes and neutron stars lies in something called their “Love numbers“. From far enough away, you can pretend both black holes and neutron stars are single points, like fundamental particles. Try to get more precise, and this picture starts to fail, but if you’re smart you can include small corrections and keep things working. Some of those corrections, called Love numbers, measure how much one object gets squeezed and stretched by the other’s gravitational field. They’re called Love numbers not because they measure how hug-able a neutron star is, but after the mathematician who first proposed them, A. E. H. Love.

What can we learn from Love numbers? Quite a lot. More impressively, there are several different types of questions Love numbers can answer. There are questions about our theories, questions about the natural world, and questions about fundamental physics.

You might have heard that black holes “have no hair”. A black hole in space can be described by just two numbers: its mass, and how much it spins. A star is much more complicated, with sunspots and solar flares and layers of different gases in different amounts. For a black hole, all of that is compressed down to nothing, reduced to just those two numbers and nothing else.

With that in mind, you might think a black hole should have zero Love numbers: it should be impossible to squeeze it or stretch it. This is fundamentally a question about a theory, Einstein’s theory of relativity. If we took that theory for granted, and didn’t add anything to it, what would the consequences be? Would black holes have zero Love number, or not?

It turns out black holes do have zero Love number, if they aren’t spinning. If they are, things are more complicated: a few calculations made it look like spinning black holes also had zero Love number, but just last year a more detailed proof showed that this doesn’t hold. Somehow, despite having “no hair”, you can actually “squeeze” a spinning black hole.

(EDIT: Folks on twitter pointed out a wrinkle here: more recent papers are arguing that spinning black holes actually do have zero Love number as well, and that the earlier papers confused Love numbers with a different effect. All that is to say this is still very much an active area of research!)

The physics behind neutron stars is in principle known, but in practice hard to understand. When they are formed, almost every type of physics gets involved: gas and dust, neutrino blasts, nuclear physics, and general relativity holding it all together.

Because of all this complexity, the structure of neutron stars can’t be calculated from “first principles” alone. Finding it out isn’t a question about our theories, but a question about the natural world. We need to go out and measure how neutron stars actually behave.

Love numbers are a promising way to do that. Love numbers tell you how an object gets squeezed and stretched in a gravitational field. Learning the Love numbers of neutron stars will tell us something about their structure: namely, how squeezable and stretchable they are. Already, LIGO and Virgo have given us some information about this, and ruled out a few possibilities. In future, the LISA telescope will show much more.

Returning to black holes, you might wonder what happens if we don’t stick to Einstein’s theory of relativity. Physicists expect that relativity has to be modified to account for quantum effects, to make a true theory of quantum gravity. We don’t quite know how to do that yet, but there are a few proposals on the table.

Asking for the true theory of quantum gravity isn’t just a question about some specific part of the natural world, it’s a question about the fundamental laws of physics. Can Love numbers help us answer it?

Maybe. Some theorists think that quantum gravity will change the Love numbers of black holes. Fewer, but still some, think they will change enough to be detectable, with future gravitational wave telescopes like LISA. I get the impression this is controversial, both because of the different proposals involved and the approximations used to understand them. Still, it’s fun that Love numbers can answer so many different types of questions, and teach us so many different things about physics.

Unrelated: For those curious about what I look/sound like, I recently gave a talk of outreach advice for the Max Planck Institute for Physics, and they posted it online here.

# “Inreach”

This is, first and foremost, an outreach blog. I try to make my writing as accessible as possible, so that anyone from high school students to my grandparents can learn something. My goal is to get the general public to know a bit more about physics, and about the people who do it, both to better understand the world and to view us in a better light.

However, as I am occasionally reminded, my readers aren’t exactly the general public. I’ve done polls, and over 60% of you either have a PhD in physics, or are on your way to one. The rest include people with what one might call an unusually strong interest in physics: engineers with a fondness for the (2,0) theory, or retired lawyers who like to debate dark matter.

With that in mind, am I really doing outreach? Or am I doing some sort of “inreach” instead?

First, it’s important to remember that just because someone is a physicist doesn’t mean they’re an expert in everything. This is especially relevant when I talk about my own sub-field, but it matters for other topics too: experts in one part of physics can still find something to learn, and it’s still worth getting on their good side. Still, if that was my main audience, I’d probably want to strike a different tone, more like the colloquium talks we give for our fellow physicists.

Second, I like to think that outreach “trickles down”. I write for a general audience, and get read by “physics fans”, but they will go on to talk about physics to anyone who will listen: to parents who want to understand what they do, to people they’re trying to impress at parties, to friends they share articles with. If I write good metaphors and clear analogies, they will get passed on to those friends and parents, and the “inreach” will become outreach. I know that’s why I read other physicists’ outreach blogs: I’m looking for new tricks to make ideas clearer.

Third, active readers are not all readers. The people who answer a poll are more likely to be regulars, people who come back to the blog again and again, and those people are pretty obviously interested in physics. (Interested doesn’t mean expert, of course…but in practice, far more non-experts read blogs on, say, military history, than on physics.) But I suspect most of my readers aren’t regulars. My most popular post, “The Way You Think Everything Is Connected Isn’t the Way Everything Is Connected”, gets a trickle of new views every day. WordPress lets me see some of the search terms people use to find it, and there are people who literally google “is everything connected?” These aren’t physics PhDs looking for content, these are members of the general public who hear something strange and confusing and want to check it out. Being that check, the source someone googles to clear things up, that’s an honor. Knowing I’m serving that role, I know I’m not doing “just inreach”: I’m reaching out too.

# Reality as an Algebra of Observables

Listen to a physicist talk about quantum mechanics, and you’ll hear the word “observable”. Observables are, intuitively enough, things that can be observed. They’re properties that, in principle, one could measure in an experiment, like the position of a particle or its momentum. They’re the kinds of things linked by uncertainty principles, where the better you know one, the worse you know the other.

Some physicists get frustrated by this focus on measurements alone. They think we ought to treat quantum mechanics, not like a black box that produces results, but as information about some underlying reality. Instead of just observables, they want us to look for “beables“: not just things that can be observed, but things that something can be. From their perspective, the way other physicists focus on observables feels like giving up, like those physicists are abandoning their sacred duty to understand the world. Others, like the Quantum Bayesians or QBists, disagree, arguing that quantum mechanics really is, and ought to be, a theory of how individuals get evidence about the world.

I’m not really going to weigh in on that debate, I still don’t feel like I know enough to even write a decent summary. But I do think that one of the instincts on the “beables” side is wrong. If we focus on observables in quantum mechanics, I don’t think we’re doing anything all that unusual. Even in other parts of physics, we can think about reality purely in terms of observations. Doing so isn’t a dereliction of duty: often, it’s the most useful way to understand the world.

When we try to comprehend the world, we always start alone. From our time in the womb, we have only our senses and emotions to go on. With a combination of instinct and inference we start assembling a consistent picture of reality. Philosophers called phenomenologists (not to be confused with the physicists called phenomenologists) study this process in detail, trying to characterize how different things present themselves to an individual consciousness.

For my point here, these details don’t matter so much. That’s because in practice, we aren’t alone in understanding the world. Based on what others say about the world, we conclude they perceive much like we do, and we learn by their observations just as we learn by our own. We can make things abstract: instead of the specifics of how individuals perceive, we think about groups of scientists making measurements. At the end of this train lie observables: things that we as a community could in principle learn, and share with each other, ignoring the details of how exactly we measure them.

If each of these observables was unrelated, just scattered points of data, then we couldn’t learn much. Luckily, they are related. In quantum mechanics, some of these relationships are the uncertainty principles I mentioned earlier. Others relate measurements at different places, or at different times. The fancy way to refer to all these relationships is as an algebra: loosely, it’s something you can “do algebra with”, like you did with numbers and variables in high school. When physicists and mathematicians want to do quantum mechanics or quantum field theory seriously, they often talk about an “algebra of observables”, a formal way of thinking about all of these relationships.

Focusing on those two things, observables and how they are related, isn’t just useful in the quantum world. It’s an important way to think in other areas of physics too. If you’ve heard people talk about relativity, the focus on measurement screams out, in thought experiments full of abstract clocks and abstract yardsticks. Without this discipline, you find paradoxes, only to resolve them when you carefully track what each person can observe. More recently, physicists in my field have had success computing the chance particles collide by focusing on the end result, the actual measurements people can make, ignoring what might happen in between to cause that measurement. We can then break measurements down into simpler measurements, or use the structure of simpler measurements to guess more complicated ones. While we typically have done this in quantum theories, that’s not really a limitation: the same techniques make sense for problems in classical physics, like computing the gravitational waves emitted by colliding black holes.

With this in mind, we really can think of reality in those terms: not as a set of beable objects, but as a set of observable facts, linked together in an algebra of observables. Paring things down to what we can know in this way is more honest, and it’s also more powerful and useful. Far from a betrayal of physics, it’s the best advantage we physicists have in our quest to understand the world.

# Poll: How Do You Get Here?

I’ve been digging through the WordPress “stats” page for this blog. One thing WordPress tells me is what links people follow to get here. It tells me how many times people come from Google or Facebook or Twitter, and how many come from seeing a link on another blog. One thing that surprised me is that some of the blogs people come here from haven’t updated in years.

The way I see it there are two possible explanations. It could be that new people keep checking the old blogs, see a link on their blogroll, and come on over here to check it out. But it could also be the same people over and over, who find it more convenient to start on an old blog and click on links from there.

WordPress doesn’t tell me the difference. But I realized, I can just ask. So in this post, I’m asking all my readers to tell me how you get here. I’m not asking how you found this blog to begin with, but rather how, on a typical day, you navigate to the site. Do you subscribe by email? Do you google the blog’s name every time? RSS reader? Let me know below! And if you don’t see an option that fits you, let me know in the comments!

# The Grant-Writing Moment

When a scientist applies for a grant to fund their research, there’s a way it’s supposed to go. The scientist starts out with a clear idea, a detailed plan for an experiment or calculation they’d like to do, and an expectation of what they could learn from it. Then they get the grant, do their experiment or calculation, and make their discovery. The world smiles upon them.

There’s also a famous way it actually goes. Like the other way, the scientist has a clear idea and detailed plan. Then they do their experiment, or calculation, and see what they get, making their discovery. Finally, they write their grant application, proposing to do the experiment they already did. Getting the grant, they then spend the money on their next idea instead, which they will propose only in the next grant application, and so on.

This is pretty shady behavior. But there’s yet another way things can go, one that flips the previous method on its head. And after considering it, you might find the shady method more understandable.

What happens if a scientist is going to run out of funding, but doesn’t yet have a clear idea? Maybe they don’t know enough yet to have a detailed plan for their experiment or their calculation. Maybe they have an idea, but they’re still foggy about what they can learn from it.

Well, they’re still running out of funding. They still have to write that grant. So they start writing. Along the way, they’ll manage to find some of that clarity: they’ll have to write a detailed plan, they’ll have to describe some expected discovery. If all goes well, they tell a plausible story, and they get that funding.

When they actually go do that research, though, there’s no guarantee it sticks to the plan. In fact, it’s almost guaranteed not to: neither the scientist nor the grant committee typically knows what experiment or calculation needs to be done: that’s what makes the proposal novel science in the first place. The result is that once again, the grant proposal wasn’t exactly honest: it didn’t really describe what was actually going to be done.

You can think of these different stories as falling on a sliding scale. On the one end, the scientist may just have the first glimmer of an idea, and their funded research won’t look anything like their application. On the other, the scientist has already done the research, and the funded research again looks nothing like the application. In between there’s a sweet spot, the intended system: late enough that the scientist has a good idea of what they need to do, early enough that they haven’t done it yet.

How big that sweet spot is depends on the pace of the field. If you’re a field with big, complicated experiments, like randomized controlled trials, you can mostly make this work. Your work takes a long time to plan, and requires sticking to that plan, so you can, at least sometimes, do grants “the right way”. The smaller your experiments are though, the more the details can change, and the smaller the window gets. For a field like theoretical physics, if you know exactly what calculation to do, or what proof to write, with no worries or uncertainty…well, you’ve basically done the calculation already. The sweet spot for ethical grant-writing shrinks down to almost a single moment.

In practice, some grant committees understand this. There are grants where you are expected to present preliminary evidence from work you’ve already started, and to discuss the risks your vaguer ideas might face. Grants of this kind recognize that science is a process, and that catching people at that perfect moment is next-to-impossible. They try to assess what the scientist is doing as a whole, not just a single idea.

Scientists ought to be honest about what they’re doing. But grant agencies need to be honest too, about how science in a given field actually works. Hopefully, one enables the other, and we reach a more honest world.

# Valentine’s Day Physics Poem 2021

It’s Valentine’s Day this weekend, so time for another physics poem. If you’d like to read the poems from past years, they’re archived with the tag Valentine’s Day Physics Poem, accessible here.

Passion Project

Passion is passion.

If you find yourself writing letter after letter,
be they “love”,
or “Physical Review”

Or if you are the quiet sort
and notice only in your mind
those questions, time after time
whenever silence reigns:
“how do I make things right?”

uncertain,
futures,
each so different
still have one
thing
in common.

If you could share that desert island, that jail cell,
and count yourself free.

You’ve found your star. Now it’s straight on till morning.

# A Tale of Two Donuts

I’ve got a new paper up this week, with Hjalte Frellesvig, Cristian Vergu, and Matthias Volk, about the elliptic integrals that show up in Feynman diagrams.

You can think of elliptic integrals as integrals over a torus, a curve shaped like the outer crust of a donut.

Integrals like these are showing up more and more in our field, the subject of bigger and bigger conferences. By now, we think we have a pretty good idea of how to handle them, but there are still some outstanding mysteries to solve.

One such mystery came up in a paper in 2017, by Luise Adams and Stefan Weinzierl. They were working with one of the favorite examples of this community, the so-called sunrise diagram (sunrise being a good time to eat donuts). And they noticed something surprising: if they looked at the sunrise diagram in different ways, it was described by different donuts.

What do I mean, different donuts?

The integrals we know best in this field aren’t integrals on a torus, but rather integrals on a sphere. In some sense, all spheres are the same: you can make them bigger or smaller, but they don’t have different shapes, they’re all “sphere-shaped”. In contrast, integrals on a torus are trickier, because toruses can have different shapes. Think about different donuts: some might have a thin ring, others a thicker one, even if the overall donut is the same size. You can’t just scale up one donut and get the other.

My colleague, Cristian Vergu, was annoyed by this. He’s the kind of person who trusts mathematics like an old friend, one who would never lead him astray. He thought that there must be one answer, one correct donut, one natural way to represent the sunrise diagram mathematically. I was skeptical, I don’t trust mathematics nearly as much as Cristian does. To sort it out, we brought in Hjalte Frellesvig and Matthias Volk, and started trying to write the sunrise diagram every way we possibly could. (Along the way, we threw in another “donut diagram”, the double-box, just to see what would happen.)

Rather than getting a zoo of different donuts, we got a surprise: we kept seeing the same two. And in the end, we stumbled upon the answer Cristian was hoping for: one of these two is, in a meaningful sense, the “correct donut”.

What was wrong with the other donut? It turns out when the original two donuts were found, one of them involved a move that is a bit risky mathematically, namely, combining square roots.

For readers who don’t know what I mean, or why this is risky, let me give a simple example. Everyone else can skip to after the torus gif.

Suppose I am solving a problem, and I find a product of two square roots:

$\sqrt{x}\sqrt{x}$

I could try combining them under the same square root sign, like so:

$\sqrt{x^2}$

That works, if $x$ is positive. But now suppose $x=-1$. Plug in negative one to the first expression, and you get,

$\sqrt{-1}\sqrt{-1}=i\times i=-1$

while in the second,

$\sqrt{(-1)^2}=\sqrt{1}=1$

In this case, it wasn’t as obvious that combining roots would change the donut. It might have been perfectly safe. It took some work to show that indeed, this was the root of the problem. If the roots are instead combined more carefully, then one of the donuts goes away, leaving only the one, true donut.

I’m interested in seeing where this goes, how many different donuts we have to understand and how they might be related. But I’ve also been writing about donuts for the last hour or so, so I’m getting hungry. See you next week!


text:
# Computing Wassertein Distance

For two probability measures $$\mu$$ and $$\nu$$, the Wassertein Distance is defined as $$W_p (\mu , \nu) = \left[ \inf\limits_{\gamma \in \Gamma} |x-y|^p \, d\gamma (x,y) \right] ^{\frac{1}{p}} \, ,$$ where $$\Gamma$$ is the set of all measures $$\gamma$$ for which $$\mu$$ and $$\nu$$ are marginals.

This is a highly non-constructive definition. So, given two sample sets, say $$x_1 , \ldots , x_n$$ iid from $$\mu$$ and $$y_1 , \ldots , y_n$$ from $$\nu$$, it is not at all obvious how to estimate $$W_p (\mu , \nu)$$, or even how to compute the distance between the empirical distribution.

Question: Given iid samples from $$\mu$$ and $$\nu$$, how does one compute the distance between the empirical distributions?

What is known? In the special case of $$p=1$$, $$W_1 (\mu , \nu) = \int_{-\infty} ^{\infty} |F_{\mu}(y) - F_{\nu}(y)| \, dy$$, where $$F_{\mu}$$ and $$F_{\nu}$$ are the CDFs of the respective measures. The proof can be easily extended to show that $$W_p ^p (\mu , \nu) = \int_{-\infty} ^{\infty} |F_{\mu}(y) - F_{\nu}(y)|^p \, dy$$, but not to an equality.

• en.wikipedia.org/wiki/… Dec 11, 2018 at 20:59
• @AlexR. Thanks, but isn't EMD just $W_1$? Dec 11, 2018 at 22:18
• If I'm not mistaken, it can be $W_p$, as it's a discretization of Wasserstein distance to a histogram. The distance function $d_{ij}$ is arbitrary, and can refer to any norm. Dec 11, 2018 at 23:50
• @AmirSagiv you forgot the 2 constraints that the transport function $\gamma$ should sum to $\mu$ and $\nu$ respectively. The unconstrained formula you currently show is the ill-posed Monge problem, but if the 2 missing constraints are included instead, you would have the more popular Kantorovich formulation Oct 15, 2020 at 11:29

format: plain


text:
# What is the difference between to Eurocode design equations (6.10a and 6.10b)?

In Eurocode, two equations for loads are given for STR limit state:

$$1.15K_{FI}G_{kj,sup}+0.9G_{kj,inf}+1.5K_{FI}Q_{k,1}+1.5K_{FI}\sum_{i>1}\psi_{0,i}Q_{k,i}$$

$$1.35K_{FI}G_{kj,sup}+0.9G_{kj,inf}$$

Designer is required to calculate using both, and the design value of the load comes from the equation that gives the least favourable result. But what is the actual difference of these equations, why do we need two? I can see that the bottom equation (6.10a) only takes into account permanent (dead) loads (letter $$G$$) and the one above considers temporary (live) loads as well (letter $$Q$$).

Why don't we need to consider the live loads in one of the equations? My lecture material says that the lower equation is rarely the deciding one, but it must always be checked. I've read my lecture materials and the Eurocode section on this, but I can't really get any good explanation of this. If somebody could explain the difference between the two equations and why we need them both I would be very grateful!

• which version of EN1990 you got the equations from? Could you explain the kj and sup, inf subscripts in your post? – NMech Oct 1 '20 at 12:03

I am not sure which version of Eurocode you have this (I have access to an older version circa 2002), and 6.10a and b have a slightly different form. In any case I will answer and I will later update my answer.

# Equation A: Dominant secondary actions and combination of transients loads

First of all: equation a is not only one equation. It represents all possible combination of temporary actions on a structure (could be wind, snow, fire, earthquake etc).

Since Qs are temporary loads, it is highly unlikely that all of them will occur together. So, what the Eurocode suggests, is to assume that any point in time only one of the actions will be dominant, while all the other are multiplied by a reduction factor (see $$\psi_{0,i}$$). So if you got 4 temporary actions, you need to perform 4 times that calculation.

The Dead weights remain constant. You need to notice that, for $$G_{kj, sup}$$ the coefficient is slightly less in eq. a (set to 1.15) compared to equation B.

Equation B represents only dead loads, but it has a slightly higher coefficient for $$G_{kj, sup}$$. In this scenario, the dominant load is the dead load, and no temporary loads are considered.
**Update:**I found a reference online regarding the finnish SFS-EN. What happens is that $$G_{sup}$$ is the upper design value, and $$G_{inf}$$ is the lower design value, which can be used if for example you have a building with maximum occupant capacity or completely empty. The two values create a type of average (leaning towards the upper limit, in order to make the calculation more direct.
• Regarding the combination of transient loads: if we have 4 of them, do I need to choose each as the dominant one once, with every combination of minor load? For example if I had wind, snow and load from people, would I choose wind as the dominant one, multiply snow and people load by $\psi_{0,i}$, then choose snow as the dominant one and multiply people load and wind by the reduction factor, and finally choose people load as the dominant and reduce wind and snow? – S. Rotos Oct 1 '20 at 15:23


text:
# nLab Minkowski metric

### Context

#### Riemannian geometry

Riemannian geometry

## Applications

#### Gravity

gravity, supergravity

## Spacetimes

black hole spacetimesvanishing angular momentumpositive angular momentum
vanishing chargeSchwarzschild spacetimeKerr spacetime
positive chargeReissner-Nordstrom spacetimeKerr-Newman spacetime

# Contents

## Idea

The Minkowski metric is a pseudo-Riemannian metric which is completely flat in that its Riemann curvature vanishes.

For $p \in \mathbb{N}$, a Cartesian space $\mathbb{R}^p+1$ equipped with the Minkowski metric $\eta$ is called Minkowski spacetime of dimension $p + 1$, denoted $\mathbb{R}^{p,1} \coloneqq (\mathbb{R}^{p+1}, \eta)$.

## Definition

In terms of the standard coordinates $(x^\mu)_{\mu = 0}^p$ on $\mathbb{R}^{p+1}$ the Minkowski metric is the constant rank 2-tensor which is given by the diagonal matrix $\eta = diag(-1,+1,+1, \cdots , +1)$ (or else $\eta = diag(+1,-1,-1, \cdots, -1)$).

This means that for $v = (v^\mu)_{\mu = 0}^p \in \mathbb{R}^{p,1}$ then

$\eta(v_1, v_2) \;=\; \eta_{\mu \nu} v_1^\mu v_2 \mu \coloneqq - (v^0)^2 + \underoverset{j = 1}{p}{\sum} (v^j)^2 \,.$

## Properties

### In terms of hermitian matrices.

In the dimensions $p+1 \in \{3,4,6,10\}$ the quadratic form corresponding to the Minkowski metric may be identified simply with the determinant function on $2 \times 2$ hermitian matrices with coefficients in one of the four real normed division algebra $\mathbb{K} \in \{\mathbb{R}, \mathbb{C}, \mathbb{H}, \mathbb{O}\}$.

For details see at geometry of physics -- A first idea of quantum field theory the chapter spacetime.

Revised on November 9, 2017 09:44:06 by Urs Schreiber (88.64.51.223)


text:
# Bounded rational decision-making from elementary computations that reduce uncertainty

In its most basic form, decision-making can be viewed as a computational process that progressively eliminates alternatives, thereby reducing uncertainty. Such processes are generally costly, meaning that the amount of uncertainty that can be reduced is limited by the amount of available computational resources. Here, we introduce the notion of elementary computation based on a fundamental principle for probability transfers that reduce uncertainty. Elementary computations can be considered as the inverse of Pigou-Dalton transfers applied to probability distributions, closely related to the concepts of majorization, T-transforms, and generalized entropies that induce a preorder on the space of probability distributions. As a consequence we can define resource cost functions that are order-preserving and therefore monotonic with respect to the uncertainty reduction. This leads to a comprehensive notion of decision-making processes with limited resources. Along the way, we prove several new results on majorization theory, as well as on entropy and divergence measures.

## Authors

• 5 publications
• 20 publications
• ### Decision Making Using Probabilistic Inference Methods

The analysis of decision making under uncertainty is closely related to ...
03/13/2013 ∙ by Ross D. Shachter, et al. ∙ 0

• ### Decision-Making with Belief Functions: a Review

Approaches to decision-making under uncertainty in the belief function f...
08/16/2018 ∙ by Thierry Denoeux, et al. ∙ 0

• ### Maximum Uncertainty Procedures for Interval-Valued Probability Distributions

Measures of uncertainty and divergence are introduced for interval-value...
03/27/2013 ∙ by Michael Pittarelli, et al. ∙ 0

• ### Flexible and Approximate Computation through State-Space Reduction

In the real world, insufficient information, limited computation resourc...
01/30/2013 ∙ by Weixiong Zhang, et al. ∙ 0

• ### Decision-making Under Ordinal Preferences and Comparative Uncertainty

This paper investigates the problem of finding a preference relation on ...
02/06/2013 ∙ by Didier Dubois, et al. ∙ 0

• ### Rational Value of Information Estimation for Measurement Selection

Computing value of information (VOI) is a crucial task in various aspect...
03/27/2010 ∙ by David Tolpin, et al. ∙ 0

• ### Learning Structural Weight Uncertainty for Sequential Decision-Making

Learning probability distributions on the weights of neural networks (NN...
12/30/2017 ∙ by Ruiyi Zhang, et al. ∙ 1

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1. Introduction

In rational decision theory, uncertainty may have multiple sources that ultimately share the commonality that they reflect a lack of knowledge on the part of the decision-maker about the environment. A paramount example is the perfectly rational decision-maker [99] that has a probabilistic model of the environment and chooses its actions so as to maximize the expected utility entailed by the different choices. When we consider bounded rational decision-makers [87]

, we may add another source of uncertainty arising from the decision-maker’s limited processing capabilities, since the decision-maker will not only accept a single best choice, but will accept any satisficing option. Today, bounded rationality is an active research topic that crosses multiple scientific fields such as economics, political science, decision theory, game theory, computer science, and neuroscience

[81, 66, 59, 12, 31, 63, 45, 89, 101, 42, 91, 92, 90, 46, 16, 70, 58, 1, 30], where uncertainty is one of the most important common denominators.

Uncertainty is often equated with Shannon entropy in information theory [85], measuring the average number of yes/no-questions that have to be answered to resolve the uncertainty. Even though Shannon entropy has many desirable properties, there are plenty of alternative suggestions for entropy measures in the literature, known as generalized entropies, such as Rényi entropy [77] or Tsallis entropy [95]

. Closely related to entropies are divergence measures, which express how probability distributions differ from a given reference distribution. If the reference distribution is uniform then divergence measures can be expressed in terms of entropy measures, which is why divergences can be viewed as generalizations of entropy, for example the Kullback-Leibler divergence

[52] generalizing Shannon entropy.

Here, we introduce the concept of elementary computation based on a slightly stronger notion of uncertainty than is expressed by Shannon entropy, or any other generalized entropy alone, but is equivalent to all of them combined. Equating decision-making with uncertainty reduction, this leads to a new comprehensive view of decision-making with limited resources. Our main contributions can be summarized as follows:

1. Based on a fundamental concept of probability transfers related to the Pigou-Dalton principle of welfare economics [23], we promote a generalized notion of uncertainty reduction of a probability distribution that we call elementary computation. This leads to a natural definition of cost functions that quantify the resource costs for uncertainty reduction necessary for decision-making. We generalize these concepts to arbitrary reference distributions. In particular, we define Pigou-Dalton-type transfers for probability distributions relative to a reference or prior distribution, which induce a preorder that is slightly stronger than Kullback-Leibler divergence, but is equivalent to the notion of divergence given by all -divergences combined. We prove several new characterizations of the underlying concept, known as relative majorization.

2. An interesting property of cost functions is their behavior under coarse-graining, which plays an important role in decision-making and formalizes the general notion of making abstractions. More precisely, if a decision in a set is split up into two steps by partitioning and first deciding in the set of (coarse-grained) partitions and secondly choosing a fine-grained option inside the selected partition , then it is an important question how the cost for the total decision-making process differs from the sum of the costs in each step. We show that -divergences are superadditive with respect to coarse-graining, which means that decision-making costs can potentially be reduced by splitting up the decision into multiple steps. In this regard, we find evidence that the well-known property of Kullback-Leibler divergence of being additive under coarse-graining might be viewed as describing the minimal amount of processing cost that cannot be reduced by a more intelligent decision-making strategy.

3. We define bounded rational decision-makers as decision-making processes that are optimizing a given utility function under a constraint on the cost function, or minimizing the cost function under a minimal requirement on expected utility. As a special case for Shannon-type information costs, we arrive at information-theoretic bounded rationality, which may form a normative baseline for bounded-optimal decision-making in the absence of process-dependent constraints. We show that bounded-optimal posteriors with informational costs trace a path through probability space that can itself be seen as an anytime decision-making process, where each step optimally trades off utility and processing costs.

4. We show that Bayesian inference can be seen as a decision-making process with limited resources given by the number of available datapoints.

Section 2 deals with and , aiming at a general characterization of decision-making in terms of uncertainty reduction. Item is covered in Section 3, deriving information-theoretic bounded rationality as a special case. Section 4 illustrates the concepts with an example including item . Sections 5 and 6 contain a general discussion and concluding remarks.

## Notation

Let denote the real numbers, the set of non-negative real numbers, and the rational numbers. We write for the number of elements contained in a countable set , and for the set difference, that is the set of elements in that are not in . denotes the set of probability distributions on a set , in particular, any is normalized so that

. Random variables are denoted by capital letters

, while their explicit values are denoted by small letters . For the probability distribution of a random variable we write , and for the values of . Correspondingly, the expectation is also written as , , or . We also write , to denote the approximation of by an average over samples from .

## 2. Decision-making with limited resources

In this section, we develop the notion of a decision-making process with limited resources following the simple assumption that any decision-making process

• reduces uncertainty

• by spending resources.

Starting from an intuitive interpretation of uncertainty and resource costs, these concepts are refined incrementally until a precise definition of a decision-making process is given at the end of this section (Definition 2.11) in terms of elementary computations. Here, a decision-making process is a comprehensive term that describes all kinds of biological as well as artificial systems that are searching for solutions to given problems, for example a human decision-maker that burns calories while thinking, or a computer that uses electric energy to run an algorithm. However, resources

do not necessarily refer to a real consumable quantity but can also represent more explicit resources (like time) as a proxy, for example the number of binary comparisons in a search algorithm, the number of forward simulations in a reinforcement learning algorithm, the number of samples in a Monte Carlo algorithm, or, even more abstractly, they can express the limited availability of some source of information, like for example the number of datapoints that are available to an inference algorithm (see Section

4).

### 2.1. Uncertainty reduction by eliminating options

In its most basic form, the concept of decision-making can be formalized as the process of looking for a decision in a discrete set of options . We say that a decision is certain, if repeated queries of the decision-maker will result in the same decision, and it is uncertain, if repeated queries can result in different decisions. Uncertainty reduction then corresponds to reducing the amount of uncertain options. Hence, a decision-making process that transitions from a space of options to a strictly smaller subset reduces the amount of uncertain options from to , with the possible goal to eventually find a single certain decision . Such a process is generally costly, the more uncertainty is reduced the more resources it costs (Figure 1). The explicit mapping between uncertainty reduction and resource cost depends on the details of the underlying process and on which explicit quantity is taken as the resource. For example, if the resource is given by time (or any monotone function of time), then a search algorithm that eliminates options sequentially until the target value is found (linear search) is less cost efficient than an algorithm that takes a sorted list and in each step removes half of the options by comparing the mid point to the target (logarithmic search). Abstractly, any real-valued function on the power set of that satisfies whenever might be used as a cost function in the sense that quantifies the expenses of reducing the uncertainty from to .

In utility theory decision-making is modelled as an optimization process that maximizes a so-called utility function (which can itself be an expected utility with respect to a probabilistic model of the environment, in the sense of von Neumann and Morgenstern [99]). A decision-maker that is optimizing a given utility function obtains a utility of on average after reducing the amount of uncertain options from to (see Figure 2). A decision-maker that completely reduces uncertainty by finding the optimum is called rational (w.l.o.g. we can assume that is unique, by redefining in the case when it is not). Since uncertainty reduction generally comes with a cost, a utility optimizing decision-maker with limited resources, correspondingly called bounded rational (see Section 3), in contrast will obtain only uncertain decisions from a subset . Such decision-makers seek satisfactory rather than optimal solutions, for example by taking the first option that satisfies a minimal utility requirement, which Herbert Simon calls a satisficing solution [87].

Summarizing, we conclude that a decision-making process with decision space that successively eliminates options can be represented by a mapping between subsets of , together with a cost function that quantifies the total expenses of arriving at a given subset,

 Ω⟶⋯⟶A′⟶ϕ(A′)⟶⋯⟶A (2.1)

such that

 Ω⊃A′⊃ϕ(A′)⊃A,0=C(Ω)

For example, a rational decision-maker can afford , whereas a decision-maker with limited resources can typically only afford uncertainty reduction with cost .

From a probabilistic perspective, a decision-making process as described above is a transition from a uniform probability distribution over options to a uniform probability distribution over options, that converges to the Dirac measure centered at

in the fully rational limit. From this point of view, the restriction to uniform distributions is artificial. A decision-maker that is uncertain about the optimal decision

might indeed have a bias towards a subset without completely excluding other options (the ones in ), so that the behavior must be properly described by a probability distribution . Therefore, in the following section, we extend (2.1) and (2.2) to transitions between probability distributions. In particular, we must replace the power set of by the space of probability distributions on , denoted by .

### 2.2. Probabilistic decision-making

Let be a discrete decision space of options, so that consists of discrete distributions

, often represented by probability vectors

. However, many of the concepts presented in this and the following section can be generalized to the continuous case [62, 44].

Intuitively, the uncertainty contained in a distribution is related to the relative inequality of its entries, the more similar its entries are, the higher the uncertainty. This means that uncertainty is increased by moving some probability weight from a more likely option to a less likely option. It turns out that this simple idea leads to a concept widely known as majorization [36, 10, 72, 13, 62, 11], which has roots in the economic literature of the early 19th century [60, 74, 23], where it was introduced to describe income inequality, later known as the Pigou-Dalton Principle of Transfers. Here, the operation of moving weight from a more likely to a less likely option corresponds to the transfer of income from one individual of a population to a relatively poorer individual (also known as a Robin Hood operation [10]). Since a decision-making process can be viewed as a sequence of uncertainty reducing computations, we call the inverse of such a Pigou-Dalton transfer an elementary computation.

###### Definition 2.1 (Elementary computation).

A transformation on of the form

 Tε:p↦(p1,…,pm+ε,…,pn−ε,…,pN), (2.3)

where are such that , and , is called a Pigou-Dalton transfer (see Figure 3). We call its inverse an elementary computation.

Since making two probability values more similar or more dissimilar are the only two possibilities to minimally transform a probability distribution, elementary computations are the most basic principle of how uncertainty is reduced. Hence, we conclude that a distribution has more uncertainty than a distribution if and only if can be obtained from by finitely many elementary computations (and permutations, which are not considered an elementary computation due to the choice of ).

###### Definition 2.2 (Uncertainty).

We say that contains more uncertainty than , denoted by

 p′≺p, (2.4)

if and only if can be obtained from by a finite number of elementary computations and permutations.

Note that, mathematically this defines a preorder on , i.e. a reflexive ( for all ) and transitive (if , then for all ) binary relation.

In the literature, there are different names for the relation between and expressed by Definition 2.2, for example is called more mixed than [79], more disordered than [78], more chaotic than [13], or an average of [36]. Most commonly however, is said to majorize , which started with the early influences of Muirhead [65], and Hardy, Littlewood, and Pólya [36] and was developed by many authors into the field of majorization theory (a standard reference is by Marshall, Olkin, and Arnold [62]), with far reaching applications until today, especially in nonequilibrium thermodynamics and quantum information theory [15, 41, 34].

There are plenty of equivalent (arguably less intuitive) characterizations of , some of which we are summarizing below. However, one characterization makes use of a concept very closely related to Pigou-Dalton transfers, known as T-transforms [13, 62], which expresses the fact that moving some weight from a more likely option to a less likely option is equivalent to taking (weighted) averages of the two probability values. More precisely, a T-transform is a linear operator on with a matrix of the form , where

denotes the identity matrix on

, denotes a permutation matrix of two elements, and . If permutes and , then for all , and

 (Tp)m=(1−λ)pm+λpn,(Tp)n=λpm+(1−λ)pn. (2.5)

Hence, a T-transform considers any two probability values and of a given , calculates their weighted averages with weights and , and replaces the original values with these averages. From (2.5) it follows immediately that a T-transform with parameter and a permutation of with is a Pigou-Dalton transfer with . Also allowing means that T-transfers include permutations, in particular, if and only if can be derived from by successive applications of finitely many T-transforms

Due to a classic result by Hardy, Littlewood and Pólya [36, p.49], this characterization can be stated in an even simpler form by using doubly stochastic matrices, i.e. matrices with and for all . By writing for all , and , these conditions are often stated as

 Aij≥0,Ae=e,eA=e. (2.6)

Note that doubly stochastic matrices can be viewed as generalizations of T-transforms in the sense that a T-transform takes an average of two entries, whereas if

with a doubly stochastic matrix

, then is a convex combination, or a weighted average, of with coefficients for each . This is also, why is then called more mixed than [79]. Therefore, similar to T-transforms, we might expect that if is the result of an application of a doubly stochastic matrix, , then is an average of and therefore contains more uncertainty than . This is exactly what is expressed by characterization in the following theorem. A similar characterization of is that must be given by a convex combination of permutations of the elements of (see property below).

Without having the concept of majorization, Schur proved that functions of the form with a convex function are monotone with respect to the application of a doubly stochastic matrix [83] (see property below). Functions of this form are an important class of cost functions for probabilistic decision-makers, as we will discuss in Example 2.2.

###### Theorem 2.3 (Characterizations of p′≺p[62]).

For , the following are equivalent:

1. , i.e. contains more uncertainty than (Definition 2.2)

2. is the result of finitely many T-transforms applied to

3. for a doubly stochastic matrix

4. where , , , and is a permutation for all

5. for all continuous convex functions

6. for all , where denotes the decreasing rearrangement of .

As argued above, the equivalence between and is straight-forward. The equivalences between , , and are due to Muirhead [65] and Hardy, Littlewood, and Pólya [36]. The implication is due to Karamata [47] and Hardy, Littlewood, and Pólya [37], whereas goes back to Schur [83]. Mathematically, means that belongs to the convex hull of all permutations of the entries of , and the equivalence is known as the Birkhoff-von Neumann theorem. Here, we have stated all relations for probability vectors , even though they are usually stated for all with the additional requirement that .

Condition is the classical and most commonly used definition of majorization [60, 36, 62], since it is often the easiest to check in practical examples. For example, from it immediately follows that uniform distributions over options contain more uncertainty than uniform distributions over options, since we have for all , i.e. for it follows that

 (1N,…,1N)≺(1N−1,…,1N−1,0)≺(12,12,0,…,0)≺(1,0…,0). (2.7)

In particular, if , then the uniform distribution over contains less uncertainty than the uniform distribution over , which shows that the notion of uncertainty introduced in Definition 2.2 is indeed a generalizatin of the notion of uncertainty given by the number of uncertain options introduced in the previous section.

Note that, only being a preorder on , in general, two distributions are not necessarily comparable, i.e. we can have both and . In Figure 4, we visualize the regions of all comparable distributions for two exemplary distributions on a three-dimensional decision space (), represented on the two-dimensional simplex of probability vectors . For example,

can not be compared under , since , but .

Cost functions can now be generalized to probabilistic decision-making by noting that the property whenever in (2.2) means that is strictly monotonic with respect to the preorder given by set inclusion.

###### Definition 2.4 (Cost functions on PΩ).

We say that a function is a cost function, if it is strictly monotonically increasing with respect to the preorder , i.e. if

 p′≺p⇒C(p′)≤C(p), (2.8)

with equality only if and are equivalent, , which is defined as and . Moreover, for a parametrized family of posteriors , we say that is a resource parameter with respect to a cost function , if the mapping is strictly monotonically increasing.

Since monotonic functions with respect to majorization were first studied by Schur [83], functions with this property are usually called (strictly) Schur-convex [62, Ch. 3].

###### Example (Generalized entropies).

From in Theorem 2.3 it follows that functions of the form

 C(p)=N∑i=1f(pi), (2.9)

where is strictly convex, are examples of cost functions. Since many entropy measures used in the literature can be seen to be special cases of (2.9) (with a concave ), functions of this form are often called generalized entropies [18]. In particular, for the choice , we have , where denotes the Shannon entropy of . Thus, if contains more uncertainty than in the sense of Definition 2.2 () then the Shannon entropy of is larger than the Shannon entropy of and therefore contains also more uncertainty in the sense of classical information theory than . Similarly, for we obtain the (negative) Burg entropy, and for functions of the form for we get the (negative) Tsallis entropy, where the sign is chosen depending on such that is convex (see e.g. [32] for more examples). Moreover, the composition of any (strictly) monotonically increasing function with (2.9) generates another class of cost functions, which contains for example the (negative) Rényi entropy [77]. Note also that entropies of the form (2.9) are special cases of Csiszár’s f-divergences [20] for uniform reference distributions (see Example 2.3 below). In Figure 5, several examples of cost functions are shown for . In this case, the 2-dimensional probability simplex is given by the triangle in with edges , , and . Cost functions are visualized in terms of their level sets.

We prove in Proposition A.1 in the appendix that all cost functions of the form (2.9) are superadditive with respect to coarse-graining. This seems to be a new result and an improvement upon the fact that generalized entropies (and -divergences) satisfy information monotonicity [5]. More precisely, if a decision in , represented by a random variable , is split up into two steps by partitioning and first deciding about the partition , correspondingly described by a random variable with values in , and then choosing an option inside of the selected partition , represented by a random variable , i.e. , then

 C(Z)≥C(X)+C(Y|X), (2.10)

where and . For symmetric cost functions (such as (2.9)) this is equivalent to

 C(p1,…,pN)≥C(p1+p2,p3,…,pN)+(p1+p2)C(p1p1+p2,p2p1+p2). (2.11)

The case of equality in (2.10) and (2.11) (see Figure 6) is sometimes called separability [51], strong additivity [21], or recursivity [4], and it is often used to characterize Shannon entropy [26, 96, 48, 55, 77, 2]. In fact, we also show in the appendix (Proposition A.2) that cost functions that are additive under coarse-graining are proportional to the negative Shannon entropy . See also Example 2.3 in the next section, where we discuss the generalization to arbitrary reference distributions.

We can now refine the notion of a decision-making process introduced in the previous section as a mapping together with a cost function satisfying (2.2). Instead of simply mapping from sets to smaller subsets by successively eliminating options, we now allow to be a mapping between probability distributions such that can be obtained from by a finite number of elementary computations (without permutations), and we require to be a cost function on , so that

 p⋨ϕ(p),C(p)

Here, quantifies the total costs of arriving at a distribution , and means that and . In other words, a decision-making process can be viewed as traversing probability space by moving pieces of probability from one option to another option such that uncertainty is reduced.

Up to now we have ignored one important property of a decision-making process, the distribution with minimal cost, i.e. satisfying for all , which must be identified with the initial distribution of a decision-making process with cost function . As one might expect (see Figure 5), it turns out that all cost functions according to Definition 2.4 have the same minimal element.

###### Proposition 2.5 (Uniform distributions are minimal).

The uniform distribution is the unique minimal element in with respect to , i.e.

 (1N,…,1N)≺p∀p∈PΩ. (2.13)

Once (2.13) is established, it follows from (2.8) that for all , in particular the uniform distribution corresponds to the initial state of all decision-making processes with cost function satisfying (2.12). In particular, it contains the maximum amount of uncertainty with respect to any entropy measure of the form (2.9), known as the second Khinchin axiom [51], e.g. for Shannon entropy . Proposition 2.5 follows from characterization in Theorem 2.3 after noticing that every can be transformed to a uniform distribution by permuting its elements cyclically (see Proposition A.3 in the appendix for a detailed proof).

Regarding the possibility that a decision-maker may have prior information, for example originating from the experience of previous comparable decision-making tasks, the assumption of a uniform initial distribution seems to be artificial. Therefore, in the following section we arrive at the final notion of a decision-making process by extending the results of this section to allow for arbitrary initial distributions.

### 2.3. Decision-making with prior knowledge

From the discussion at the end of the previous section we conclude that, in full generality, a decision-maker transitions from an initial probability distribution , called prior, to a terminal distribution , called posterior. Note that, since once eliminated options are excluded from the rest of the decision-making process, a posterior must be absolutely continuous with respect to the prior , denoted by , i.e. can be non-zero for a given only if is non-zero.

The notion of uncertainty (Definition 2.2) can be generalized with respect to a non-uniform prior by viewing the probabilities as the probabilities of partitions of an underlying elementary probability space of equally likely elements under , in particular represents as the uniform distribution on (see Figure 7). The similarity of the entries of the corresponding representation of any (its uncertainty) then contains information about how close is to , which we call the relative uncertainty of with respect to (Definition 2.6 below).

The formal construction is as follows: Let be such that and . The case when then follows from a simple approximation of each entry by a rational number. Let be such that for all , for example could be chosen as the least common multiple of the denominators of the . The underlying elementary probability space then consists of elements and there exists a partitioning of such that

 |Ai|=αqi∀i∈{1,…,N}, (2.14)

where denotes the uniform distribution on . In particular, it follows that

 Q(Ai)=|Ai|∑j=11α=qi∀i∈{1,…,N}, (2.15)

i.e.  represents in with respect to the partitioning . Similarly, any can be represented as a distribution on by requiring that for all and letting to be constant inside of each partition, i.e. similar to (2.15) we have for all and therefore by (2.14)

 P(ω) = 1αpiqi∀ω∈Ai . (2.16)

Note that, if then by absolute continuity () in which case we can either exclude option from or set .

###### Example.

For a prior we put , so that should be partitioned as . Then corresponds to the probability of the -th partition under the uniform distribution , while is represented on by (see Figure 7).

Importantly, if the components of the representation in given by (2.16) are similar to each other, i.e. if is close to uniform, then the components of must be very similar to the components of , which we express by the concept of relative uncertainty.

###### Definition 2.6 (Uncertainty relative to q).

We say that contains more uncertainty with respect to a prior than , denoted by , if and only if contains more uncertainty than , i.e.

 p′≺qp:⇔Λqp′≺Λqp (2.17)

where is given by (2.16).

As we will show in Theorem 2.7 below, it turns out that coincides with a known concept called -majorization [97], majorization relative to [44, 62], or mixing distance [80]. Due to the lack of a characterization by partial sums, it is usually defined as a generalization of characterization in Theorem 2.3, that is is -majorized by iff , where is a so-called -stochastic matrix, which means that it is a stochastic matrix () with . In particular, does not depend on the choice of in the definition of . Here, we provide two new characterizations of -majorization, the one given by Definition 2.6, and one using partial sums generalizing the original definition of majorization.

###### Theorem 2.7 (Characterizations of p′≺qp).

The following are equivalent

1. , i.e. contains more uncertainty relative to than (Def. 2.6)

2. can be obtained from by a finite number of elementary computations and permutations on

3. for a -stochastic matrix , i.e.  and

4. for all continuous convex functions

5. for all that satisfy and , where the arrows indicate that is ordered decreasingly, and .

To prove that , , and are equivalent (see Proposition A.4 in the appendix), we use of the fact that has a left inverse . This can be verified by simply multiplying the corresponding matrices given in the proof of Proposition A.4. The equivalence betweeen and is shown in [44] (see also [80, 62]). Characterization follows immediately from Definition 2.2 and Definition 2.6.

As required from the discussion at the end of the previous section, is indeed minimal with respect to , which means that it contains the most amount of uncertainty with respect to itself.

###### Proposition 2.8 (The prior is minimal).

The prior is the unique minimal element in with respect to , that is

 q≺qp∀p∈PΩ. (2.18)

This follows more or less directly from Proposition 2.5 and the equivalence of and in Theorem 2.7 (see Proposition A.5 in the appendix for a detailed proof).

Order-preserving functions with respect to generalize cost functions introduced in the previous section (Definition 2.4). According to Proposition 2.8, such functions have a unique minimum given by the prior . Since cost functions are used in Definition 2.11 below to quantify the expenses of a decision-making process, we require their minimum to be zero, which can always be achieved by redefining a given cost function by an additive constant.

###### Definition 2.9 (Cost functions relative to q).

We say that a function is a cost function relative to , if , if it is invariant under relabeling , and if it is strictly monotonically increasing with respect to the preorder , that is if

 p′≺qp⇒Cq(p′)≤Cq(p), (2.19)

with equality only if , i.e. if and . Moreover, for a parametrized family of posteriors , we say that is a resource parameter with respect to a cost function , if the mapping is strictly monotonically increasing.

Similar to generalized entropy functions discussed in Example 2.2, in the literature there are many examples of relative cost functions, usually called divergences or measures of divergence.

###### Example (f-divergences).

From in Theorem 2.7 it follows that functions of the form

 Cq(p)\coloneqqN∑i=1qif(piqi), (2.20)

where is continuous and strictly convex with , are examples of cost functions relative to . Many well-known divergence measures can be seen to belong to this class of relative cost functions, also known as Csiszár’s -divergences [20]: the Kullback-Leibler divergence (or relative entropy), the squared distance, the Hartley entropy, the Burg entropy, the Tsallis entropy, and many more [32, 21] (see Figure 8 for visualizations of some of them in relative to a non-uniform prior).

As a generalizition of Proposition A.1 (superadditivity of generalized entropies), we prove in Proposition A.6 in the appendix that -divergences are superadditive under coarse-graining, that is, for

 Cq(Z)≥Cq(X)+Cq(Y|X) (2.21)

whenever and . This generalizes (2.10) to the case of a non-uniform prior. Similar to entropies, the case of equality in (2.21) is sometimes called composition rule [40], chain rule [57], or recursivity [21], and is often used to characterize Kullback-Leibler divergence [40, 63, 21, 57].

Indeed, we also show in the appendix (Proposition A.7) that all additive cost functions with respect to are proportional to Kullback-Leibler divergence (relative entropy). This goes back to Hobson’s modification [40] of Shannon’s original proof [85], after establishing the following monotonicity property for uniform distributions: If denotes the cost of a uniform distribution over elements relative to a uniform distribution over elements, then (see Figure 9)

 f(M′,N)≤f(M,N) ∀M≤M′≤N,f(M,N)≥f(M,N′) ∀M≤N′≤N. (2.22)

Note that, even though our proof of Proposition A.7 uses additivity under coarse graining to show the monotonicity property (2.22), it is easy to see that any relative cost function of the form (2.20) also satisfies (2.22) by using the convexity of in the form with .

In terms of decision-making, superadditivity under coarse-graining means that decision-making costs can potentially be reduced by splitting up the decision into multiple steps, for example by a more intelligent search strategy. For example, if for some and is superadditive, then the cost for reducing uncertainty to a single option, i.e. , when starting from a uniform distribution , satisfies

 Cq(p) ≥Cq2(1,0)+CqN/2(1,0,…,0) ≥…≥ logN=DKL(p∥q),

where , and we have set as unit cost (corresponding to 1 bit in the case of Kullback-Leibler divergence). Thus, intuitively the property of the Kullback-Leibler divergence of being additive under coarse-graining might be viewed as describing the minimal amount of processing costs that must be contained in any cost function, because it cannot be reduced by changing the decision-making process. Therefore, in the following we call cost functions that are proportional to the Kullback-Leibler divergence simply informational costs.

In contrast to the previous section, in the definition of and its characterizations we have never used elementary computations on directly. This is due to the fact that permutations do interact with the uncertainty relative to , and therefore cannot be characterized by a finite number of elementary computations and permutations on . However, we can still define elementary computations relative to by the inverse of Pigou-Dalton transfers of the form (2.3) such that for , which is arguably the most basic form of how to generate uncertainty with respect to .

Even for small , a regular Pigou-Dalton transfer does not necessarily increase uncertainty relative to , because the similarity of the components now needs to be considered with respect to . Instead, we compare the components of the representation of , and move some probability weight from to whenever for and , by distributing evenly among the elements in (see Figure 10), denoted by the transformation . Here, must be small enough such that the inequality is invariant under , which means that

 (~TεP)(ω)≤(~TεP)(ω′)⇔1αpmqm+ε|Am| ≤ 1αpnqn−ε|An|

and therefore

 ε ≤ pnqn−pmqm1qm+1qn. (2.23)

By construction, minimally increases uncertainty in while staying in the image of under , by keeping the values of constant in each partition, and therefore can be considered as the most basic way of how to increase uncertainty relative to .

###### Definition 2.10 (Elementary computation relative to q).

We call a transformation on of the form

 Tε:p↦(p1,…,pm+ε,…,pn−ε,…,pN), (2.24)

with such that , and satisfying (2.23), a Pigou-Dalton transfer relative to , and its inverse an elementary computation relative to .

We are now in the position to state our final definition of a decision-making process.

###### Definition 2.11 (Decision-making process).

A decision-making process is a gradual transformation

 q⟶⋯⟶p′⟶ϕ(p′)⟶⋯⟶p

of a prior to a posterior , such that each step decreases uncertainty relative to . This means that is obtained from by successive application of a mapping between probability distributions on , such that can be obtained from by finitely many elementary computations relative to , in particular

 q⋨qp′⋨qϕ(p′),0=Cq(q)

where quantifies the total costs of a distribution , and means that and .

In other words, a decision-making process can be viewed as traversing probability space from prior to posterior by moving pieces of probability from one option to another option such that uncertainty is reduced relative to , while expending a certain amount of resources determined by the cost function .

## 3. Bounded rationality

### 3.1. Bounded rational decision-making

In this section, we consider decision-making processes that trade off utility against costs. Such decision-makers either maximize a utility function subject to a constraint on the cost function, for example an author of a scientific article that optimizes the article’s quality until a deadline is reached, or minimizing the cost function subject to a utility constraint, for example a high-school student that minimizes effort such that the requirement to pass a certain class is achieved. In both cases, the decision-makers are called bounded rational, since in the limit of no resource constraints they coincide with rational decision-makers.

In general, depending on the underlying system, such an optimization process might have additional process dependent

constraints that are not directly given by resource limitations, for example in cases when the optimization takes place in a parameter space that has less degrees of freedom than the full probability space

. Abstractly, this is expressed by allowing the optimization process to search only in a subset .

###### Definition 3.1 (Bounded rational decision-making process).

Let be a given utility function, and . A decision-making process with prior , posterior , and cost function is called bounded rational if its posterior satisfies

 (3.1)

for a given upper bound , or equivalently

 p∗=argminp∈Γ{Cq(p)∣∣Ep[U]≥U0}, (3.2)

for a given lower bound . In the case when the process constraints disappear, i.e. if , then a bounded rational decision-maker is called bounded-optimal.

The equivalence between (3.1) and (3.2) is easily seen from the equivalent optimization problem given by the formalism of Lagrange multipliers [25],

 pβ\coloneqqargminp∈Γ(Cq(p)−βEp[U])=argmaxp∈Γ(Ep[U]−1βCq(p)), (3.3)

where the cost or utility constraint is expressed by a trade-off between utility and cost, or cost and utility, with a trade-off parameter given by the Lagrange multiplier , which is chosen such that the constraint given by or is satisfied. It is easily seen from the maximization problem on the right side of (3.3) that a larger value of decreases the weight of the cost term and thus allows for higher values of the cost function. Hence, parametrizes the amount of resources the decision-maker can afford with respect to the cost function , and, at least in non-trivial cases (non-constant utilities) it is therefore a resource parameter with respect to in the sense of Definition 2.9. In particular, for , the decision-maker minimizes its cost function irrespective of the expected utility, and therefore stays at the prior, , whereas makes the cost function disappear so that the decision-maker becomes purely rational with a Dirac posterior centered on the optima of the utility function .

For example, in Figure 11 we can see how the posteriors of bounded-optimal decision-makers with different cost functions for and with utility leave a trace in probability space, by moving away from an exemplary prior and eventually arriving at the rational solution .

For informational costs (i.e. proportional to Kullback-Leibler divergence), is a resource parameter with respect to any cost function.

###### Proposition 3.2.

If is a family of bounded-optimal posteriors given by (3.3) with , then is a resource parameter with respect to any cost function, in particular

 q=p0⋨qpβ′⋨qpβ∀β′,β  with  β′<β. (3.4)

This generalizes a result in [78] to the case of non-uniform priors, by making use of our new characterization


text:
# Differential Equation Word Problem

1. Apr 9, 2012

### aves

I am having trouble starting this problem:

A tank is filled with 1000 liters of pure water. Brine containing 0.08 kg of salt per liter enters the tank at 9 liters per minute. Another brine solution containing 0.03 kg of salt per liter enters the tank at 9 liters per minute. The contents of the tank are kept thoroughly mixed and the drains from the tank at 18 liters per minute.

A. Determine the differential equation which describes this system. Let S(t) denote the number of kg of salt in the tank after t minutes. Then:
dS/dt=?

Any help on how to start this would be appreciated

2. Apr 9, 2012

### tiny-tim

welcome to pf!

hi aves! welcome to pf!

show us what you've tried, and where you're stuck, and then we'll know how to help!

3. Apr 9, 2012

### aves

I am not even sure how to make the differential equation out of the word problem. I can do the rest from there, but I just can't figure it out.

4. Apr 9, 2012

### Ray Vickson

Hint: in a small interval of time $\Delta t > 0,$ how many kg of salt enters the tank? How many kg of salt leaves the tank?

RGV

5. Apr 9, 2012

### tiny-tim

the question helps you on this, telling you to use "t" for time, in seconds, and S for the total weight of salt, in kg

now try translating into an equation the effect of …

6. Apr 9, 2012

### aves

Would it follow the general equation: S(t)=S0*e^(kt)?
Where t is the time and S0 is the initial weight of salt (0.08 kg)?

7. Apr 9, 2012

### tiny-tim

don't solve it

just write it!

dS/dt = … ?

8. Apr 9, 2012

### aves

Would it be:
dS/dt=0.72+0.27-18S/1000
?

Last edited: Apr 9, 2012


text:
Continue to Site

# LCD via rotary encoder + PIC - sanity check

Status
Not open for further replies.

#### dsc

##### Member
Hi guys,

I've decided to use a quadrature rotary encoder for my next project and the encoder itself will be used to control some settings via a 20x4 LCD. The idea is to have the knob 'scroll' through the available settings (3 for now) and the button to select the setting you want. After pressing the button you access the setting and further knob turns will scroll through the available options for that setting (usually ON or OFF). So it's like a two level menu accessible via encoder.

To handle the encoder I've written a short function which uses a primitive delay method to debounce the contacts:

Code:
[SIZE="2"][FONT="Times New Roman"]; ######################### CHECK ENCODER ##########################

Rot_Enc

movf	PORTC, W		;copy PORTC to W
andwf	b'00000111',W	;mask bits3-7 so only 0,1,2 are saved (the rotary enc inputs)
movwf	PORTC_new	;copy to variable

subwf	PORTC_last, W	;do (PORTC_last - PORTC_new) => W
btfsc	STATUS, Z		;check zero bit
goto	Rot_Enc_end	;values the same because result = 0
btfsc	deb_flag		;test debounce flag to see if this is first change detected
goto	Rot_Enc_change	;if PORTC is different than last value and again different after 50ms
call	Delay50		;primitive debounce by waiting 50ms
bsf	deb_flag, 0		;set debounce flag
goto	Rot_Enc		;after debouncing check port again

Rot_Enc_change

; check if turned right
movlw 	HIGH turn_right	;preload PCLATH with
movwf 	PCLATH		;high byte of turn_right table
movf	PORTC_last, W	;move PORTC_last to W
call	turn_right		;get the next correct value from the table
subwf	PORTC_new, W	;do (PORTC_new - next correct value) => W
btfsc	STATUS, Z		;check zero bit
goto	Rot_Enc_right	;values the same because result = 0

; check if turned left
movlw 	HIGH turn_left	;preload PCLATH with
movwf 	PCLATH		;high byte of turn_left table
movf	PORTC_last, W	;move PORTC_last to W
call	turn_left		;get the next correct value from the table
subwf	PORTC_new, W	;do (PORTC_new - next correct value) => W
btfsc	STATUS, Z		;check zero bit
goto	Rot_Enc_left	;values the same because result = 0

; check if pressed
btfss	PORTC_new, 2	;check bit 2 = knob press
goto	Rot_Enc_press	;values the same because result = 0
goto	Rot_Enc_update	;if not it means that there was a skip in steps so just update the value

Rot_Enc_right
; knob turned right

goto	Rot_Enc_update

Rot_Enc_left
; knob turned left

goto	Rot_Enc_update

Rot_Enc_press
; knob pressed

Rot_Enc_update
; update the last scan value

movf	PORTC_new, W	;move new value to W
movwf	PORTC_last		;update last scan value

Rot_Enc_end

retlw	0x00[/FONT][/SIZE]

[NOTE: the function grabs the PORTC value (only bits 0-2 are used for the encoder) and compares it to the last scan value. Tables turn_left, turn_right are not shown, but they hold the next correct values when turning the knob. The right/left/press parts don't hold any code yet of course]

Now the encoder will be turned by hand and obviously if you turn it too fast it will skip a step and not do anything. I'm curious if the 50ms delay for debounce is not going to force very slow turns in order to change the settings. Perhaps someone here tried something similar?

Regards,
dsc.

#### Mike - K8LH

##### Well-Known Member
I've used a rotary encoder for the input portion of an LCD menu system before and it worked quite well. The encoder I used had 16 detent positions with all four quadrature states between the detents so I simply detected all of the "change" states but ignored all but the change into the detent state. I used something like 2-msecs between samples...

Regards, Mike

You can determine "direction" of a quadrature A-B signal state change by exclusive-or'ing the A or B bit from the new sample with the opposite bit from the previous sample. Here's a quick example that uses a single variable (though you would still need to add your "inc" and "dec" code).

Code:
;
;  sample rotary encoder at 2-msec intervals
;
movf    PORTC,W         ; sample encoder, W = '------BA'
andlw   b'00000011'     ; mask off unused bits
xorwf   encold,W        ; state change?
bz      done            ; no, branch, else
xorwf   encold,W        ; restore WREG
rrf     encold,F        ; shift B old '-------B'
xorwf   encold,F        ; bit 0 = direction (A new ^ B old)
rrf     encold,F        ; Carry = direction
movwf   encold          ; update 'encold' to current sample
;
;  Carry = direction.  Check for detent position.
;
xorlw   b'00000011'     ; detent (BA = 11)?
bz      done            ; no, branch, else

done

Last edited:

#### dsc

##### Member
Hi Mike,

ah yes the famous XOR, much easier indeed, thanks for the tip.

I've noticed you haven't bothered with debouncing, is that because the transitions are pretty much bounce-less?

Regards,
Tom

EDIT: I've just checked and my rotary encoder goes through the entire A/B cycle per dent. This means the above code should work but it might lose a lot of steps (especially if I want to do time-based) debouncing. I might consider switching to 3 tactile switches instead.

Last edited:

#### Mike - K8LH

##### Well-Known Member
Hi Tom,

The switches still bounce but the intermediate state changes between detents are ignored in my implementation so it doesn't matter if they're bouncing between left and right.

The 2-msec sample interval I used seemed fast enough to keep me from missing a change and long enough to debounce the switches.

Regards, Mike

#### dsc

##### Member
Hi Mike,

ah yes true you only act on a dent (11 state) and not in between states. Might give this a try, although the encoder I've got has 32 positions instead of 16, so it's actually quite hard to make small changes manually and it might be quite hard to operate.

Regards,
Tom

#### Mike - K8LH

##### Well-Known Member
Tom,

Could you pass along distributor and part number for that encoder, please?

Mike

#### dsc

##### Member
Hi Mike,

unfortunately I don't know the model number (nothing on the case), don't know the manufacturer and don't have a datasheet. It's a big unknown to be honest.

Regards,
Tom

Status
Not open for further replies.

Replies
4
Views
970
Replies
3
Views
5K
Replies
6
Views
1K
Replies
42
Views
14K
Replies
25
Views
1K


text:
Main

## Main.OptionApmMvType History

July 27, 2017, at 03:10 PM by 201.171.58.156 -
Changed line 8 from:
 Default Value: 0

to:
 Default Value: 1

June 09, 2017, at 12:25 AM by 10.5.113.159 -
Changed lines 5-6 from:
to:
Added lines 14-15:

See also CV_TYPE, EV_TYPE

June 01, 2017, at 07:42 PM by 45.56.3.173 -
Added lines 1-13:

(:title APM.MV_TYPE - APMonitor Option:) (:keywords APM.MV_TYPE, Optimization, Estimation, Option, Configure, Default, Description:) (:description Manipulated variable type: 0=zero order hold, 1=linear:)

 Type: Integer, Input
Default Value: 0
Description: Manipulated variable type
0=zero order hold
1=first order hold (linear)

MV_TYPE specifies either a zero order hold (0) or a first order linear (1) interpolation between the MV endpoints. When the MV_STEP_HOR is two or greater, the MV_TYPE is applied only to each segment where adjustments are allowed. The MV segment is otherwise equal to the prior time segment. The MV_TYPE only influences the solution when the number of NODES is between 3 and 6. It is not important when NODES=2 because there are no interpolation nodes between the endpoints.


text:
E. Square Root of Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of length n is an array containing each integer from 1 to n exactly once. For example, q = [4, 5, 1, 2, 3] is a permutation. For the permutation q the square of permutation is the permutation p that p[i] = q[q[i]] for each i = 1... n. For example, the square of q = [4, 5, 1, 2, 3] is p = q2 = [2, 3, 4, 5, 1].

This problem is about the inverse operation: given the permutation p you task is to find such permutation q that q2 = p. If there are several such q find any of them.

Input

The first line contains integer n (1 ≤ n ≤ 106) — the number of elements in permutation p.

The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the elements of permutation p.

Output

If there is no permutation q such that q2 = p print the number "-1".

If the answer exists print it. The only line should contain n different integers qi (1 ≤ qi ≤ n) — the elements of the permutation q. If there are several solutions print any of them.

Examples
Input
42 1 4 3
Output
3 4 2 1
Input
42 1 3 4
Output
-1
Input
52 3 4 5 1
Output
4 5 1 2 3