text:
# Re: an alternate prisoners dilema.

## Main Question or Discussion Point

https://www.physicsforums.com/showthread.php?t=30021

Here's the thread, look at the last two pages, can anyone come up with a formula that anyone could learn it is so simple, that will lead with the suggestions here to an outcome that will in theory and on average mean that each prisoner is there for the least number of days.

I'm nowhere near competent enough to prove any mathematical theory this complex, but maybe you number crunchers could do it?

Feel free to use any of the suggestions or your own.

Does anyone know the solution, if there is one off the top of their heads?

Last edited:

## Answers and Replies

Related Set Theory, Logic, Probability, Statistics News on Phys.org
verty
Homework Helper
That question has been posted before. I think it relies on far too many bogus assumptions, like that the switch won't be fiddled by anyone else.

That question has been posted before. I think it relies on far too many bogus assumptions, like that the switch won't be fiddled by anyone else.
Indeed, but let's assume that either way the switch could be fiddled with or not. What is the best solution? So if the switch is often played around with how can you compensate, and if of course by the very nature of the puzzle people want to get out of there ASAP and don't screw with there lives what is the result?

We are assuming that it is in the best interest of all 100 prisoners to act honestly, if you do you get out of prison quicker, and if there is a moron/s who doesn't play the game how can you account for him/her or them.

verty
Homework Helper
Each person makes a scratch in the wall, when there are 100 scratches, they know. I think this relies on less dubious assumptions.

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
A naïve information theory argument suggests that you'll need 10,000 days. It follows from the following hypotheses:

(1) When selected, you expect to get at most one bit of information
(2) You need 100 bits of information to guarantee everyone has been selected

On the other hand, after a few thousand days, the odds that someone hasn't been picked is so staggeringly low that it's virtually certain everyone has been picked.

Last edited:
Each person makes a scratch in the wall, when there are 100 scratches, they know. I think this relies on less dubious assumptions.
No you can't do that as soon as you do the prison guards will fill in the scratch.

The whole point is, there is only one variable other than the prisoners and the guards. Otherwise it would make no sense to ask the question in the first place.

A naïve information theory argument suggests that you'll need 10,000 days. It follows from the following hypotheses:

(1) When selected, you expect to get at most one bit of information
(2) You need 100 bits of information to guarantee everyone has been selected

I'm trying to work on a stronger argument, but I'm having trouble getting a good estimate on the number of possible ways one can write a sequence of n numbers in the range [1, 100] such that each number is picked at least once.
Yes you are right, but with my scenarios it should be less on average, and a bright mathemetician should be able to work out a system? worry not no one has yet. I trust you guys might?

But read the original thread it gives you a way of making 100 less. we're looking at patterns here, and probability.

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
Like I said, it was just an approximation, and it was naïve. (and you missed a correction) :tongue: It's not usually easy to find theoretical minimums for problems like this. :tongue:

One omission is that the selection process gives you, on average, 0.08 bits of information per day, which is a heck of a lot more than the 0.01 bits per day you get from the lightbulb. (Of course, it might not be useful information)

And AKG's solution is valid. :grumpy: It just takes roughly 10,200 days, on average, before the counter is able to make his announcement. The exact formula for the expected amount of time is:

10,000 + 100 * (1 + 1/2 + 1/3 + 1/4 + ... + 1/99)

Last edited:
Like I said, it was just an approximation, and it was naïve. (and you missed a correction) :tongue: It's not usually easy to find theoretical minimums for problems like this. :tongue:

One omission is that the selection process gives you, on average, 0.08 bits of information per day, which is a heck of a lot more than the 0.01 bits per day you get from the lightbulb. (Of course, it might not be useful information)

And AKG's solution is valid. :grumpy: It just takes roughly 10,200 days, on average, before the counter is able to make his announcement. The exact formula for the expected amount of time is:

10,000 + 100 * (1 + 1/2 + 1/3 + 1/4 + ... + 1/99)

According to the maths professor who set the problem it isn't read the link. Do you think I'd of set it otherwise, the only valid answer is?

No ones got an answer yet.....

AKG is wrong because it's not 100%. and it's a slow answer, even mine was quicker.

No it doesnt you are assuming that the counter will be chosen x amount if times, Read the link.

Guys we've already done this, read the link.

You can do it in less.....

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
I don't see anywhere in the thread where the OP suggests AKG's solution doesn't work.

Any solution assumes each person is eventually picked at least once. :tongue: If you're going to reject AKG's solution on the grounds that we can't guarantee the counter gets picked enough times, you're going to have to reject any proposed solution on the grounds that we can't guarantee any particular individual gets picked at least once.

I don't see anywhere in the thread where the OP suggests AKG's solution doesn't work.

Any solution assumes each person is eventually picked at least once. :tongue: If you're going to reject AKG's solution on the grounds that we can't guarantee the counter gets picked enough times, you're going to have to reject any proposed solution on the grounds that we can't guarantee any particular individual gets picked at least once.
You don't?

No on the grounds that in order to posit an answer you must be 100% sure, he is wrong it's as simple as that

It doesn't work because the solution has to be 100% infalible, since every pick is random, the special chosen person could never be chosen in their lifetimes, leaving all the prisoners dead anyway. If he is chosen only once and someone screws up or messes with the system, everyone dies.

The answer is optimal, and infalible, I just don't have the maths moxie to know how to optimise any of my solutions.

If you've solved the problem, why doesn't the author of the problem agree? As the man in the example below says the reason is significant and also leads to a solution.

However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Some time ago, Ilia Denotkine has posted the following problem on the CTK Exchange
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

He then added a background to his question:

I have seen this problem on the forums, and here are some of the best solutions (to my opinion):

1.

At the beginning, the prisoners select a leader. Whenever a person (with the exception of the leader) comes into a room, he turns the lights on. If the lights are already on, he does nothing. When the leader goes into the room, he turns off the lights. When he will have turned off the lights 99 times, he is 100% sure that everyone has been in the room.
2.

wait 3 years, and with a great probability say that everyone has been in the room.

Does anyone know The optimal solution???

I have taken this problem from the www.ocf.berkeley.edu site, but I believe that you can find it on many others.

As I had a recollection of seeing this problem in [Winkler], I replied

The problem is indeed popular. It's even included in P. Winkler's Mathematical Puzzles, which is a recommended book in any event. Winkler also lists a slew of sources where the problem appeared, including ibm.com and a newsletter of the MSRI.

The solution is this:

The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room.

As it happened, I was wrong. This may be immediately surmised from Stuart Andersen's response. In my wonderment I contacted Peter Winkler who kindly set things straight for me. The formulation in his book is somewhat different, but this difference proves to be of major significance:

Each of n prisoners will be sent alone into a certain room, infinitely often, but in some arbitrary order determined by their jailer. The prisoners have a chance to confer in advance, but once the visits begin, their only means of communication will be via a light in the room which they can turn on or off. Help them design a protocol which will ensure that some prisoner will eventually be able to deduce that everyone has visited the room.

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
You don't?
Nope. I did a search for Tigers2B1's name in that thread, and I did not find any post where he rejected a solution.

No on the grounds that in order to posit an answer you must be 100% sure, he is wrong it's as simple as that
In AKG's solution, given the conditions of the problem, the counter is 100% sure when he makes the announcement.

... person could never be chosen in their lifetimes, leaving all the prisoners dead anyway.
As I said, if this is grounds for rejecting a solution, then this problem is provably unsolvable. If any individual is never chosen in their lifetimes, the prisoners will all die.

Nope. I did a search for Tigers2B1's name in that thread, and I did not find any post where he rejected a solution.

In AKG's solution, given the conditions of the problem, the counter is 100% sure when he makes the announcement.

As I said, if this is grounds for rejecting a solution, then this problem is provably unsolvable. If any individual is never chosen in their lifetimes, the prisoners will all die.
Yes. That is precisely it, the system must be 100% airtight. That's the point of the problem, it would be too easy to solve otherwise, your proof must be airtight. You must divise a system that will in 100% of cases result in the prisoners release, not in 99% of cases but 100/100 and optimal.

Otherwise I could of thought up a solution in five minutes.

Last edited:
Last edited:
seems like a long winded von Neuman architecture with prisoners.
Thanks for that.

With the one-counter solution, I wrote a simulator and ran it 100,000 times. Of course, this assumes that the prisoner assignment is totally arbitrary and the random numbers are "truly" random (no clustering, but evenly distributed).

Results:

0-999 days: 0 times
1000-1999 days: 0 times
2000-2999 days: 0 times
3000-3999 days: 0 times
4000-4999 days: 0 times
5000-5999 days: 0 times
6000-6999 days: 10 times
7000-7999 days: 459 times
8000-8999 days: 6806 times
9000-9999 days: 27676 times
10000-10999 days: 37769 times
11000-11999 days: 21085 times
12000-12999 days: 5461 times
13000-13999 days: 681 times
14000-14999 days: 52 times
15000-15999 days: 1 time

On average, that means you're looking at about 24 to 33 years before you're POSITIVE that everyone's been in the room. Being overly optomistic, you might actually wait 16 years. And there's about a 0.001% chance that you'll be waiting 42 years or more.

Now, comparaitvely, here's how many days it ACTUALLY took to get all 100 people in the room:

0-99 days: 0 times
100-199 days: 0 times
200-299 days: 409 times
300-399 days: 14543 times
400-499 days: 35987 times
500-599 days: 27511 times
600-699 days: 13046 times
700-799 days: 5353 times
800-899 days: 1998 times
900-999 days: 755 times
1000-1099 days: 266 times
1100-1199 days: 89 times
1200-1299 days: 33 times
1300-1399 days: 5 times
1400-1499 days: 3 times
1500-1599 days: 1 time
1600-1699 days: 1 time

So, if you wait 4 years and then assert that everyone's been in the room, you have around a 99.997% chance of being correct. That means chances are, you're pretty safe NOT using the technique, and just waiting, say, 5 years for a 99.9999% chance of safety, rather than 16-42 years for a 100% chance of safety.

DaveE

Schrodinger's Dog said:
The chance has to be 100%, that's the point otherwise it's easy to solve. Now the only method I know that does this in an optimised and 100% situation is to have no counter, but everyone as a counter, the first person to get enough results to call the warden calls the warden, in the unlikely event that the counter is never chosen, here at least you will be 100% corrrect in your assumption not 99.9999996 but 100% as the question asks. This is the point.

You have to bear in mind in the one counter situation if the counter is never chosen, all prisoners will be dead before the counter can make an assumption.

http://www.cut-the-knot.org/Probability/LightBulbs.shtml
This would work of course, but is it optimal? For instance, this would also work, I think:

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

What does optimal mean here? It could only reasonably mean that the prisoners are freed in the shortest time. So what is the expected time they must wait until Alice has counted to n-1? This is a rather elaborate calculation in probability, so the prisoners turn to the actuary (who is in prison for embezzlement) for some answers.

He explains that using Bayes theorem,
P(X|Y)·P(Y) = P(X&Y) = P(Y|X)·P(X)

and the linearity of expected value,
E(X|Y)·P(Y) + E(X|~Y)·P(~Y) = E(X)

you can calculate the expected time in prison like this:

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K) = n - 1, P(K=k) = 1/n·((n-1)/n)k, P(K = k & OFF) = 1/n·(c/n)k, which are fairly obvious.

Summing the last formula over all k gives P(OFF) = 1/(n-c). Bayes theorem then gives P(K = k|OFF) = (1-c/n)·(c/n)k, and from this you can calculate E(K|OFF) = c/(n-c) and linearity gives

E(K|ON) = ((n-1)(n-c)-c/(n-c))/(n-c-1).

Now let m be the number of times Alice visits and L be the number of days that pass before she next finds it on. Each time she finds it is off, c does not change, so all the calculations regarding the time until her next visit also do not change.

Therefore, the expected number of days until she next finds the light on is found by summing over all possible m to get the expected total time wasted on visits where the light is off, plus the expected time for the one visit where it was on. This gives

E(L) = (1+E(K|ON))P(ON) + sum(m(1+E(K|OFF))P(OFF)m
= n(1/(n-c-1) - 1/(n-c) + 1 - 1/(n-c)2).

Now we know how long we expect to wait from count = c to count = c+1. Therefore, we must sum this up from c=0 to c=n-2 to find the total expected time E(T). The result is E(T) = n2 - n/(n-1) - a, where a = S(1/c2) from 2 to n. Putting n=100 into this gives 9935.5 days, which is 26.2 years.

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c, d), which is obviously equal to P(c-1,d-1)·(1-(c-1)/n) + P(c, d-1)·(c/n). Of course, P(0, 0) = P(1, 1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n, d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

As they are about to kill Alice (who was already a member of Mensa) for coming up with a crazy plan to keep them in prison for 26 years, the game theorist (who is in prison for insider trading on the stock market) steps in to point out that this is a losing move. If they kill her now she will never go into the room, and the warden will keep them here forever.

In the happy ending, they let Alice live, and they all get out of prison in 5 years. Strangely, they all decline to join Mensa, preferring to enter actuarial training.
Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?
Schrodinger's Dog said:
This is why your idea and all the others are dismissed, not because it isn't likely, but because it does not meet the criteria of the experiment, read the quote again as for why and how this leads to the only conclusion that a single counter or 99 counters is not viable, only all counters will be 100%. Run your tests with that, is it more or less viable? I think you already know the answer, it not only more quickly leads to a result, but it is 100%. This is why he asid he was wrong because quite simply he was wrong, but this leads to the solution, since no one online appears to have got this technicality.

There answer is different and I can assure you I didn't read it before I came up with mine, so my answer could also be correct, and in fact, if your lucky it's even more optimised. But their answer is to just wait five years, now what if you have both as a precursor, aren't you optimising the situation still further?
It's OK by diligence and actually reading and following up my own links I have an answer, thanks for all the contributions.

I'd like to add 1 in a million is not 100% it's $$\frac{1}{1000000}1=0.000001%$$

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
Yes. That is precisely it, the system must be 100% airtight. That's the point of the problem, it would be too easy to solve otherwise, your proof must be airtight. You must divise a system that will in 100% of cases result in the prisoners release, not in 99% of cases but 100/100 and optimal.

Otherwise I could of thought up a solution in five minutes.
I repeat:

If there is a time limit, the problem has no solution.
If there is no time limit, AKG's solution is guarnateed to get the prisoners released.

If you disagree with my first point, then please demonstrate how to release the prisoners within a time limit of L, if prisoner #13 is never chosen until time L+1.

If you disagree with my second point, then please demonstrate how the guards may choose prisoners, within the constraints of the problem, so that AKG's method either gets the prisoners killed or leaves them eternally imprisoned.

Last edited:
I repeat:

If there is a time limit, the problem has no solution.
If there is no time limit, AKG's solution is guarnateed to get the prisoners released.

If you disagree with my first point, then please demonstrate how to release the prisoners within a time limit of L, if prisoner #13 is never chosen until time L+1.

If you disagree with my second point, then please demonstrate how the guards may choose prisoners, within the constraints of the problem, so that AKG's method either gets the prisoners killed or leaves them eternally imprisoned.

No it isn't if the choser is never chosen then it is not guaranteed, because all the prisoners might be dead before he gets chosen, if you have an issue take it up with the professor who proposed the question and says you are wrong because it's not optimised. To be honest I'm not sure how more clear I can make this 1 in a million is not 100% anyway. My solution is to have 100 counters plus the original light switch solution plus the five years probability, and thus it is 100%. The first prisoner to be chosen 100 times and to see the switches all down is 100% assured of being right. Time limit is their lifetimes. Otherwise my original lateral solution is true. But what are the chances that no one gets chosen 100 times before they die? Say in 50 years average? Now add in the fact that you have a five year probability solution?

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
No it isn't if the choser is never chosen then it is not guaranteed, because all the prisoners might be dead before he gets chosen
Which is why I say, if there is a time limit, this problem is unsolvable. :tongue:

if you have an issue take it up with the professor who proposed the question
You're the one who made the thread here. You are the one arguing the point. Thus, I'll take the issue up with you, thank you very much. :grumpy:

and says you are wrong because it's not optimised.
I never claimed AKG's was optimal.

To be honest I'm not sure how more clear I can make this 1 in a million is not 100% anyway.
Where are you getting "1 in a million" from?

My solution is to have 100 counters plus the original light switch solution plus the five years probability, and thus it is 100%.
What if one of the prisoners is never chosen in their lifetimes? :grumpy:
And if you have a "probability" solution, then it's not 100%. :grumpy:

I will repeat my point one last time.

If there is a time limit, this problem has no solution. You cannot guarantee that prisoner #26 will ever be picked before the time limit is up, and thus you cannot guarantee the prisoners' escape.

If there is not a time limit, AKG's solution guarantees their release: the counter cannot make his announcement before all 100 prisoners have entered the room.

Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
I see the original thread is still active: is there merit in having this topic in two threads? If not, I'm going to close this one.

According to the maths professor who set the problem it isn't read the link.
Ok. The math professor's solution WAS wrong. But his solution is NOT the same as AKG's solution. The solution he posted:

"The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room."

Which he agrees is wrong. Then, he receives the following, which he acknowledges is a correct, but possibly not optimal solution:

"Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room."

Notice that the latter solution (the correct one) matches AKG's solution.

DaveE

cristo
Staff Emeritus
Science Advisor
Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Schrodinger's Dog: In your post above you appear to be highlighting this point, and using it to justify why AKG's solution is incorrect. However, in AKG's solution, the prisoners will only declare that they have all been in when they are 100% sure! If the counter never enters, then they will not declare that they have all been in, hence this is a correct solution. It seems to me that in your solution you do not have 100% certainty, since you are talking about declaring when the prisoners are x% certain.

In all solutions to this problem, if a person does not enter the room, then the riddle can't be solved; this is clear, isn't it?

Which is why I say, if there is a time limit, this problem is unsolvable. :tongue:

You're the one who made the thread here. You are the one arguing the point. Thus, I'll take the issue up with you, thank you very much. :grumpy:

I never claimed AKG's was optimal.

Where are you getting "1 in a million" from?
But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c, d), which is obviously equal to P(c-1,d-1)·(1-(c-1)/n) + P(c, d-1)·(c/n). Of course, P(0, 0) = P(1, 1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n, d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

What if one of the prisoners is never chosen in their lifetimes? :grumpy:
And if you have a "probability" solution, then it's not 100%. :grumpy:

I will repeat my point one last time.

If there is a time limit, this problem has no solution. You cannot guarantee that prisoner #26 will ever be picked before the time limit is up, and thus you cannot guarantee the prisoners' escape.
Not true I explain this below.

If there is not a time limit, AKG's solution guarantees their release: the counter cannot make his announcement before all 100 prisoners have entered the room.
But this is unrealistic for the reasons given below.

And this is also wrong, since I didn't write the rules for the puzzle the professor did the answer is what he gave, all I'm saying is that this is not 100% either but 99.99999999% etc but obviously for the experiment this is close enough. However I merely suggested adding both systems in case the counter system got lucky.

Schrodinger's Dog: In your post above you appear to be highlighting this point, and using it to justify why AKG's solution is incorrect. However, in AKG's solution, the prisoners will only declare that they have all been in when they are 100% sure! If the counter never enters, then they will not declare that they have all been in, hence this is a correct solution. It seems to me that in your solution you do not have 100% certainty, since you are talking about declaring when the prisoners are x% certain.

In all solutions to this problem, if a person does not enter the room, then the riddle can't be solved; this is clear, isn't it?
Well there also wrong because it's not optimised, and it still doesn't make the solution 100% from the point of view of the prisoners, ie what is the best solution possible which will ensure there release in the minimum possible time. The answer is 3 years or if you want 100% then the alternate counter system, or both if you want the best possible solution, given that the counter system may get lucky and your out before 3 years.

Ok. The math professor's solution WAS wrong. But his solution is NOT the same as AKG's solution. The solution he posted:

"The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room."

Which he agrees is wrong. Then, he receives the following, which he acknowledges is a correct, but possibly not optimal solution:

"Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room."

Notice that the latter solution (the correct one) matches AKG's solution.

DaveE
And note it is also wrong and the explanation of why is given above.

I see the original thread is still active: is there merit in having this topic in two threads? If not, I'm going to close this one.
Fine by me.

Last edited:
cristo
Staff Emeritus
Science Advisor
and it still doesn't make the solution 100% from the point of view of the prisoners, ie what is the best solution possible which will ensure there release in the minimum possible time.
Where does the problem state that the solution must be proved to be optimal?

The only clause is that the prisoners must be 100% certain before they make a claim. In AKG's they are.

My counter-statement is always the same, and is never answered. Thus, I shall bow out of this discussion, since it is going nowhere!

Where does the problem state that the solution must be proved to be optimal?

The only clause is that the prisoners must be 100% certain before they make a claim. In AKG's they are.

My counter-statement is always the same, and is never answered. Thus, I shall bow out of this discussion, since it is going nowhere!
I showed you this in the link? Did anyone read it? Using Bayes theorem the probability that all are picked is in three years at 1/1000 probability and 1/1000000 at 5 years. thus the light switch answer is wrong, all you need do to optimise your time of release is to wait 5 years. Why would a prisoner chose one system that means waiting an average of 26 years over one that means you're all out in 5? Obviously in maths world the answer is correct but in a real world situation, which is kind of the point of having real people it is not right. The most unarguably correct answer taking the lifespans of the prisoners into account is to wait untill everyone has died but one prisoner, but this is hardly a valid solution although it is correct, there is both a solution with or without a time limit though if you get chosen 100 times after everyone has died then you can be sure that you're getting out by simply using the method of the light switch up, if no one changes it to down as in whatver solution then you know you are alone.

This is a logic problem or an applied maths problem, not a pure maths problem.

Last edited:
cristo
Staff Emeritus
Science Advisor
AKG's solution satisfies the conditions as stated in the problem statement in the original post. Therefore it is a solution to the riddle.

Does the fact that there happens to be another solution that takes less time for the prisoners to be free mean that AKG's solution is incorrect?

That is my point!!

AKG's solution satisfies the conditions as stated in the problem statement in the original post. Therefore it is a solution to the riddle.

Does the fact that there happens to be another solution that takes less time for the prisoners to be free mean that AKG's solution is incorrect?

That is my point!!
I never said that I just said it's flawed and thus wrong from the point of view of the prisoners, reality is second place to mathematics though obviously. I don't see why it is correct if there's is a chance it is not 100% anyway, so I guess it's a technicality.

Look I'm honestly not trying to annoy anyone I just thought it would be fun to think about the limitations of the solutions and how logically they do not meet the criteria of the OP on that thread. Obviously it isn't fun, and obviously no ones interested so as suggested lets just agree to disagree and close the thread.

The prisoner must be 100% sure he is right.


text:
# Math Help - Higher level Math Proof, using induction

1. ## Higher level Math Proof, using induction

Image - TinyPic - Free Image Hosting, Photo Sharing & Video Hosting

2. ## Re: Higher level Math Proof, using induction

This looks like a problem from the American Math Monthly.

3. ## Re: Higher level Math Proof, using induction

I'm not really sure the original source. Its a bonus question for my foundations class. For some reason I have just been really struggling. I have never gotten lower then an A on a math test, and when my last one came back a C. I just got kinda shook up. So I figured I'd look for some help.

format: plain


text:
# Implication and entailment

I have several questions about entailment and implication.

1) Let $A = \{p_1, ..., p_n \}$ be some set of logical statements and $q$ some logical statement. Is it right that "$A \models q$" is a correct logical statement, i.e. it may be true, or false and we may always define its logical meaning?

2) What if $A = \varnothing$?

3) Is it right that $(A \models p) \equiv ((p_1 \land ... \land p_n) \rightarrow q)$ ?

4) How should i treat the following situation: $\{ q, q->p \} \models p \rightarrow r$. Is it a correct entailment? I'm confused because there is $r$ on the right and there is no $r$ on the left.

EDIT

Sorry for my English. I suppose "logical proposition" is a more correct term then "logical statement".

• If $q$ is a "logical statement" (assuming you mean is logically valid), then we have $\vDash q$, and so a fortiori $A \vDash q$. (If $q$ is true on all interpretations, it is true in particular on all intepretations which make the members of $A$ true.)

• If $q$ is a "logical statement", then we have $\emptyset \vDash q$. (For $\emptyset \vDash q$ says that $q$ is true on those interpretations which make any $p$ true if $p$ is a member of $\emptyset$ -- which are, vacuously, all interpretations).

• Not quite. You mean $(A \models q)$ iff $\models ((p_1 \land ... \land p_n) \rightarrow q)$ or $(A \models q) \Leftrightarrow\ \models ((p_1 \land ... \land p_n) \rightarrow q)$ [You want metalinguistic claims on both sides of the equivalence.]

• Finally $\{ q, q->p \} \models p \rightarrow r$ is plainly not correct. Suppose $p$ and $q$ are true, and $r$ false.

• You seem to be using "logical statement" for what I would call "logically valid statement". Is this standard terminology, or a typo? – Henning Makholm Mar 22 '14 at 12:29
• Well, I was using quotes to signal I was indeed quoting the OP, and I took him indeed to mean logically valid statement -- I've clarified! – Peter Smith Mar 22 '14 at 12:48
• Sorry, I was confused because the question seemed to make better sense to me if "logical statement" meant "wff" and "correct" means "well-formed" rather than "true". – Henning Makholm Mar 22 '14 at 13:09
• Well I agree it wasn't clear ...but I though he was worrying about cases where we say that a [logically valid] $q$ is entailed by a load of irrelevant $p_i$, or by nothing. – Peter Smith Mar 22 '14 at 13:17

I'm assuming (contrary to Peter Smith), that by "logical statement" you mean "well-formed formula" or possibly even "sentence".

1) It is true that if $p_1$ through $p_n$ and $q$ are formulas, then we can say $p_1,\ldots,p_n\vDash q$, and that $p_1,\ldots,p_n\vDash q$ will be either true or false. But $p_1,\ldots,p_n\vDash q$ is not itself a formula. It is a claim about formulas at the metalevel.

A metalevel claim such as $\vDash q$ has a definite truth value in itself, (though it can be difficult to determine what it is). On the other hand a formula only acquires a truth value when we specify an interpretation for the non-logical symbols in it.

2) All of the above holds for empty sets of assumptions too.

3) No, because $A\vDash p$ is a property at the metalevel and $(p_1\land \cdots \land p_n)\to q$ is a formula itself. They are not even the same kind of things, so they can't be equivalent.

4) $p, p\to q\vDash p\to r$ is a meaningful claim, which just happens to be false. I suspect you're using "correct" to mean "meaningful" rather than "true", in which case you would probably call it "correct".


text:
# Multivariate Pareto distribution

In statistics, a multivariate Pareto distribution is a multivariate extension of a univariate Pareto distribution.[1]

There are several different types of univariate Pareto distributions including Pareto Types I−IV and Feller−Pareto.[2] Multivariate Pareto distributions have been defined for many of these types.

## Bivariate Pareto distributions

### Bivariate Pareto distribution of the first kind

Mardia (1962)[3] defined a bivariate distribution with cumulative distribution function (CDF) given by

$F(x_1, x_2) = 1 -\sum_{i=1}^2\left(\frac{x_i}{\theta_i}\right)^{-a}+ \left(\sum_{i=1}^2 \frac{x_i}{\theta_i} - 1\right)^{-a}, \qquad x_i > \theta_i > 0, i=1,2; a>0,$

and joint density function

$f(x_1, x_2) = (a+1)a(\theta_1 \theta_2)^{a+1}(\theta_2x_1 + \theta_1x_2 - \theta_1 \theta_2)^{-(a+2)}, \qquad x_i \geq \theta_i>0, i=1,2; a>0.$

The marginal distributions are Pareto Type 1 with density functions

$f(x_i)=a\theta_i^a x_i^{-(a+1)}, \qquad x_i \geq \theta_i>0, i=1,2.$

The means and variances of the marginal distributions are

$E[X_i] = \frac{a \theta_i}{a-1}, a>1; \quad Var(X_i)=\frac{a\theta_i^2}{(a-1)^2(a-2)}, a>2; \quad i=1,2,$

and for a > 2, X1 and X2 are positively correlated with

$\operatorname{cov}(X_1, X_2) = \frac{\theta_1 \theta_2}{(a-1)^2 (a-2)}, \text{ and } \operatorname{cor}(X_1, X_2) = \frac{1}{a}.$

### Bivariate Pareto distribution of the second kind

Arnold[4] suggests representing the bivariate Pareto Type I complementary CDF by

$\overline{F}(x_1,x_2) = \left(1 + \sum_{i=1}^2 \frac{x_i-\theta_i}{\theta_i} \right)^{-a}, \qquad x_i > \theta_i, i=1,2.$

If the location and scale parameter are allowed to differ, the complementary CDF is

$\overline{F}(x_1,x_2) = \left(1 + \sum_{i=1}^2 \frac{x_i-\mu_i}{\sigma_i} \right)^{-a}, \qquad x_i > \mu_i, i=1,2,$

which has Pareto Type II univariate marginal distributions. This distribution is called a multivariate Pareto distribution of type II by Arnold.[4] (This definition is not equivalent to Mardia's bivariate Pareto distribution of the second kind.)[3]

For a > 1, the marginal means are

$E[X_i] = \mu_i + \frac{\sigma_i}{a-1}, \qquad i=1,2,$

while for a > 2, the variances, covariance, and correlation are the same as for multivariate Pareto of the first kind.

## Multivariate Pareto distributions

### Multivariate Pareto distribution of the first kind

Mardia's[3] Multivariate Pareto distribution of the First Kind has the joint probability density function given by

$f(x_1,\dots,x_k) = a(a+1)\cdots(a+k-1) \left(\prod_{i=1}^k \theta_i \right)^{-1} \left(\sum_{i=1}^k \frac{x_i}{\theta_i} - k + 1 \right)^{-(a+k)}, \qquad x_i > \theta_i > 0, a > 0, \qquad (1)$

The marginal distributions have the same form as (1), and the one-dimensional marginal distributions have a Pareto Type I distribution. The complementary CDF is

$\overline{F}(x_1,\dots,x_k) = \left(\sum_{i=1}^k \frac{x_i}{\theta_i}-k+1 \right)^{-a}, \qquad x_i > \theta_i > 0, i=1,\dots,k; a > 0. \quad (2)$

The marginal means and variances are given by

$E[X_i] = \frac{a \theta_i}{a-1}, \text{ for } a > 1, \text{ and } Var(X_i) = \frac{a \theta_i^2}{(a-1)^2 (a-2)}, \text{ for } a > 2.$

If a > 2 the covariances and correlations are positive with

$\operatorname{cov}(X_i, X_j) = \frac{\theta_i \theta_j}{(a-1)^2(a-2)}, \qquad \operatorname{cor}(X_i, X_j) = \frac{1}{a}, \qquad i \neq j.$

### Multivariate Pareto distribution of the second kind

Arnold[4] suggests representing the multivariate Pareto Type I complementary CDF by

$\overline{F}(x_1, \dots, x_k) = \left(1 + \sum_{i=1}^k \frac{x_i-\theta_i}{\theta_i} \right)^{-a}, \qquad x_i > \theta_i>0, \quad i=1,\dots, k.$

If the location and scale parameter are allowed to differ, the complementary CDF is

$\overline{F}(x_1,\dots,x_k) = \left(1 + \sum_{i=1}^k \frac{x_i-\mu_i}{\sigma_i} \right)^{-a}, \qquad x_i > \mu_i, \quad i=1,\dots,k, \qquad (3)$

which has marginal distributions of the same type (3) and Pareto Type II univariate marginal distributions. This distribution is called a multivariate Pareto distribution of type II by Arnold.[4]

For a > 1, the marginal means are

$E[X_i] = \mu_i + \frac{\sigma_i}{a-1}, \qquad i=1,\dots,k,$

while for a > 2, the variances, covariances, and correlations are the same as for multivariate Pareto of the first kind.

### Multivariate Pareto distribution of the fourth kind

A random vector X has a k-dimensional multivariate Pareto distribution of the Fourth Kind[4] if its joint survival function is

$\overline{F}(x_1,\dots,x_k) = \left( 1 + \sum_{i=1}^k \left(\frac{x_i-\mu_i}{\sigma_i}\right)^{1/\gamma_i}\right)^{-a}, \qquad x_i > \mu_i, \sigma_i > 0, i=1,\dots,k; a > 0. \qquad (4)$

The k1-dimensional marginal distributions (k1<k) are of the same type as (4), and the one-dimensional marginal distributions are Pareto Type IV.

### Multivariate Feller–Pareto distribution

A random vector X has a k-dimensional Feller–Pareto distribution if

$X_i = \mu_i + (W_i / Z)^{\gamma_i}, \qquad i=1,\dots,k, \qquad (5)$

where

$W_i \sim \Gamma(\beta_i, 1), \quad i=1,\dots,k, \qquad Z \sim \Gamma(\alpha, 1),$

are independent gamma variables.[4] The marginal distributions and conditional distributions are of the same type (5); that is, they are multivariate Feller–Pareto distributions. The one–dimensional marginal distributions are of Feller−Pareto type.

## References

1. ^ S. Kotz, N. Balakrishnan, N. L. Johnson (2000). "52". Continuous Multivariate Distributions 1 (second ed.). ISBN 0-471-18387-3.
2. ^ Barry C. Arnold (1983). Pareto Distributions. International Co-operative Publishing House. ISBN 0-89974-012-X. Chapter 3.
3. ^ a b c Mardia, K. V. "Multivariate Pareto distributions". Annals of Mathematical Statistics 33: 1008–1015. doi:10.1214/aoms/1177704468.
4. Barry C. Arnold (1983). Pareto Distributions. International Co-operative Publishing House. ISBN 0-89974-012-X. Chapter 6.


text:
# Review: Information Effects

One of the most exciting papers I’ve read in a long time is James and Sabry’s Information Effects. It starts with the hook “computation is a physical process which, like all other physical processes, is fundamentally reversible,” and it goes from there. If that doesn’t immediately pull you in, perhaps some of the subsequent PL jargon will – it promises a “typed, universal, and reversible computation model in which information is treated as a linear resource”.

I don’t know about you, but I was positively shaking with anticipation at this point. That’s one heck of an abstract.

After some philosophy and overview of the paper, James and Sabry dive into the appetizer in a section titled “Thermodynamics of Computation and Information”. They give the following definition:

DEFINITION 2.2 (Entropy of a variable). Let $b$ be a (not necessarily finite) type whose values are labeled $b_1$, $b_2$, $\ldots$. Let $\xi$ be a random variable of type $b$ that is equal to $b_i$ with probability $p_i$. The entropy of $\xi$ is defined as $- \sum p_i \log{p_i}$.

and the following, arguably less inspired definition:

DEFINITION 2.3 (Output entropy of a function). Consider a function f : a -> b where b is a (not necessarily finite) type whose values are labeled $b_1$, $b_2$, $\ldots$. The output entropy of the function is given by $- \sum q_j \log{q_j}$ where $q_j$ indicates the probability of the function to have value $b_j$.

We can say now that a function is reversible if and only if the entropy of its arguments is equal to the entropy of its output. Which is to say that the gain in entropy across the function is 0.

Of course, as astute students of mathematics we know that reversibility of a function is equivalent to whether that function is an isomorphism. While this is how we will prefer to think of reversibility, the definition in terms of entropy brings up interesting questions of pragmatics that we will get to later.

James et al. present the following language, which we have reproduced here translated into Haskell. The language is first order, and so we will ignore function types, giving us the types:

{-# LANGUAGE TypeOperators     #-}
{-# LANGUAGE NoImplicitPrelude #-}

-- Corresponds to Haskell '()' type
data U = U

-- Corresponds to Haskell 'Either' type
data a + b
= InL a
| InR a

-- Corresponds to Haskell '(,)' type
data a * b = Pair a b

The language presented is based around the notion of type isomorphisms, and so in order to model this language in Haskell, we’ll need the following types:

data a <=> b = Iso
{ run :: a -> b
, rev :: b -> a
}

This type a <=> b represents an isomorphism between type a and type b, as witnessed by a pair of functions to and from. This probably isn’t the best encoding of an isomorphism, but for our purposes it will be sufficient.

James and Sabry present the following axioms of their language:

swapP   ::       a + b <=> b + a
assocP  :: a + (b + c) <=> (a + b) + c
unite   ::       U * a <=> a
swapT   ::       a * b <=> b * a
assocT  :: a * (b * c) <=> (a * b) * c
distrib :: (a + b) * c <=> (a * c) + (b * c)
id      ::           a <=> a

The implementations of these terms are all trivial, being that they are purely syntactic isomorphisms. They will not be reproduced here, but can be found in the code accompanying this post. The motivated reader is encouraged to implement these for themself.

With the terms of our algebra out of the way, we’re now ready for the operators. We are presented with the following:

-- Isomorphisms are symmetric.
sym :: (a <=> b) -> (b <=> a)

-- Isomorphisms are transitive.
(>>) :: (a <=> b) -> (b <=> c) -> (a <=> c)

-- Products and coproducts are bifunctors.
(.+) :: (a <=> c) -> (b <=> d) -> (a + b <=> c + d)
(.*) :: (a <=> c) -> (b <=> d) -> (a * b <=> c * d)

It turns out that the resulting language is already surprisingly expressive. We can encode booleans:

type Bool = U + U

true, false :: Bool
true  = InL U
false = InR U

With these out of the way, James et al. show us a “one-armed if-expression”: if the incoming Bool is true, transform the a by the provided combinator:

ifthen :: (a <=> a) -> (Bool * a <=> Bool * a)
ifthen c = distrib >> (id .* c) .+ id >> sym distrib

For syntactic convenience, we will enable rebindable syntax, allowing us to represent these chains of isomorphism transitivities with do notation. We can thus express the above more clearly as:

{-# LANGUAGE RebindableSyntax #-}

ifthen :: (a <=> a) -> (Bool * a <=> Bool * a)
ifthen c = do
distrib
(id .* c) .+ id
sym distrib

The mystery behind naming our transitivity operator (>>) is thus explained.

But how does our ifthen combinator actually work? Recall that Bool = U + U, meaning that we can distribute the Us across the pair, giving us the type (U * a) + (U * a). The left branch (of type U * a) of this coproduct has an inhabitant if the incoming boolean was true.

We can thus bimap over the coproduct. Since the left case corresponds to an incoming true, we can apply an isomorphism over only that branch. Because we want to transform the incoming a by the combinator c, we then bimap over our U * a with id .* c – not touching the U but using our combinator.

Finally, we need to repackage our (U * a) + (U * a) into the correct return type Bool * a, which we can do by factoring out the a. Factoring is the inverse of distributing, and so we can use the sym operator to “undo” the distrib.

It’s crazy, but it actually works! We can run these things to convince ourselves. Given:

not :: Bool <=> Bool
not = swapP  -- move a left ('true') to a right ('false'), and vice versa.

We get:

> run (ifthen not) $Pair true false Pair true true > run (ifthen not)$ Pair false false
Pair false false

Neat, no? For fun, we can also run these things backwards:

> rev (ifthen not) $Pair true true Pair true false > rev (ifthen not)$ Pair false false
Pair false false

James et al. are eager to point out that ifthen (ifthen not) :: Bool * (Bool * Bool) <=> Bool * (Bool * Bool) is the Toffoli gate – a known universal reversible gate. Because we can implement Toffoli (and due to its universalness), we can thus implement any boolean expression.

## Recursion and Natural Numbers

Given two more primitives, James and Sabry show us how we can extend this language to be “expressive enough to write arbitrary looping programs, including non-terminating ones.”

We’ll need to define a term-level recursion axiom:

trace :: (a + b <=> a + c) -> (b <=> c)

The semantics of trace are as follows: given an incoming b (or, symmetrically, a c), lift it into InR b :: a + b, and then run the given iso over it looping until the result is an InR c, which can then be returned.

Notice here that we have introduced potentially non-terminating looping. Combined with our universal boolean expressiveness, this language is now Turing-complete, meaning it is capable of computing anything computable. Furthermore, by construction, we also have the capability to compute backwards – given an output, we can see what the original input was.

You might be concerned that the potential for partiality given by the trace operator breaks the bijection upon which all of our reversibility has been based. This, we are assured is not a problem, because a divergence is never actually observed, and as such, does not technically violate the bijectiveness. It’s fine, you guys. Don’t worry.

There is one final addition we need, which is the ability to represent inductive types:

data Fix f = Fix { unFix :: f (Fix f) }

fold :: f (Fix f) <=> Fix f
fold = Iso Fix unFix

Given these things, we can define the natural numbers a little circuitously. We can define their type as follows:

type Nat = Fix ((+) U)

Constructing such things is a little tricky, however. First we’ll need a way to introduce a coproduct. The type and name of this isomorphism should be suggestive:

just :: a <=> U + a
just = trace $do sym assocP (sym fold >> swapP) .+ id just is a tricky little beast; it works by using trace to eliminate the Nat + U of a (Nat + U) + (U + a). We can follow the derivation a little more closely: body :: (Nat + U) + a <=> (Nat + U) + (U + a) body = do sym assocP -- Nat + (U + a) sym fold .+ id -- (U + Nat) + (U + a) swapP .+ id -- (Nat + U) + (U + a) trace body :: a <=> U + a I wish I had come up with this, because it’s quite clever. Notice however that this is a partial isomorphism; when run backwards, it will diverge in the case of InR U :: U + a. Given just, we can now define succ: succ :: Nat <=> Nat succ = do just -- U + Nat fold -- Nat James et al. provide a little more machinery in order to get to the introduction of a 0: injectR :: a <=> a + a injectR = do sym unite -- U * a just .* id -- (U + U) * a distrib -- (U * a) + (U * a) unite .+ unite -- a + a and finally: zero :: U <=> Nat zero = trace$ do
id       -- Nat + U
swapP    -- U + Nat
fold     -- Nat
injectR  -- Nat + Nat

What’s interesting here is that the introduction of 0 is an isomorphism between U and Nat, as we should expect since 0 is a constant.

### Induction on Nats

The paper teases an implementation of isEven for natural numbers – from the text:

For example, it is possible to write a function even? :: Nat * Bool <=> Nat * Bool which, given inputs (n, b), reveals whether n is even or odd by iterating not n-times starting with b. The iteration is realized using trace as shown in the diagram below (where we have omitted the boxes for fold and unfold).

Emphasis mine. The omitted fold and unfold bits of the diagram are the actual workhorses of the isomorphism, and their omission caused me a few days of work to rediscover. I have presented the working example here to save you, gentle reader, from the same frustration.

The insight is this – our desired isomorphism has type Nat * a <=> Nat * a. Due to its universally qualified nature, we are unable to pack any information into the a, and thus to be reversible, the Nat must be the same on both sides. Since we are unable to clone arbitrary values given our axioms (seriously! try it!), our only solution is to build a resulting Nat up from 0 as we tear apart the one we were given.

We can view the a in trace :: (a + b <=> a + c) -> (b <=> c) as “scratch space” or “intermediate state”. It is clear that in order to execute upon our earlier insight, we will need three separate pieces of state: the Nat we’re tearing down, the Nat we’re building up, and the a along for the ride.

For reasons I don’t deeply understand, other than it happened to make the derivation work, we also need to introduce a unit to the input of our traced combinator.

With this line of reasoning, we have the following:

iterNat :: (a <=> a) -> (Nat * a <=> Nat * a)
iterNat step = do
sym unite
trace $do id -- (Nat' * (Nat * a)) + (U * (Nat * a)) unite For clarity, we’ll annotate the natural number under construction as Nat'. When the iteration begins, our combinator receives an InR whose contents are of type U * (Nat * a) corresponding to the fact that there is not yet any internal state. From there we can factor our the Nat * a:  ... trace$ do
id           -- (Nat' * (Nat * a)) + (U * (Nat * a))
sym distrib  -- (Nat' + U) * (Nat * a)
...

All of a sudden this looks like a more tenable problem. We now have a product of (conceptually) a Maybe Nat', the Nat being torn down, and our a. We can fold :: U + Nat <=> Nat our Nat', which will give us 0 in the case that the state hasn’t yet been created, or $n+1$ in the case it has.

  ...
trace $do id -- (Nat' * (Nat * a)) + (U * (Nat * a)) sym distrib -- (Nat' + U) * (Nat * a) (swapP >> fold) .* id -- Nat' * (Nat * a) ... The only thing left is to destruct the incoming Nat and apply our step isomorphism. We introduce a lemma to help: swapBacT :: a * (b * c) <=> b * (a * c) swapBacT = do assocT swapT .* id sym assocT which we can then use to move the pieces of our state and destruct the correct number:  ... trace$ do
id                         -- (Nat' * (Nat * a)) + (U * (Nat * a))
sym distrib                -- (Nat' + U) * (Nat * a)
(swapP >> fold) .* id      -- Nat' * (Nat * a)
swapBacT                   -- Nat * (Nat' * a)
(sym fold >> swapP) .* id  -- (Nat + U) * (Nat' * a)
...

We can then distribute out the Nat + U again:

  ...
trace $do id -- (Nat' * (Nat * a)) + (U * (Nat * a)) sym distrib -- (Nat' + U) * (Nat * a) (swapP >> fold) .* id -- Nat' * (Nat * a) swapBacT -- Nat * (Nat' * a) (sym fold >> swapP) .* id -- (Nat + U) * (Nat' * a) distrib -- (Nat * (Nat' * a)) + (U * (Nat' * a)) ... And finally, we apply our step iso to the internal state (we do this after the distrib so that we don’t apply the combinator if the incoming number was 0). The fruits of our labor are presented in entirety: iterNat :: (a <=> a) -> (Nat * a <=> Nat * a) iterNat step = do sym unite trace$ do
id                          -- (Nat' * (Nat * a)) + (U * (Nat * a))
sym distrib                 -- (Nat' + U) * (Nat * a)
(swapP >> fold) .* id       -- Nat' * (Nat * a)
swapBacT                    -- Nat * (Nat' * a)
(sym fold >> swapP) .* id   -- (Nat + U) * (Nat' * a)
distrib                     -- (Nat * (Nat' * a)) + (U * (Nat' * a))
(id .* (id .* step)) .+ id  -- (Nat * (Nat' * a)) + (U * (Nat' * a))
swapBacT .+ id              -- (Nat' * (Nat * a)) + (U * (Nat' * a))
unite

Lo and behold, the types now line up, and thus quod erat demonstrandum. The implementation of isEven is now trivial:

isEven :: Nat * Bool <=> Nat * Bool
isEven = iterNat not

which computes if a Nat is even in the case the incoming Bool is false, and whether it is odd otherwise.

## Lists

James and Sabry provide a sketch of how to define lists, but I wanted to flesh out the implementation to test my understanding.

For reasons I don’t pretend to understand, Haskell won’t let us partially apply a type synonym, so we’re forced to write a higher-kinded data definition in order to describe the shape of a list.

-- To be read as @type ListF a b = U + (a * b)@.
data ListF a b
= Nil
| Cons a b

We can then get the fixpoint of this in order to derive a real list:

type List a = Fix (ListF a)

And to get around the fact that we had to introduce a wrapper datatype in order to embed this into Haskell, we then provide an eliminator to perform “pattern matching” on a List a. In a perfect world, this function would just be sym fold, but alas, we must work with what we have.

liste :: List a <=> U + (a * List a)
liste = Iso to from
where
to (Fix Nil)          = InL U
to (Fix (Cons a b))   = InR (Pair a b)
from (InL U)          = Fix Nil
from (InR (Pair a b)) = Fix (Cons a b)

From here, it is trivial to write cons:

cons :: a * List a <=> List a
cons = do
just       -- U + (a * List a)
sym liste  -- List

However, introducing a list via nil is actually quite complicated. Note the parallels with the natural numbers, where it was trivial to define succ but required a clever trick to introduce a zero.

We begin with a lemma that moves a coproduct:

swapCbaP :: (a + b) + c <=> (c + b) + a
swapCbaP = do
sym assocP   -- a + (b + c)
swapP        -- (b + c) + a
swapP .+ id  -- (c + b) + a

And given that, we can write an isomorphism between any a and any b. The catch, of course, is that you can never witness such a thing since it obviously doesn’t exist. Nevertheless, we can use it to convince the type checker that we’re doing the right thing in cases that would diverge in any case.

diverge :: a <=> b
diverge = trace $do id -- (a + b) + a swapP .+ id -- (b + a) + a swapCbaP -- (a + a) + b sym injectR .+ id -- a + b swapP -- b + a right .+ id -- (b + b) + a swapCbaP -- (a + b) + b Finally we can implement nil using the same trick we did for zero – use trace to vacuously introduce exactly the type we need, rip out the result, and then divergently reconstruct the type that trace expects. nil :: U <=> List a nil = trace$ do
id                        -- (a * List a) + U
swapP                     -- U + (a * List a)
sym liste                 -- List a
sym unite                 -- U * List a
just .* id                -- (U + U) * List a
distrib                   -- (U * List a) + (U * List a)
(diverge .* id) .+ unite  -- (a * List a) + List a

### Induction on Lists

In a manner spiritually similar to iterNat, we can define iterList :: (a * z <=> b * z) -> (List a * z <=> List b * z). The semantics are mostly what you’d expect from its type, except that the resulting List b is in reverse order due to having to be constructed as the List a was being destructed. We present the implementation here for completeness but without further commentary.

iterList :: (a * z <=> b * z) -> (List a * z <=> List b * z)
iterList f = do
sym unite
trace $do -- ((b * List b) * (List a * z)) + (U * (List a * z)) sym distrib -- ((b * List b) + U) * (List a * z) (swapP >> sym liste) .* id -- List b * (List a * z) swapBacT -- List a * (List b * z) liste .* id -- (U + (a * List a)) * (List b * z) distrib -- (U * (List b * z)) + ((a * List a) * (List b * z)) (.+) id$                   -- (U * (List b * z)) + ...
do
swapT .* id             --    ((List a * a) * (List b * z))
swapAcbdT               --    ((List a * List b) * (a * z))
id .* f                 --    ((List a * List b) * (b * z))
swapAcbdT               --    ((List a * b) * (List b * z))

swapP                       -- ((List a * b) * (List b * z)) + (U * (List b * z))
(swapT .* id) .+ id         -- ((b * List a) * (List b * z)) + (U * (List b * z))
swapAcbdT .+ id             -- ((b * List b) * (List a * z)) + (U * (List b * z))
unite

swapAcbdT :: (a * b) * (c * d) <=> (a * c) * (b * d)
swapAcbdT = do
sym assocT
id .* sw
assocT

From here, the functional programming favorite map is easily defined:

map :: (a <=> b) -> (List a <=> List b)
map f = do
sym unite
swapT
iterList f .* id -- map iterList id -- reverse to original order swapT unite ## Remnants The bulk of the remainder of the paper is an extension to the reversible semantics above, introducing create :: U ~> a and erase :: a ~> U where (~>) is a non-reversible arrow. We are shown how traditional non-reversible languages can be transformed into the (~>)-language. Of more interest is James and Sabry’s construction which in general transforms (~>) (a non-reversible language) into (<=>) (a reversible one). But how can such a thing be possible? Obviously there is a trick! The trick is this: given a ~> b, we can build h * a <=> g * b where h is “heap” space, and g is “garbage”. Our non-reversible functions create and erase thus become reversible functions which move data from the heap and to the garbage respectively. Unfortunately, this is a difficult thing to model in Haskell, since the construction requires h and g to vary based on the axioms used. Such a thing requires dependent types, which, while possible, is quite an unpleasant undertaking. Trust me, I actually tried it. However, just because it’s hard to model entirely in Haskell doesn’t mean we can’t discuss it. We can start with the construction of (~>): {-# LANGUAGE GADTs #-} data a ~> b where Arr :: (a <=> b) -> (a ~> b) Compose :: (a ~> b) -> (b ~> c) -> (a ~> c) First :: (a ~> b) -> (a * c ~> b * c) Left :: (a ~> b) -> (a + c ~> b + c) Create :: U ~> a Erase :: a ~> U The axioms here are quite explanatory and will not be discussed further. A point of note, however, is that Arr allows arbitrary embeddings of our iso (<=>) language in this arrow language. The semantics of Create is given by induction: \newcommand{\u}{\text{U}} \begin{align*} \text{create U} & \mapsto \u \\ \text{create}(a + b) & \mapsto \text{InL } (\text{create } a) \\ \text{create}(a \times b) & \mapsto (\text{create } a, \text{create } b) \end{align*} With the ability to create and erase information, we’re (thankfully) now able to write some everyday functions that you never knew you missed until trying to program in the iso language without them. James et al. give us what we want: fstA :: a * b ~> a fstA = do arr swapT -- b * a first erase -- U * a arr unite -- a In addition to projections, we also get injections: leftA :: a ~> a + b leftA = do arr sym unite  -- U * a
first create     -- (a + b) * a
arr leftSwap     -- (a + b) * a
fstA             -- a + b

leftSwap :: (a + b) * a <=> (a + b) * a
leftSwap = do
distrib      -- (a * a') + (b * a')
swapT .+ id  -- (a' * a) + (b * a')
sym distrib  -- (a' + b) * a

And the ability to extract from a coproduct:

join :: a + a ~> a
join = do
arr $do sym unite .+ sym unite -- (U * a) + (U * a) sym distrib -- (U + U) * a swapT -- a * (U + U) fstA -- a We are also provided with the ability to clone a piece of information, given by structural induction. Cloning U is trivial, and cloning a pair is just cloning its projections and then shuffling them into place. The construction of cloning a coproduct, however, is more involved: clone :: a + b ~> (a + b) * (a + b) clone = do left$ do
clone                -- (a * a) + b
first leftA          -- ((a + b) * a) + b
arr swapT            -- (a * (a + b)) + b
arr swapP              -- b + (a * (a + b))
left $do clone -- (b * b) + (a * (a + b)) first leftA -- ((b + a) * b) + (a * (a + b)) arr swapT -- (b * (b + a)) + (a * (a + b)) arr$ do
swapP                -- (a * (a + b)) + (b * (b + a))
id .+ (id .* swapP)  -- (a * (a + b)) + (b * (a + b))
sym distrib          -- (a + b) * (a + b)

It should be quite clear that this arrow language of ours is now more-or-less equivalent to some hypothetical first-order version of Haskell (like Elm?). As witnessed above, information is no longer a linear commodity. A motivated programmer could likely get work done in a 9 to 5 with what we’ve built so far. It probably wouldn’t be a lot of fun, but it’s higher level than C at the very least.

The coup de grace of Information Effects is its construction lifting our arrow language back into the isomorphism language. The trick is to carefully construct heap and garbage types to correspond exactly with what our program needs to create and erase. We can investigate this further by case analysis on the constructors of our arrow type:

Arr :: (a <=> b) -> (a ~> b)

As we’d expect, an embedding of an isomorphism in the arrow language is already reversible. However, because we need to introduce a heap and garbage anyway, we’ll use unit.

Since we can’t express the typing judgment in Haskell, we’ll use a sequent instead:

Assuming we have a way of describing this type in Haskell, all that’s left is to implement the lifting of our iso into the enriched iso language:

lift (Arr f) = id .* f

Compose :: (a ~> b) -> (b ~> c) -> (a ~> c)

Composition of arrows proceeds likewise in a rather uninteresting manner. Here, we have two pairs of heaps and garbages, results from lifting each of the arrows we’d like to compose. Because composition will run both of our arrows, we’ll need both heaps and garbages in order to implement the result. By this logic, the resulting heap and garbage types are pairs of the incoming ones.

$\frac{\lifted{f}{h_1\times a}{g_1\times b},\; \lifted{g}{h_2\times b}{g_2\times c}}{\lifted{(g \circ f)}{(h_1\times h_2)\times a}{(g_1\times g_2)\times c}}$

We can express the resulting combinator in Haskell:

lift (Compose f g) = do
id            -- (H1 * H2) * a
swapT .* id   -- (H2 * H1) * a
sym assocT    -- H2 * (H1 * a)
id .* lift f  -- H2 * (G1 * b)
assocT        -- (H2 * G1) * b
swapT .* id   -- (G1 * H2) * b
sym assocT    -- G1 * (H2 * b)
id .* lift g  -- G1 * (G2 * c)
assocT        -- (G1 * G2) * c

First :: (a ~> b) -> (a * c ~> b * c)

Lifting arrows over products again is uninteresting – since we’re doing nothing with the second projection, the only heap and garbage we have to work with are those resulting from the lifting of our arrow over the first projection.

$\frac{\lifted{f}{h\times a}{g\times b}} {\lifted{(\text{First } f)}{h\times (a\times c)}{g\times (b\times c)}}$

In Haskell, our resulting combinator looks like this:

lift (First f) = do
id          -- H * (a * c)
assocT      -- (H * a) * c
f .* id     -- (G * b) * c
sym assocT  -- G * (b * c)

Left :: (a ~> b) -> (a + c ~> b + c)

Finally, we get to an interesting case. In the execution of Left, we may or may not use the incoming heap. We also need a means of creating a b + c given a b or given a c. Recall that in our iso language, we do not have create (nor relatedly, leftA) at our disposal, and so this is a harrier problem than it sounds at first.

We can solve this problem by requiring both a b + c and a c + b from the heap. Remember that the Toffoli construction (what we’re implementing here) will create a reversible gate with additional inputs and outputs that gives the same result when all of its inputs have their default values (ie. the same as those provided by create’s semantics). This means that our incoming b + c and c + b will both be constructed with InL.

Given this, we can thus perform case analysis on the incoming a + c, and then use leftSwap from earlier to move the resulting values into their coproduct.

What does the garbage situation look like? In the case we had an incoming InL, we will have used up our function’s heap, as well as our b + c, releasing the g, b (the default value swapped out of our incoming b + c), and the unused c + b.

If an InR was input to our isomorphism, we instead emit the function’s heap h, the unused b + c, and the default c originally in the heap’s coproduct.

Our final typing judgment thus looks like this:

$\frac{\lifted{f}{h\times a}{g\times b}}{\lifted{(\text{Left f})}{h'\times (a + c)}{g' \times (b + c)}}$

$h' = h\times ((b + c) \times(c + b)) \\ g' = (g\times (b\times(c + b))) + (h\times ((b+c)\times c))$

and is rather horrifyingly implemented:

lift (Left f) = do
swapT
distrib
leftSide f .+ rightSide
sym distrib

leftSide
:: (h * a <=> g * b)
-> (a * (h * ((b + c) * (c + b))) <=> (g * (b * (c + b))) * (b + c))
leftSide f = do
swapT                -- (H * ((b + c) * (c + b))) * a
swapT .* id          -- (((b + c) * (c + b)) * H) * a
sym assocT           -- ((b + c) * (c + b)) * (H * a)
id .* f              -- ((b + c) * (c + b)) * (G * b')
swapT .* id          -- ((c + b) * (b + c)) * (G * b')
sw2                  -- ((c + b) * G) * ((b + c) * b')
id .* leftSwap       -- ((c + b) * G) * ((b' + c) * b)
swapT .* swapT       -- (G * (c + b)) * (b * (b' + c))
assocT               -- ((G * (c + b)) * b) * (b' + c)
sym assocT .* id     -- (G * ((c + b) * b)) * (b' + c)
(id .* swapT) .* id  -- (G * (b * (c + b))) * (b' + c)

rightSide :: c * (h * ((b + c) * (c + b))) <=> (h * ((b + c) * c)) * (b + c)
rightSide = do
swapT                -- c' * (H * ((b + c) * (c + b)))
assocT .* id         -- ((H * (b + c)) * (c + b)) * c'
sym assocT           -- (H * (b + c)) * ((c + b) * c')
id .* leftSwap       -- (H * (b + c)) * ((c' + b) * c)
id .* swapT          -- (H * (b + c)) * (c * (c' + b))
assocT               -- ((H * (b + c)) * c) * (c' + b)
sym assocT .* swapP  -- (H * ((b + c) * c)) * (b + c')

The home stretch is within sight. We have only two constructors of our arrow language left. We look first at Create:

Create  :: U ~> a

Because we’ve done all of this work to thread through a heap in order to give us the ability to create values, the typing judgment should come as no surprise:

$\frac{}{\lifted{\text{create}}{a\times\u}{\u\times a}}$

Our heap contains the a we want, and we drop our incoming U as garbage. The implementation of this is obvious:

lift Create = swapT

We’re left with Erase, whose type looks suspiciously like running Create in reverse:

Erase  :: a ~> U

This is no coincidence; the two operations are duals of one another.

$\frac{}{\lifted{\text{erase}}{\u\times a}{a\times\u}}$

As expected, the implementation is the same as Create:

lift Erase = swapT

And we’re done! We’ve now constructed a means of transforming any non-reversible program into a reversible one. Success!

## Summary

Still here? We’ve come a long way, which we’ll briefly summarize. In this paper, James and Sabry have taken us through the construction of a reversible language, given a proof that it’s Turing-complete, and given us some simple constructions on it. We set out on our own to implement lists and derived map for them.

We then constructed a non-reversible language (due to its capability to create and erase information), and then gave a transformation from this language to our earlier reversible language – showing that non-reversible computing is a special case of its reversible counterpart.

Information Effects ends with a short discussion of potential applications, which won’t be replicated here.

## Commentary (on the physics)

Assuming I understand the physics correctly (which I probably don’t), the fact that these reversible functions do not increase entropy implies that they should be capable of shunting information for near-zero energy. Landauer’s Principle and Szilard’s engine suggests that information entropy and thermodynamic entropy are one and the same; if we don’t increase entropy in our computation of a function, there is nowhere for us to have created any heat.

That’s pretty remarkable, if you ask me. Together with our construction from any non-reversible program to a reversible one, it suggests we should be able to cut down on our CPU power usage by a significant order of magnitudes.

## Commentary (on where to go from here)

An obvious limitation of what we’ve built here today is that it is first-order, which is to say that functions are not a first class citizen. I can think of no immediate problem with representing reversible functions in this manner. We’d need to move our (<=>) directly into the language.

id would provide introduction of this type, and (>>) (transitivity) would allow us to create useful values of the type. We’d also need a new axiom:

apply :: a * (a <=> b) <=> b * (b <=> a)

which would allow us to use our functions. We should also expect the following theorems (which may or may not be axioms) due to our iso language forming a cartesian closed category:

product   :: (a <=> (b * c)) <=> (a <=> b) * (a <=> c)

Things that we’d expect to be theorems but are not are:

terminal :: U <=> (a <=> U)
select   :: a <=> (U <=> a)
coproduct :: (a <=> (b + c)) <=> (a <=> b) + (a <=> c)

due to the symmetry of (<=>), both of these are equivalent to create and erase. I think the fact that these are not theorems despite U being the terminal object is that (<=>) requires arrows in both directions, but U only has incoming arrows.


text:
# What is the Easiest way to Animate the rigid body properties of a large group of objects

I would like to animate 500 or so shards to be "animated" rigid body at frame zero and "dynamic" at frame 550. Do I really have to set a keyframe for each individual object or is there a way to animate that rigid body property as a group? The shards are in a group, but it appears that the rigid body for a group of objects can only be set, not animated. I've tried using an empty parent object to no avail.

[Select the rigid body object and copy their properties (except for animated).]

1. Select all rigid body object to be modified.
2. Alt click on the Animated property. This will change the property for all the selected object to the same value. Now all object have animated enabled.
3. Use this script to key the property on all of them.
import bpy
sel = bpy.context.selected_objects
for ob in sel:
ob.rigid_body.keyframe_insert(data_path="enabled")
ob.rigid_body.keyframe_insert(data_path="kinematic")

Now all objects are keyed.

To remove all Animated keys on a frame, execute the script but replace keyframe_insert with keyframe_delete.

• Thank you so much, Leander. Please add the following line to your script, and then I will mark your answer as 100% helpful by clicking the checkmark: ob.rigid_body.keyframe_insert(data_path="enabled") – silvermanj7 May 3 '18 at 15:42
• @silvermanj7 You're welcome, I have edited the line, feel free to edit it yourself, if I misunderstood – Leander May 3 '18 at 15:44
• oh i didn't realize i had the power. thanks again. :)) – silvermanj7 May 3 '18 at 16:10


text:
Heaviside function

The Heaviside function is the D218: Basic boolean function $$\mathbb{R} \to \{ 0, 1 \}, \quad x \mapsto \begin{cases} 1, \quad & x \geq 0 \\ 0, \quad & x < 0 \end{cases}$$

The Heaviside function is the D218: Basic boolean function $$\mathbb{R} \to \{ 0, 1 \}, \quad x \mapsto I_{[0, \infty)}(x)$$
Also known as
Heaviside step function


text:
## The Annals of Statistics

### Robust Regression: Asymptotics, Conjectures and Monte Carlo

Peter J. Huber

#### Abstract

Maximum likelihood type robust estimates of regression are defined and their asymptotic properties are investigated both theoretically and empirically. Perhaps the most important new feature is that the number $p$ of parameters is allowed to increase with the number $n$ of observations. The initial terms of a formal power series expansion (essentially in powers of $p/n$) show an excellent agreement with Monte Carlo results, in most cases down to 4 observations per parameter.

#### Article information

Source
Ann. Statist. Volume 1, Number 5 (1973), 799-821.

Dates
First available in Project Euclid: 12 April 2007

Permanent link to this document
http://projecteuclid.org/euclid.aos/1176342503

Digital Object Identifier
doi:10.1214/aos/1176342503

Mathematical Reviews number (MathSciNet)
MR356373

Zentralblatt MATH identifier
0289.62033

JSTOR
links.jstor.org

#### Citation

Huber, Peter J. Robust Regression: Asymptotics, Conjectures and Monte Carlo. Ann. Statist. 1 (1973), no. 5, 799--821. doi:10.1214/aos/1176342503. http://projecteuclid.org/euclid.aos/1176342503.


text:
## Dynamics of threshold solutions for energy-critical wave equation.(English)Zbl 1159.35043

The initial value problem to the equation $$u_{tt}-\Delta u-\left| u\right| ^{\frac{4}{n-2}}u=0$$ for the dimensions $$n=3,4,5$$ is treated. The authors give a classification of the solutions, not necessarily radial, with critical energy corresponding the energy of the stationary solution. The existence of two special radial solutions connecting different behavior for negative and positive times is proved.

### MSC:

 35L70 Second-order nonlinear hyperbolic equations 35B40 Asymptotic behavior of solutions to PDEs 35L15 Initial value problems for second-order hyperbolic equations
Full Text:


text:
A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 7 Issue 6
Oct.  2020

IEEE/CAA Journal of Automatica Sinica

• JCR Impact Factor: 6.171, Top 11% (SCI Q1)
CiteScore: 11.2, Top 5% (Q1)
Google Scholar h5-index: 51， TOP 8
Turn off MathJax
Article Contents
Yantao Tian, Xuanhao Cao, Xiaoyu Wang and Yanbo Zhao, "Four Wheel Independent Drive Electric Vehicle Lateral Stability Control Strategy," IEEE/CAA J. Autom. Sinica, vol. 7, no. 6, pp. 1542-1554, Nov. 2020. doi: 10.1109/JAS.2019.1911729
 Citation: Yantao Tian, Xuanhao Cao, Xiaoyu Wang and Yanbo Zhao, "Four Wheel Independent Drive Electric Vehicle Lateral Stability Control Strategy," IEEE/CAA J. Autom. Sinica, vol. 7, no. 6, pp. 1542-1554, Nov. 2020.

# Four Wheel Independent Drive Electric Vehicle Lateral Stability Control Strategy

##### doi: 10.1109/JAS.2019.1911729
Funds:  This work was supported by the National Nature Science Foundation (U1664263), and National Key R&D Program of China (2016YFB0101102)
• In this paper, a kind of lateral stability control strategy is put forward about the four wheel independent drive electric vehicle. The design of control system adopts hierarchical structure. Unlike the previous control strategy, this paper introduces a method which is the combination of sliding mode control and optimal allocation algorithm. According to the driver’s operation commands (steering angle and speed), the steady state responses of the sideslip angle and yaw rate are obtained. Based on this, the reference model is built. Upper controller adopts the sliding mode control principle to obtain the desired yawing moment demand. Lower controller is designed to satisfy the desired yawing moment demand by optimal allocation of the tire longitudinal forces. Firstly, the optimization goal is built to minimize the actuator cost. Secondly, the weighted least-square method is used to design the tire longitudinal forces optimization distribution strategy under the constraint conditions of actuator and the friction oval. Beyond that, when the optimal allocation algorithm is not applied, a method of axial load ratio distribution is adopted. Finally, CarSim associated with Simulink simulation experiments are designed under the conditions of different velocities and different pavements. The simulation results show that the control strategy designed in this paper has a good following effect comparing with the reference model and the sideslip angle $\,\beta$ is controlled within a small rang at the same time. Beyond that, based on the optimal distribution mode, the electromagnetic torque phase of each wheel can follow the trend of the vertical force of the tire, which shows the effectiveness of the optimal distribution algorithm.

•  [1] F.-Y. Wang, N. N. Zheng, D. P. Cao, C. M. Martinez, L. Li, and T. Liu, “Parallel driving in CPSS: A unified approach for transport automation and vehicle intelligence,” IEEE/CAA J. Autom. Sinica, vol. 4, no. 4, pp. 577–587, Sept. 2017. [2] C. Lv, D. P. Cao, Y. F. Zhao, D. J. Auger, M. Sullman, H. J. Wang, L. M. Dutka, L. Skrypchuk, and A. Mouzakitis, “Analysis of autopilot disengagements occurring during autonomous vehicle testing,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 58–68, Jan. 2018. [3] C. Lv, X. S. Hu, A. Sangiovanni-Vincentelli, Y. T. Li, C. M. Martinez, and D. P. Cao, “Driving-style-based codesign optimization of an automated electric vehicle: A cyber-physical system approach,” IEEE Trans. Ind. Electron., vol. 66, no. 4, pp. 2965–2975, Apr. 2019. [4] C. Lv, Y. H. Liu, X. S. Hu, H. Y. Guo, D. P. Cao, and F.-Y. Wang, “Simultaneous observation of hybrid states for cyber-physical systems: A case study of electric vehicle powertrain,” IEEE Trans. Cybernet., vol. 48, no. 8, pp. 2357–2367, Aug. 2018. [5] C. Lv, Y. Xing, C. Lu, Y. H. Liu, H. Y. Guo, H. B. Gao, and D. P. Cao, “Hybrid-learning-based classification and quantitative inference of driver braking intensity of an electrified vehicle,” IEEE Trans. Veh. Technol., vol. 67, no. 7, pp. 5718–5729, Jul. 2018. [6] D. Kim, S. Hwang, and H. Kim, “Vehicle stability enhancement of four-wheel-drive hybrid electric vehicle using rear motor control,” IEEE Trans. Veh. Technol., vol. 57, no. 2, pp. 727–735, Mar. 2008. [7] X. Y. Huang, H. Zhang, G. G. Zhang, et al., “Robust weighted gain-scheduling H ∞ vehicle lateral motion control with considerations of steering system backlash-type hysteresis,” IEEE Trans. Control Systems Technology, vol. 22, no. 5, pp. 1740–1753, Sept. 2014. [8] C. Zhou and J. Xiao, “Improved strong track filter and its application to vehicle state estimation,” Acta Autom. Sinica, vol. 38, no. 9, pp. 1520–1527, Sept. 2012. [9] K. Tabti, M. Bourahla, and L. Mostefai, “Hybrid control of electric vehicle lateral dynamics stabilization,” J. Electr. Eng., vol. 64, no. 1, pp. 50–54, Mar. 2013. [10] H. Ohara and T. Murakami, “A stability control by active angle control of front-wheel in a vehicle system,” IEEE Trans. Ind. Electron., vol. 55, no. 3, pp. 1277–1285, Mar. 2008. [11] M. Canale, L. Fagiano, A. Ferrara, and C. Vecchio, “Vehicle yaw control via second-order sliding-mode technique,” IEEE Trans. Ind. Electron., vol. 55, no. 11, pp. 3908–3916, Nov. 2008. [12] M. H. B. Peeie, “Skid control of small electric vehicles (direct yaw moment control using tire steer angle),” Proc. Schl. Eng. Tokai Univ. Ser. E, vol. 39, no. 11, pp. 73–80, Nov. 2014. [13] A. Nasri, B. Gasbaoui, and B. M. Fayssal, “Sliding mode control for four wheels electric vehicle drive,” Procedia Technol., vol. 22, pp. 518–526, Jan. 2016. [14] K. Nam, H. Fujimoto, and Y. Hori, “Lateral stability control of in-wheel-motor-driven electric vehicles based on sideslip angle estimation using lateral tire force sensors,” IEEE Trans. Veh. Technol., vol. 61, no. 5, pp. 1972–1985, Jun. 2012. [15] A. Nahidi, A. Kasaiezadeh, S. Khosravani, A. Khajepour, S. K. Chen, and B. Litkouhi, “Modular integrated longitudinal and lateral vehicle stability control for electric vehicles,” Mechatronics, vol. 44, pp. 60–70, Jun. 2017. [16] L. J. Zhang, J. Sun, and G. Orosz, “Hierarchical design of connected cruise control in the presence of information delays and uncertain vehicle dynamics,” IEEE Trans. Control Syst. Technol., vol. 26, no. 1, pp. 139–150, Jan. 2018. [17] Y. Q. Xia, F. Pu, S. F. Li, and Y. Gao, “Lateral path tracking control of autonomous land vehicle based on ADRC and differential flatness,” IEEE Trans. Ind. Electron., vol. 63, no. 5, pp. 3091–3099, May 2016. [18] S. Khosravani, M. Jalali, A. Khajepour, A. Kasaiezadeh, S. K. Chen, and B. Litkouhi, “Application of lexicographic optimization method to integrated vehicle control systems,” IEEE Trans. Ind. Electron., vol. 65, no. 12, pp. 9677–9686, Dec. 2018. [19] R. C. Rafaila, C. F. Caruntu, and G. Livint, “Nonlinear model predictive control using lyapunov functions for vehicle lateral dynamics,” IFAC-Papersonline, vol. 49, no. 3, pp. 135–140, Jul. 2016. [20] Y. Yamaguchi and T. Murakami, “Adaptive control for virtual steering characteristics on electric vehicle using steer-by-wire system,” IEEE Trans. Ind. Electron., vol. 56, no. 5, pp. 1585–1594, May 2009. [21] C. Geng, L. Mostefai, M. Denai, and Y. Hori, “Direct yaw-moment control of an in-wheel-motored electric vehicle based on body slip angle fuzzy observer,” IEEE Trans. Ind. Electron., vol. 56, no. 5, pp. 1411–1419, May 2009. [22] H. Imine, N. K. M’Sirdi, and Y. Delanne, “Sliding-mode observers for systems with unknown inputs: Application to estimating the road profile,” Proc. Inst. Mech. Eng.,Part D:J. Autom. Eng., vol. 219, no. 8, pp. 989–997, Aug. 2005. [23] H. B. Pacejka, Tire and Vehicle Dynamics. 3rd ed. Oxford, UK: Butterworth-Heinemann, 2012. [24] J. Ahmadi, A. K. Sedigh, and M. Kabganian, “Adaptive vehicle lateral-plane motion control using optimal tire friction forces with saturation limits consideration,” IEEE Trans. Veh. Technol., vol. 58, no. 8, pp. 4098–4107, Oct. 2009. [25] R. Rajamani, Vehicle Dynamics and Control. Austin, US: Springer, 2006. [26] S. H. Ding, L. Liu, and W. X. Zheng, “Sliding mode direct yaw-moment control design for in-wheel electric vehicles,” IEEE Trans. Ind. Electron., vol. 64, no. 8, pp. 6752–6762, Aug. 2017. [27] L. Zhai, T. M. Sun, and J. Wang, “Electronic stability control based on motor driving and braking torque distribution for a four in-wheel motor drive electric vehicle,” IEEE Trans. Veh. Technol., vol. 65, no. 6, pp. 4726–4739, Jun. 2016. [28] O. Mokhiamar and M. Abe, “Simultaneous optimal distribution of lateral and longitudinal tire forces for the model following control,” J. Dyn. Syst.,Meas.,Control, vol. 126, no. 4, pp. 753–763, Dec. 2004. [29] B. X. Duan, “Study on electronic stability control of in-wheel motor EV,” M.S. thesis, Jilin Univ., Changchun, China, 2013.

### Catalog

###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

Figures(12)  / Tables(2)