text:
Yet another HP simulator (using C + X11)
12-02-2021, 10:18 AM
Post: #21
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-02-2021 01:07 AM)cdmackay Wrote:  But the real problem was that many mouse-clicks on the keys are missed. More than half.

Not sure why that is - I frequently use a remote desktop with my headless Raspberry Pi and haven't seen that problem. Are you using X over SSH? (I just enable XDMCP on my LAN and use Xephyr to connect. If someone can sniff those packets I've got bigger problems to worry about than un-encrypted network traffic!).

You can't (yet) easily change the font size but you can make the window bigger by modifying the following lines in x11-calc.h. I added this feature so I could resize the windows to fit the display when using one of the Pi touch screens. If you want to mess with the font _names_ they are defined in x11-calc-font.h.

Code:
 #define SCALE_WIDTH     1 #define SCALE_HEIGHT    1

Nice to know to compiles with unstable!

I'm not sure how things work on a MacOS but if you have the X headers installed you should be able to compile it natively..

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
12-03-2021, 01:00 AM
Post: #22
 cdmackay Senior Member Posts: 634 Joined: Sep 2018
RE: Yet another HP simulator (using C + X11)
thanks! Yes, X over ssh; my server doesn't allow any other sort of login.

I'll give those compiles a try, thanks again.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 32SII 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
12-25-2021, 12:00 PM (This post was last modified: 12-26-2021 04:21 PM by Mike T..)
Post: #23
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
Quite a lot more work needed (as the classic machines have slightly different opcodes) but I was wondering what the HP45 fans make of this:

Note: CLX button is pressed in this screen shot.

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
12-25-2021, 12:41 PM
Post: #24
 rprosperi Senior Member Posts: 5,069 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
Looks good!
Seems to answer the question: What would an HP-45 look like if it were a Woodstock?

--Bob Prosperi
12-25-2021, 01:07 PM
Post: #25
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-25-2021 12:41 PM)rprosperi Wrote:  Looks good!
Seems to answer the question: What would an HP-45 look like if it were a Woodstock?

Actually I hope it looks more like an HP45 as I spent yesterday evening redesigning the buttons to try and match the original...

Perhaps I should make the background darker.

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
12-26-2021, 03:43 AM
Post: #26
 rprosperi Senior Member Posts: 5,069 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-25-2021 01:07 PM)Mike T. Wrote:
(12-25-2021 12:41 PM)rprosperi Wrote:  Looks good!
Seems to answer the question: What would an HP-45 look like if it were a Woodstock?

Actually I hope it looks more like an HP45 as I spent yesterday evening redesigning the buttons to try and match the original...

Perhaps I should make the background darker.

For a real 45-like appearance, I suggest these tweaks:

-Smaller buttons with more space between them

-The 4 math operator keys should be half-width (nearly square)

-In several places "-" should be arrow keys, "->"

-y^x, e^x and 10^x powers should be higher

-Label for [shift] [Rv] should have a bar above the x

With such changes, it will be much closed to real 45 in appearance.

--Bob Prosperi
12-26-2021, 12:52 PM
Post: #27
 Thomas Okken Senior Member Posts: 1,472 Joined: Feb 2014
RE: Yet another HP simulator (using C + X11)
(12-02-2021 10:18 AM)Mike T. Wrote:
(12-02-2021 01:07 AM)cdmackay Wrote:  But the real problem was that many mouse-clicks on the keys are missed. More than half.

Not sure why that is - I frequently use a remote desktop with my headless Raspberry Pi and haven't seen that problem. Are you using X over SSH? (I just enable XDMCP on my LAN and use Xephyr to connect. If someone can sniff those packets I've got bigger problems to worry about than un-encrypted network traffic!).

I just tried building and running the latest from GitHub in a VM running Ubuntu 14.04, and I found that it was dropping mouse events as well, and also just being unbearably sluggish overall. I noticed that while the app was running, compiz was running at over 100% CPU, and xorg was using another 40% or so. Compiz pegging a core could explain the dropped events.

Note that this version does include the -std=gnu99 option that was mentioned earlier... it also includes -no-pie in src/makefile, which I had to remove because it was not recognized, and causing compilation to fail.
12-26-2021, 04:13 PM
Post: #28
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-26-2021 12:52 PM)Thomas Okken Wrote:  I just tried building and running the latest from GitHub in a VM running Ubuntu 14.04, and I found that it was dropping mouse events as well, and also just being unbearably sluggish overall. I noticed that while the app was running, compiz was running at over 100% CPU, and xorg was using another 40% or so. Compiz pegging a core could explain the dropped events.

Note that this version does include the -std=gnu99 option that was mentioned earlier... it also includes -no-pie in src/makefile, which I had to remove because it was not recognized, and causing compilation to fail.

Thomas,

If would he helpful to know what VM host you have and which desktop you were using?

Was the simulator using 100% CPU all the time? If it was then that suggests that it is using a default busy loop rather then an dependent sleep() function.

If you send me a private message with the output of 'dpkg --get-selections' that would be useful (alternatively create an issue on github https://github.com/mike632t/x11-calc/blo...em-reports and attach it there). I'll see if I can set up an Ubuntu 14.04 VM in the meantime.

Having seen a similar issue on the Raspberry Pi there I suspect there may be a problem drawing the X11 primitives when hardware acceleration is enabled. It is worth trying to reproduce the problem but I'm not sure I can do much about it!

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
12-26-2021, 04:32 PM (This post was last modified: 12-26-2021 04:34 PM by Mike T..)
Post: #29
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-26-2021 03:43 AM)rprosperi Wrote:
(12-25-2021 01:07 PM)Mike T. Wrote:  Actually I hope it looks more like an HP45 as I spent yesterday evening redesigning the buttons to try and match the original...

Perhaps I should make the background darker.

For a real 45-like appearance, I suggest these tweaks:

-Smaller buttons with more space between them

-The 4 math operator keys should be half-width (nearly square)

-In several places "-" should be arrow keys, "->"

-y^x, e^x and 10^x powers should be higher

-Label for [shift] [Rv] should have a bar above the x

With such changes, it will be much closed to real 45 in appearance.

Unfortunately I really can't do a lot about the text without a custom font (I know there is a suitable true fype font somewhere but I can't use it as I can only use an X11 bitmap font).

I've made the math function keys narrower, but left the others unchanged to keep the buttons as big as possible so they are easier to use with a touch screen.

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
12-26-2021, 07:07 PM
Post: #30
 Thomas Okken Senior Member Posts: 1,472 Joined: Feb 2014
RE: Yet another HP simulator (using C + X11)
(12-26-2021 04:13 PM)Mike T. Wrote:  If would he helpful to know what VM host you have and which desktop you were using?

The VM host is VirtualBox 6.1.29 r148218 running under the latest MacOS;
the desktop is GNOME 3 with Xorg (no Wayland).

(12-26-2021 04:13 PM)Mike T. Wrote:  Was the simulator using 100% CPU all the time? If it was then that suggests that it is using a default busy loop rather then an dependent sleep() function.

Pretty much, yes, but note that it's not the simulator itself that's using all that CPU time:

Code:
top - 20:01:47 up 10 min,  3 users,  load average: 1.02, 0.61, 0.38 Tasks: 203 total,   2 running, 201 sleeping,   0 stopped,   0 zombie %Cpu(s): 62.3 us, 14.9 sy,  0.0 ni, 22.6 id,  0.0 wa,  0.0 hi,  0.2 si,  0.0 st KiB Mem:   2048144 total,  1580932 used,   467212 free,    19440 buffers KiB Swap:  2095100 total,     7652 used,  2087448 free.   450480 cached Mem   PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                           2051 thomas    20   0 1638940 276124  67544 R 116.3 13.5   2:31.84 compiz                                                            1019 root      20   0  373216  84776  30160 S  33.2  4.1   0:56.02 Xorg                                                              3318 thomas    20   0   22340   2944   2620 S   2.3  0.1   0:01.28 x11-calc-67                                                       2281 thomas    20   0 1619444 201468 112084 S   0.7  9.8   0:17.05 Web Content                                                       2348 thomas    20   0 1839656 243068  82820 S   0.7 11.9   0:15.93 WebExtensions                                                        7 root      20   0       0      0      0 S   0.3  0.0   0:00.68 rcu_sched                                                          144 root       0 -20       0      0      0 S   0.3  0.0   0:00.01 kworker/1:1H                                                      1734 thomas    20   0  182964   2832   2484 S   0.3  0.1   0:01.25 VBoxClient                                                        2558 thomas    20   0  659576  30608  22332 S   0.3  1.5   0:01.39 gnome-terminal                                                    3331 thomas    20   0   29168   3128   2576 R   0.3  0.2   0:00.11 top

(12-26-2021 04:13 PM)Mike T. Wrote:  If you send me a private message with the output of 'dpkg --get-selections' that would be useful (alternatively create an issue on github https://github.com/mike632t/x11-calc/blo...em-reports and attach it there).

Will do, you should be getting it shortly.
12-27-2021, 12:12 AM
Post: #31
 Mike T. Member Posts: 66 Joined: Dec 2013
RE: Yet another HP simulator (using C + X11)
(12-26-2021 07:07 PM)Thomas Okken Wrote:  Pretty much, yes, but note that it's not the simulator itself that's using all that CPU time:

Code:
top - 20:01:47 up 10 min,  3 users,  load average: 1.02, 0.61, 0.38 Tasks: 203 total,   2 running, 201 sleeping,   0 stopped,   0 zombie %Cpu(s): 62.3 us, 14.9 sy,  0.0 ni, 22.6 id,  0.0 wa,  0.0 hi,  0.2 si,  0.0 st KiB Mem:   2048144 total,  1580932 used,   467212 free,    19440 buffers KiB Swap:  2095100 total,     7652 used,  2087448 free.   450480 cached Mem   PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                           2051 thomas    20   0 1638940 276124  67544 R 116.3 13.5   2:31.84 compiz                                                            1019 root      20   0  373216  84776  30160 S  33.2  4.1   0:56.02 Xorg                                                              3318 thomas    20   0   22340   2944   2620 S   2.3  0.1   0:01.28 x11-calc-67                                                       2281 thomas    20   0 1619444 201468 112084 S   0.7  9.8   0:17.05 Web Content                                                       2348 thomas    20   0 1839656 243068  82820 S   0.7 11.9   0:15.93 WebExtensions                                                        7 root      20   0       0      0      0 S   0.3  0.0   0:00.68 rcu_sched                                                          144 root       0 -20       0      0      0 S   0.3  0.0   0:00.01 kworker/1:1H                                                      1734 thomas    20   0  182964   2832   2484 S   0.3  0.1   0:01.25 VBoxClient                                                        2558 thomas    20   0  659576  30608  22332 S   0.3  1.5   0:01.39 gnome-terminal                                                    3331 thomas    20   0   29168   3128   2576 R   0.3  0.2   0:00.11 top

The good news is that it isn't the busy loop issue (so the compiler is behaving itself), but I have no idea why compiz is taking so much CPU. I'm not a MAC user but I'll see if I can reproduce the problem in QEMU on Debian...

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)


text:
# Algebraic Identities for RMO and IITJEE Mathematics

Below is a list of algebraic identities, which beckon a serious student of RMO or IITJEE mathematics. See if you can prove all of them. The expressions given below are symmetric and/or cyclic and/or alternating. Refer to Higher Algebra of Bernard Child if you want to refresh your theory.

1. $(b-c)+(c-a)+(a-b)=0$
2. $a(b-c)+b(c-a)+c(a-b)=0$
3. $a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)=-(b-c)(c-a)(a-b)$
4. $bc(b-c)+ca(c-a)+ab(a-b)=-(b-c)(c-a)(a-b)$
5. $a(b^{2}-c^{2})+b(c^{2}-a^{2})+c(a^{2}-b^{2})=(b-c)(c-a)(a-b)$
6. $a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)=-(b-c)(c-a)(a-b)(a+b+c)$
7. $(a+b+c)(bc+ca+ab)=a(b^{2}+c^{2})+b(c^{2}+a^{2})+c(a^{2}+b^{2})+3abc$
8. $(b+c)(c+a)(a+b)=a(b^{2}+c^{2})+b(c^{2}+a^{2})+c(a^{2}+b^{2})+2abc$
9. $a^{3}+b^{3}+c^{3}-3abc=(a+b+c)(a^{2}+b^{2}+c^{2}-bc-ca-ab)$
10. $(b-c)^{2}+(c-a)^{2}+(a-b)^{2}=2(a^{2}+b^{2}+c^{2}-ab-bc-ca)$
11. $(a+b+c)(b+c-a)(c+a-b)(a+b-c)$ which equals

$-a^{4}-b^{4}-c^{4}+2b^{2}c^{2}+2c^{2}a^{2}+2a^{2}b^{2}$

If you have trouble proving them using the theory of symmetric/alternating expressions as elucidated in Higher Algebra of Bernard Child, please write to me and I will share my proofs with you.

A word of caution: Just because some of the expressions are simple for you to handle by brute force, please do not do so. The idea of this exercise is to underline the power of theory of symmetric expressions. I will show  you more powerful examples later.

Nalin Pithwa

## One thought on “Algebraic Identities for RMO and IITJEE Mathematics”

This site uses Akismet to reduce spam. Learn how your comment data is processed.

format: plain


text:
Uniform LBP Features and Spatial Histogram Computation

Introduction

In the earlier article we had seen that we had computed a LBP image.Each pixel in this image still can take $2^8$ possible values. The idea of uniform LBP is to perform lossy encoding so that we eliminate some irrelevant data and retain useful information which takes on 58 possible values. In this article we will look at Uniform LBP and computation of Spatial Histogram of LBP which can be used as a feature for image description.
• Uniform LBP features are considered as one which have only 2 contigious regions corresponding to 0's and 1's,while non uniform LBP have more than 1 contigious regions corresponding to 0's and 1's.
• This we need a mapping from which assign each on $2^8$ possible codes to one of 58 encoded uniform LBP values.
• All the non uniform codes are assigned to a single values.
• The uniform LBP's can be viewed as corners,line,ramp gradient
• The non uniform LBP's are assumed to be irrelevant and can be ignored.
• A uniform binary pattern can be identified by performing a bit wise traversal and checking if number of bit transitions are atmost 2 .
• This is done by first circular right/left shifting the given code and performing XOR operation with the original code.
• Since we need to only consider 8 bit numbers ,we need perform circular shift and masking MSB for integers.
• Now number of bit operations is simply the number of set bits in the result
• The code for this can be as follows
• the method to count bits is naive way and since we are using 8 bit words,it will take 8 iterations of the for loop.
• Brian Kernighan's method performs this by going through as many iterations as set bits
• The result can be precomputed for possible input code to determine if a LBP is a uniform code or not.
• The next task is to map the LBP codes to one of 58 uniform codes.
• The encoding will be done along the rows as per the below figure
• Since we known the possible input codes before hand,we can prepare a lookup table before hand to check if a uniform code or not
• Now if it is a uniform code we need to map it to one of possible 58 codes.
• To do this we move from all numbers from $0-2^8$,check if they are uniform and assign them to a one of 58 possible code.
• However we can see than
• Thus we modify the existing lbp image code to return only uniform lbp coded as destination lbp image by performing a simple lookup operations.
• Now next task is to compute a spatial histogram,the histogram may be computed over the entire image or dividing the image into grids
• The LBP spatial histogram can be used as a texture descriptor.
• However the LBP image is a gradient image in some sense,it encode information about different types of gradiants
• The LBP pattern can be used to identify isolated corners or flat region ( all 0 or 1)
• The LBP pattern can be used to identify corner a continuous run of 0 or 1 of length (5-8 and its rotated version)
• The LBP pattern can be used to identify a edge a continous run of 0 or 1(length 4 and rotated version )
• The LBP pattern can be used to identify horizontal or vertical edge ( vertical/horizontal run of 0 and 1 )
• The LBP pattern can be used to identify a line end (1000000 and its rotated version)
• The LBP pattern with 2 continuous 1'2 can be considered as a horizontal or vertical line

Code

• The code for the same can be found at git rep https://github.com/pi19404/OpenVision/ in ImgFeatures/lbpfeatures.cpp and ImgFeatures/lbpfeatures.hpp files.

References

• Description of interest regions with local binary patterns by Heikkil,Pietikֳ & Schmid
• Rotation invariant image description with local binary pattern histogram fourier features. by Ahonen T. and Matas J. and He C & Pietikֳinen M.
• Multiresolution gray-scale and rotation invariant texture classification with Local Binary Patterns by Ojala


text:
# Contradiction/breach 2nd law? Simply with carnot engine + negative temperature

1. Sep 19, 2010

### nonequilibrium

Hello,

For a reversible heat engine between temperatures $$T_1$$ and $$T_2$$, the ratio of heat going in and out the engine is $$\frac{Q_1}{Q_2} = \frac{T_1}{T_2}$$ (second law).

Say $$T_1 = 200 K$$ and $$T_2 = 273 K$$, then heat goes from 2 to 1 and as we can see, the ratio of heat that goes in the engine is indeed bigger than what comes out ( = logical, due to delivery of work).

Take two ideal paramagnets, each at a negative temperature (note: negative temperature > positive temperature; the scale goes $$0 \to \infty \to - \infty \to 0$$).

Now say $$T_1 = -200 K$$ and $$T_2 = -273 K$$, then heat will go from 1 to 2 (Because the entropy of paramagnetic reservoir 1 will raise more than the drop in that of paramagnetic reservoir 2). The ratio of heat going in and out hasn't changed due to the minus cancelling in top and bottom. This says that the heat going in from 1 into the engine is less than the heat deposited from the engine into 2.

What's the explanation?

2. Sep 19, 2010

### Staff: Mentor

You cannot have a negative temperature on the Kelvin scale. 0 is absolute zero, you cannot get any colder than that.

3. Sep 19, 2010

### nonequilibrium

:( You missed my point completely, did you even read my post? I said negative temperature is even hotter than any positive temperature!

4. Sep 19, 2010

### Staff: Mentor

What does that even mean? How can a negative temperature be hotter than a positive temp?

5. Sep 19, 2010

### Pythagorean

Abstract math is not physics

6. Sep 19, 2010

### nonequilibrium

That if it's placed in contact with any system with a postive temperature, heat will flow from the negative to the positive system.

EDIT: (to pythagorean) What do you mean? With what part do you not agree? Please don't interpret me as somebody who is saying "the 2nd law is false"; of course not. I'm just trying to interpret the above. The two two things that seem contradictory to me: 1) the ratio of heat directly derived from the 2nd law; 2) heat flow for idealized paramagnets.

7. Sep 19, 2010

### Pythagorean

Kelvin is bound between 0 and a finite number because it's based on energy. You can't have negative energy and you can't have infinite energy.

8. Sep 19, 2010

### Pythagorean

This is the faulty application of abstract math that I'm referring to:

.

9. Sep 19, 2010

### Staff: Mentor

Why would heat flow from a lower temperature to a higher temperature? Or does this go back to saying that the negative temperature has more heat than the positive temperature?

10. Sep 20, 2010

### Gerenuk

Please excuse the ignorance of the previous posters. They really should read up some concepts beyond the very basics before they complain.

I haven't thought too much, but my first guess is that you are completely right, but there is no problem. In one case work goes in for a reversible operation and in the other case work goes out. Is that a problem?

11. Sep 20, 2010

### Staff: Mentor

Negative temperatures are only defined for systems with a limited number of energy states. I am not sure that the derivation for the equation of the heat engine is valid for such a system. I would think you would need to work this with statistical mechanics.

12. Sep 20, 2010

### Gerenuk

I think the equation still works for reversible processes in any system. What about my proposal that indeed there is a difference, but it's not a problem?

13. Sep 20, 2010

### Staff: Mentor

I suspect (just a guess really) that is correct, but I would have to actually work through the derivation of the heat engine for a negative temperature system before I would feel comfortable making that assertion.

14. Sep 20, 2010

### nonequilibrium

Hello, thank you for the replies.

Gerenuk, I'm not sure how it would not be a problem? If $$T_1 = -200K$$ and $$T_2 = -273K$$, then heat will flow (if allowed...) spontaneously from system 1 to system 2, we all agree on that. This means I can put in an engine with system 1 acting as the hot reservoir and 2 as the cold reservoir, where $$W > 0$$. Obviously the heat coming out of 1 must thus be greater than the heat going into 2, if work is delivered, yet the reversible equation $$\Delta S_{universe} = - \frac{Q_1}{T_1} + \frac{Q_2}{T_2} = 0$$ implies this is not the case (if you're wondering about the signs: the first term in its totality presents the entropy GAIN in the first system, so since the temperature is negative, I had to add a minus [N.B.: all $$Q$$ symbols are taken as absolute values]; reverse the situation for system 2).

DaleSpam, fair point! So you can't actually make them reservoirs without destroying their weird behavior, but okay, let's imagine the two pseudo-reservoirs really big and only a small engine in between. The equation $$\Delta S_{universe} = - \frac{Q_1}{T_1} + \frac{Q_2}{T_2} = 0$$ won't be exact anymore, but we can approach zero as close as we want, and then even for finite reservoirs we'll get the weird situation where the heat deposited is greater than the heat absorped, although work was delivered...

Really weird situation, cause it's such a simple set-up, but I can't pinpoint where it goes wrong...

15. Sep 20, 2010

### Gerenuk

Why should work be delivered? The only constraint is that it is reversible. But maybe this transfer actually requires heat?
Just a random thought.... not sure.

16. Sep 20, 2010

### nonequilibrium

Okay, let's do the following thought experiment:

Q_h is the heat going from 1 into the engine, Q_c is the heat going from the engine into 2. Now let's presume the engine USES work W as to fix our anomaly. Then Q_h + W = Q_c. Now stop the engine. Call the state of the universe we have now A. Now reverse the engine: now we get out W and Q_c leaves 2 and Q_h goes into 1, okay. Now as we know: heat can spontaneously flow from 1 to 2, so let the Q_h flow back spontaneously into 2. Stop. Call this state B. Now if you've followed closely, the net result of going from A to B: heat has been taken out of 2 and work has been delivered without any other effect in the universe.

The Kelvin-Planck statement says "It is impossible to convert heat completely into work in a cyclic process." We have just breached this in our thought experiment, thus W must be going out instead of in.

Or the summary of this post for the lazy ones: if it costs work rather than gives work, we'd directly be breaching the kelvin-planck version of the 2nd law.

17. Sep 20, 2010

### JaredJames

How do you achieve a negative temperature (-K)?

The results from putting a negative Kelvin figure into this equation are no different to a person accidentally putting the Celsius value in (when negative). Putting the Celsius value into this equation doesn't work.

Just because you can put other values in (particularly Celsius as they can be equal to the Kelvin Value - 0C = 273K etc and this is a common mistake) doesn't make the result that comes out correct.

You can prove any law of physics wrong if you invent values to go into it, but unless you can prove the existence of negative temperatures (below 0K - or negative energy), I think you're breaching PF guidelines.

Or am I just totally missing the point here?

Last edited: Sep 20, 2010
18. Sep 20, 2010

### Staff: Mentor

19. Sep 20, 2010

### nonequilibrium

jarednjames: Indeed you're missing the point, as you say yourself, but I don't mean that impolitely: I'd also be very skeptical if I hadn't heard of statistical mechanics before. The main difference between the temperature you're used to is that this temperature's no longer a degree for kinetic energy, but something more general (still dependent on the concept of energy). The important thing is that the equation I use is not dependent on the kinetic energy temperature and should also be applicable to the general situation, or at least I thought so. The conclusion seems to be that $$\Delta S = \int \frac{dQ_{rev}}{T}$$ does not work in general?

20. Sep 20, 2010

### JaredJames

So does this have a basis in real life? Is it useful or just some piece of maths that shows A but we can only achieve B due to the laws of physics?

"By the definition of temperature such a system has a negative temperature."

Does the temperature actually drop below 0K or is it purely showing it as a negative temperature (in reality, the temperature is +K (any positive temperature) but due to the maths it comes out as negative)?


text:
# Proportional approval voting

Proportional approval voting (PAV) is a proportional electoral system for selecting committees. It is an extension of the D'Hondt method of apportionment[1][2] that additionally allows for personal votes (voters vote for candidates, not for a party list). The voters vote via approval ballots where each voter marks those candidates that the voter finds acceptable.

## History

The system was first proposed by Thorvald N. Thiele.[3][4][5] It was used in combination with ranked voting in the early 20th century in Sweden, for example between 1909 and 1921 for distributing seats within parties, and in local elections.[4] After 1921 it was replaced by Phragmén's rules. PAV was rediscovered by Forest Simmons in 2001[6] who gave it the name "proportional approval voting".

## Definition

PAV selects a committee of a fixed desired size with the highest score, where scores are calculated according to the following formula. Given a committee ${\displaystyle W}$, for each voter we check how many candidates in the committee the voter approves. Assuming that the voter voted for ${\displaystyle r}$ candidates in ${\displaystyle W}$, the voter contributes to the score of ${\displaystyle W}$ the value of the ${\displaystyle r}$-th harmonic number, that is:[6][7]

${\displaystyle \mathrm {H} (r)=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{r}}{\text{.}}}$

The score of ${\displaystyle W}$ is calculated as the sum of the scores garnered from all the voters.

Formally, assume we have a set of candidates ${\displaystyle C=\{c_{1},c_{2},\ldots ,c_{m}\}}$, a set of voters ${\displaystyle N=\{1,2,\ldots ,n\}}$, and a committee size ${\displaystyle k}$. Let ${\displaystyle A_{i}}$ denote the set of candidates approved by voter ${\displaystyle i\in N}$. The PAV score of a committee ${\displaystyle W\subseteq C}$ with size ${\displaystyle |W|=k}$ is defined as ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} (|A_{i}\cap W|)}$. PAV select the committee ${\displaystyle W}$ with the maximal score.

### Example 1

Assume 2 seats to be filled, and the are four candidates: Andrea (A), Brad (B), Carter (C), and Delilah (D), and 30 voters. The ballots are:

• 5 voters voted for A and B
• 17 voters voted for A and C
• 8 voters voted for D

There are 6 possible results: AB, AC, AD, BC, BD, and CD.

AB AC AD BC BD CD
score from the 5 voters voting for AB ${\displaystyle 5\cdot \left(1+{\tfrac {1}{2}}\right)=7.5}$ ${\displaystyle 5\cdot 1=5}$ ${\displaystyle 5\cdot 1=5}$ ${\displaystyle 5\cdot 1=5}$ ${\displaystyle 5\cdot 1=5}$ ${\displaystyle 5\cdot 0=0}$
score from the 17 voters voting for AC ${\displaystyle 17\cdot 1=17}$ ${\displaystyle 17\cdot \left(1+{\tfrac {1}{2}}\right)=25.5}$ ${\displaystyle 17\cdot 1=17}$ ${\displaystyle 17\cdot 1=17}$ ${\displaystyle 17\cdot 0=0}$ ${\displaystyle 17\cdot 1=17}$
score from the 8 voters voting for D ${\displaystyle 8\cdot 0=0}$ ${\displaystyle 8\cdot 0=0}$ ${\displaystyle 8\cdot 1=8}$ ${\displaystyle 8\cdot 0=0}$ ${\displaystyle 8\cdot 1=8}$ ${\displaystyle 8\cdot 1=8}$
Total score 24.5 30.5 30 22 13 25

Andrea and Carter are elected.

Note that Simple Approval shows that Andrea has 22 votes, Carter has 17 votes, Delilah has 8 votes and Brad has 5 votes. In this case, the PAV selection of Andrea and Carter is coincident with the Simple Approval sequence. However, if the above votes are changed slightly so that A and C receive 16 votes and D receives 9 votes, then Andrea and Delilah are elected since the A and C score is now 29 while the A and D score remains at 30. Also, the sequence created by using Simple Approval remains unchanged. This shows that PAV can give results that are incompatible with the method which simply follows the sequence implied by Simple Approval.

### Example 2

Assume there are 10 seats to be selected, and there are three groups of candidates: red, blue, and green candidates. There are 100 voters:

• 60 voters voted for all blue candidates,
• 30 voters voted for all red candidates,
• 10 voters voted for all green candidates.

In this case PAV would select 6 blue, 3 red, and 1 green candidate. The score of such a committee would be

${\displaystyle 60\cdot \mathrm {H} (6)+30\cdot \mathrm {H} (3)+10\cdot \mathrm {H} (1)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{6}}\right)+30\cdot \left(1+{\tfrac {1}{2}}+{\tfrac {1}{3}}\right)+10\cdot 1=147+55+10=212{\text{.}}}$
All other committees receive a lower score. For example, the score of a committee that consists of only blue candidates would be

${\displaystyle 60\cdot \mathrm {H} (10)+30\cdot \mathrm {H} (0)+10\cdot \mathrm {H} (0)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{10}}\right)\approx 175.73{\text{.}}}$

In this example, the outcome of PAV is proportional: the number of candidates selected from each group is proportional to the number of voters voting for the group. This is not coincidence: If the candidates form disjoint groups, as in the above example (the groups can be viewed as political parties), and each voter votes exclusively for all of the candidates within a single group, then PAV will act in the same way as the D'Hondt method of party-list proportional representation.[1]

## Properties

This section describes axiomatic properties of Proportional Approval Voting.

### Committees of size one

In an election with only one winner, PAV operates in exactly the same way as approval voting. That is, it selects the committee consisting of the candidate who is approved by the most voters.

### Proportionality

Most systems of proportional representation use party lists. PAV was designed to have both proportional representation and personal votes (voters vote for candidates, not for a party list). It deserves to be called a "proportional" system because if votes turn out to follow a partisan scheme (each voter votes for all candidates from a party and no other) then the system elects a number of candidates in each party that is proportional to the number of voters who chose this party (see Example 2).[1] Further, under mild assumptions (symmetry, continuity and Pareto efficiency), PAV is the only extension of the D'Hondt method that allows personal votes and that satisfies the consistency criterion.[2]

Even if the voters do not follow the partisan scheme, the rule provides proportionality guarantees. For example, PAV satisfies the strong fairness property called extended justified representation,[7] as well as the related property proportional justified representation.[8] It also has optimal proportionality degree.[9][10] All these properties guarantee that any group of voters with cohesive (similar) preferences will be represented by a number of candidates that is at least proportional to the size of the group. It has been shown that PAV is the only method satisfying such properties among all PAV-like optimization methods (that may use numbers other than harmonic numbers in their definition).

The committees returned by PAV might not be in the core,[7][11] yet---among the known multiwinner voting rules---PAV is closest to satisfying the property. It guarantees 2-approximation of the core, which is the optimal approximation ratio that can be achieved by a rule satisfying the Pigou–Dalton principle of transfers.[11] Furthermore, PAV satisfies the property of the core if there are sufficiently many similar candidates running in an election.[12]

PAV fails priceability (that is, the choice of PAV cannot be always explained via a process, where the voters are endowed with a fixed amount of virtual money, and spend this spend money on buying candidates they like) and laminar proportionality.[11] Two alternative rules that satisfy priceability and laminar proportionality, and that have comparably good proportionality-related properties to PAV are the Method of Equal Shares and Phragmén's Sequential Rules.[13] These two alternative methods are also computable in polynomial time, yet they fail Pareto efficiency.

### Other properties

Apart from properties pertaining to proportionality, PAV satisfies the following axioms:

PAV fails the following properties:

## Computation

An integer linear programming formulation for computing winning committees according to PAV. The variable ${\displaystyle y_{c}}$ indicates whether candidate ${\displaystyle c}$ is selected or not. The variable ${\displaystyle x_{i,\ell }}$ indicates whether voter ${\displaystyle i}$ approves at least ${\displaystyle \ell }$ selected candidates.[13][15]

Computing the winning committee under PAV is NP-hard,[16][17] making it a computationally demanding voting method as the number of candidates and seats increase. Under a brute force approach, if there were m candidates and k seats, then there would be

${\displaystyle {\binom {m}{k}}={\frac {m!}{k!(m-k)!}}}$

combinations of candidates to compare with each election.[18] For example, if there were 24 candidates for 4 seats, there would be 10,626 combinations for which we would need to calculate PAV scores. An election requiring this many calculations would necessitate vote counting by computer. For medium-size elections, the outcome of PAV can be computed by using integer programming solvers. The ILP implementation of PAV is a part of the Python package abcvoting.[19] However, when k is fixed, the computation of the PAV winning subset is computable in polynomial time, i.e. ${\displaystyle O(nm^{k})}$, where n is the number of voters.

Sequential proportional approval voting is a method that can be considered an approximation of PAV with approximation ratio equal to ${\displaystyle 1-1/e\approx 0.63}$, so the PAV score of the resulting committee is at most 37% worse than optimal.[17] This method can be computed in polynomial time, and the election outcome could potentially be determined by hand. Sequential proportional approval voting on its own exhibits good properties and can be used as a full-fledged election system, though formally it fails all the proportionality properties that distinguish PAV. A more complex approach based on randomized rounding gives an approximation ratio of 0.7965.[20] Under standard assumptions in complexity theory, this is the best approximation ratio that can be achieved for PAV in polynomial time.[20] The problem of approximating PAV can be also formulated as the a minimization problem (instead of maximizing ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$ we want to minimize ${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$), in which case the best known approximation ratio is 2.36.[21]

From the perspective of parameterized complexity, the problem of computing PAV is typically hard, with a few exceptional easy cases.[16][22] The problem is NP-hard even in the two-dimensional spatial model of voting.[23] It is solvable in polynomial time in the case of a single dimension.[15]

## Beyond approval committee elections

PAV can be used for voting on an agenda consisting of a number of independent issues, on which yes/no decisions need to be made.[24][25]

• Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. SpringerBriefs in Intelligent Systems. arXiv:2007.01795. doi:10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID 244921148.
• Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (2017-10-26). "Multiwinner Voting: A New Challenge for Social Choice Theory". In Endriss, Ulle (ed.). Trends in Computational Social Choice. AI Access. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)

## References

1. ^ a b c Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). "Multiwinner Approval Rules as Apportionment Methods". Journal of Theoretical Politics. 30 (3): 358–382. arXiv:1611.08691. doi:10.1177/0951629818775518. S2CID 10535322.
2. ^ a b Lackner, Martin; Skowron, Piotr (2021). "Consistent approval-based multi-winner rules". Journal of Economic Theory. 192: 105173. arXiv:1704.02453. doi:10.1016/j.jet.2020.105173. S2CID 232116881.
3. ^ Thiele, Thorvald N. (1895). "Om Flerfoldsvalg". Oversigt over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger: 415–441.
4. ^ a b Janson, Svante (2016). "Phragmén's and Thiele's election methods". arXiv:1611.08826 [math.HO].
5. ^ "RangeVoting.org - Optimal proportional representation". rangevoting.org. Retrieved 2023-01-12.
6. ^ a b Kilgour, D. Marc (2010). "Approval Balloting for Multi-winner Elections". In Jean-François Laslier; M. Remzi Sanver (eds.). Handbook on Approval Voting. Springer. pp. 105–124. ISBN 978-3-642-02839-7.
7. ^ a b c Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. doi:10.1007/s00355-016-1019-3. S2CID 8564247.
8. ^ Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martin; Fernández, Norberto; Fisteus, Jesús; Val, Pablo Basanta; Skowron, Piotr (2017-02-10). "Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). doi:10.1609/aaai.v31i1.10611. ISSN 2374-3468. S2CID 17538641.
9. ^ Aziz, Haris; Elkind, Edith; Huang, Shenwei; Lackner, Martin; Sánchez Fernández, Luis; Skowron, Piotr (2018). "On the Complexity of Extended and Proportional Justified Representation". Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI-18. 32 (1): 902–909.
10. ^ Skowron, Piotr (2021). "Proportionality Degree of Multiwinner Rules". Proceedings of the 22nd ACM Conference on Economics and Computation. EC-21: 820–840. arXiv:1810.08799. doi:10.1145/3465456.3467641. ISBN 9781450385541. S2CID 53046800.
11. ^ a b c d Peters, Dominik; Skowron, Piotr (2020). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC'20: 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 9781450379755. S2CID 208291203.
12. ^ Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020). "Approval-Based Apportionment". Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI-20. 34 (2): 1854–1861. arXiv:1911.08365. doi:10.1609/aaai.v34i02.5553. S2CID 208158445.
13. Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. SpringerBriefs in Intelligent Systems. arXiv:2007.01795. doi:10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID 244921148.
14. ^ Sánchez Fernández, Luis; Fisteus, Jesús (2019). "Monotonicity Axioms in Approval-based Multi-winner Voting Rules" (PDF). Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS-19: 485–493. arXiv:1710.04246.
15. ^ a b Peters, Dominik (2018). "Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections". Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI-18: 1169–1176. arXiv:1609.03537.
16. ^ a b Aziz, Haris; Gaspers, Serge; Gudmundsson, Joachim; Mackenzie, Simon; Mattei, Nicholas; Walsh, Toby (2015). "Computational Aspects of Multi-Winner Approval Voting". Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. AAMAS-15: 107–115. arXiv:1407.3247. ISBN 978-1-4503-3413-6.
17. ^ a b Skowron, Piotr; Faliszewski, Piotr; Lang, Jérôme (2016). "Finding a collective set of items: From proportional multirepresentation to group recommendation". Artificial Intelligence. 241: 191–216. arXiv:1402.3044. doi:10.1016/j.artint.2016.09.003. S2CID 11313941.
18. ^ Plaza, E. (2004). "Technologies for political representation and accountability". www.semanticscholar.org. S2CID 17991644. Retrieved 2023-01-12.
19. ^ The Python library abcvoting contains several algorithms for computing PAV, including very fast ones based on integer linear programming.
20. ^ a b Dudycz, Szymon; Manurangsi, Pasin; Marcinkowski, Jan; Sornat, Krzysztof (2020). "Tight Approximation for Proportional Approval Voting". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI-20: 276–282. doi:10.24963/ijcai.2020/39. ISBN 978-0-9992411-6-5. S2CID 220484671.
21. ^ Byrka, Jaroslaw; Skowron, Piotr; Sornat, Krzysztof (2018). "Proportional Approval Voting, Harmonic k-median, and Negative Association". Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. ICALP-18. 107: 26:1–26:14. arXiv:1704.02183. doi:10.4230/LIPIcs.ICALP.2018.26. ISBN 9783959770767. S2CID 3839722.
22. ^ Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Knop, Dusan; Niedermeier, Rolf (2020). "Parameterized Algorithms for Finding a Collective Set of Items". Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI-20. 34 (2): 1838–1845. doi:10.1609/aaai.v34i02.5551. S2CID 213963505.
23. ^ Godziszewski, Michal; Batko, Pawel; Skowron, Piotr; Faliszewski, Piotr (2021). "An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections". Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence. AAAI-21. 35 (6): 5448–5455. doi:10.1609/aaai.v35i6.16686. S2CID 235306592.
24. ^ Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). "Fair Public Decision Making". Proceedings of the 18th ACM Conference on Economics and Computation. EC'17: 629–646. arXiv:1611.04034. doi:10.1145/3033274.3085125. ISBN 9781450345279. S2CID 30188911.
25. ^ Freeman, Rupert; Kahng, David; Pennock, Anson (2020). "Proportionality in Approval-Based Elections With a Variable Number of Winners". Proceedings of the 29th International Joint Conference on Artificial Intelligence. IJCAI'20. 1: 132–138. doi:10.24963/ijcai.2020/19. ISBN 978-0-9992411-6-5. S2CID 211052991.


text:
Given a weighted rooted tree tree, PathLengths() returns the distance from each vertex to each of its descendant vertices.

PathLengths(tree, fullMatrix = FALSE)

Arguments

tree

Original tree of class phylo, in Preorder.

fullMatrix

Logical specifying return format; see "value" section.

Value

If fullMatrix = TRUE, PathLengths() returns a square matrix in which entry [i, j] denotes the distance from internal node i to the descendant vertex j. Vertex pairs without a continuous directed path are denoted NA. If fullMatrix = FALSE, PathLengths() returns a data.frame with three columns: start lists the deepest node in each path (i.e. that closest to the root); end lists the shallowest node (i.e. that closest to a leaf); length lists the total length of that path.

Other tree properties: ConsensusWithout(), NSplits(), NTip(), SplitsInBinaryTree(), TipLabels(), TreeIsRooted()

Author

Martin R. Smith (martin.smith@durham.ac.uk)

Examples

tree <- rtree(6)
plot(tree)
nodelabels()
tiplabels()

PathLengths(tree)
#>    start end     length
#> 1      7   1 0.44186817
#> 2      8   1 0.29856379
#> 3      9   1 0.05893438
#> 4      7   2 1.02522205
#> 5      8   2 0.88191767
#> 6      9   2 0.64228826
#> 7      7   3 1.79848827
#> 8      8   3 1.65518389
#> 9     10   3 0.77891468
#> 10     7   4 1.81688242
#> 11     8   4 1.67357804
#> 12    10   4 0.79730883
#> 13     7   5 0.86535854
#> 14    11   5 0.41008408
#> 15     7   6 1.26614470
#> 16    11   6 0.81087024
#> 17     7   8 0.14330438
#> 18     7   9 0.38293379
#> 19     8   9 0.23962942
#> 20     7  10 1.01957359
#> 21     8  10 0.87626921
#> 22     7  11 0.45527445
`


text:
# How do you write the complex conjugate of the complex number 7+2i?

$7 - 2 i$
The conjugate of the complex number $a + b i$ is $a - b i$.
Hence, the conjugate of $7 + 2 i$ is $7 - 2 i$


text:
Subjects -> STATISTICS (Total: 130 journals)
 Showing 1 - 151 of 151 Journals sorted alphabetically Advances in Complex Systems       (Followers: 10) Advances in Data Analysis and Classification       (Followers: 61) Annals of Applied Statistics       (Followers: 39) Applied Categorical Structures       (Followers: 4) Argumentation et analyse du discours       (Followers: 10) Asian Journal of Mathematics & Statistics       (Followers: 8) AStA Advances in Statistical Analysis       (Followers: 4) Australian & New Zealand Journal of Statistics       (Followers: 13) Bernoulli       (Followers: 9) Biometrical Journal       (Followers: 10) Biometrics       (Followers: 51) British Journal of Mathematical and Statistical Psychology       (Followers: 18) Building Simulation       (Followers: 1) Bulletin of Statistics       (Followers: 4) CHANCE       (Followers: 5) Communications in Statistics - Simulation and Computation       (Followers: 9) Communications in Statistics - Theory and Methods       (Followers: 11) Computational Statistics       (Followers: 14) Computational Statistics & Data Analysis       (Followers: 37) Current Research in Biostatistics       (Followers: 8) Decisions in Economics and Finance       (Followers: 11) Demographic Research       (Followers: 16) Electronic Journal of Statistics       (Followers: 8) Engineering With Computers       (Followers: 5) Environmental and Ecological Statistics       (Followers: 7) ESAIM: Probability and Statistics       (Followers: 5) Extremes       (Followers: 2) Fuzzy Optimization and Decision Making       (Followers: 8) Geneva Papers on Risk and Insurance - Issues and Practice       (Followers: 13) Handbook of Numerical Analysis       (Followers: 5) Handbook of Statistics       (Followers: 7) IEA World Energy Statistics and Balances -       (Followers: 2) International Journal of Computational Economics and Econometrics       (Followers: 6) International Journal of Quality, Statistics, and Reliability       (Followers: 17) International Journal of Stochastic Analysis       (Followers: 3) International Statistical Review       (Followers: 12) International Trade by Commodity Statistics - Statistiques du commerce international par produit Journal of Algebraic Combinatorics       (Followers: 4) Journal of Applied Statistics       (Followers: 20) Journal of Biopharmaceutical Statistics       (Followers: 20) Journal of Business & Economic Statistics       (Followers: 39, SJR: 3.664, CiteScore: 2) Journal of Combinatorial Optimization       (Followers: 7) Journal of Computational & Graphical Statistics       (Followers: 20) Journal of Econometrics       (Followers: 82) Journal of Educational and Behavioral Statistics       (Followers: 6) Journal of Forecasting       (Followers: 17) Journal of Global Optimization       (Followers: 7) Journal of Interactive Marketing       (Followers: 10) Journal of Mathematics and Statistics       (Followers: 8) Journal of Nonparametric Statistics       (Followers: 6) Journal of Probability and Statistics       (Followers: 10) Journal of Risk and Uncertainty       (Followers: 32) Journal of Statistical and Econometric Methods       (Followers: 5) Journal of Statistical Physics       (Followers: 13) Journal of Statistical Planning and Inference       (Followers: 8) Journal of Statistical Software       (Followers: 20, SJR: 13.802, CiteScore: 16) Journal of the American Statistical Association       (Followers: 72, SJR: 3.746, CiteScore: 2) Journal of the Korean Statistical Society       (Followers: 1) Journal of the Royal Statistical Society Series C (Applied Statistics)       (Followers: 31) Journal of the Royal Statistical Society, Series A (Statistics in Society)       (Followers: 26) Journal of the Royal Statistical Society, Series B (Statistical Methodology)       (Followers: 43) Journal of Theoretical Probability       (Followers: 3) Journal of Time Series Analysis       (Followers: 16) Journal of Urbanism: International Research on Placemaking and Urban Sustainability       (Followers: 30) Law, Probability and Risk       (Followers: 8) Lifetime Data Analysis       (Followers: 7) Mathematical Methods of Statistics       (Followers: 4) Measurement Interdisciplinary Research and Perspectives       (Followers: 1) Metrika       (Followers: 4) Modelling of Mechanical Systems       (Followers: 1) Monte Carlo Methods and Applications       (Followers: 6) Monthly Statistics of International Trade - Statistiques mensuelles du commerce international       (Followers: 2) Multivariate Behavioral Research       (Followers: 5) Optimization Letters       (Followers: 2) Optimization Methods and Software       (Followers: 8) Oxford Bulletin of Economics and Statistics       (Followers: 34) Pharmaceutical Statistics       (Followers: 17) Probability Surveys       (Followers: 4) Queueing Systems       (Followers: 7) Research Synthesis Methods       (Followers: 7) Review of Economics and Statistics       (Followers: 124) Review of Socionetwork Strategies Risk Management       (Followers: 15) Sankhya A       (Followers: 2) Scandinavian Journal of Statistics       (Followers: 9) Sequential Analysis: Design Methods and Applications Significance       (Followers: 7) Sociological Methods & Research       (Followers: 37) SourceOCDE Comptes nationaux et Statistiques retrospectives SourceOCDE Statistiques : Sources et methodes SourceOECD Bank Profitability Statistics - SourceOCDE Rentabilite des banques       (Followers: 1) SourceOECD Insurance Statistics - SourceOCDE Statistiques d'assurance       (Followers: 2) SourceOECD Main Economic Indicators - SourceOCDE Principaux indicateurs economiques       (Followers: 1) SourceOECD Measuring Globalisation Statistics - SourceOCDE Mesurer la mondialisation - Base de donnees statistiques SourceOECD Monthly Statistics of International Trade       (Followers: 1) SourceOECD National Accounts & Historical Statistics SourceOECD OECD Economic Outlook Database - SourceOCDE Statistiques des Perspectives economiques de l'OCDE       (Followers: 2) SourceOECD Science and Technology Statistics - SourceOCDE Base de donnees des sciences et de la technologie SourceOECD Statistics Sources & Methods       (Followers: 1) SourceOECD Taxing Wages Statistics - SourceOCDE Statistiques des impots sur les salaires Stata Journal       (Followers: 9) Statistica Neerlandica       (Followers: 1) Statistical Applications in Genetics and Molecular Biology       (Followers: 5) Statistical Communications in Infectious Diseases Statistical Inference for Stochastic Processes       (Followers: 3) Statistical Methodology       (Followers: 7) Statistical Methods and Applications       (Followers: 6) Statistical Methods in Medical Research       (Followers: 27) Statistical Modelling       (Followers: 19) Statistical Papers       (Followers: 4) Statistical Science       (Followers: 13) Statistics & Probability Letters       (Followers: 13) Statistics & Risk Modeling       (Followers: 2) Statistics and Computing       (Followers: 13) Statistics and Economics       (Followers: 1) Statistics in Medicine       (Followers: 191) Statistics, Politics and Policy       (Followers: 6) Statistics: A Journal of Theoretical and Applied Statistics       (Followers: 14) Stochastic Models       (Followers: 3) Stochastics An International Journal of Probability and Stochastic Processes: formerly Stochastics and Stochastics Reports       (Followers: 2) Structural and Multidisciplinary Optimization       (Followers: 12) Teaching Statistics       (Followers: 7) Technology Innovations in Statistics Education (TISE)       (Followers: 2) TEST       (Followers: 3) The American Statistician       (Followers: 24) The Annals of Applied Probability       (Followers: 8) The Annals of Probability       (Followers: 10) The Annals of Statistics       (Followers: 34) The Canadian Journal of Statistics / La Revue Canadienne de Statistique       (Followers: 11) Wiley Interdisciplinary Reviews - Computational Statistics       (Followers: 1)
Similar Journals
 Optimization LettersJournal Prestige (SJR): 0.721 Citation Impact (citeScore): 1Number of Followers: 2      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1862-4480 - ISSN (Online) 1862-4472 Published by Springer-Verlag  [2626 journals]
• On generalized convex functions and generalized subdifferential II
• Abstract: Abstract We introduce and study the notion of the $$\left( \sigma ,y\right)$$ -conjugate of a proper $$\sigma$$ -convex function. Some relations between the $$\sigma$$ -subdifferentials and the Clarke–Rockafellar subdifferential are established. Also, we present some results regarding the $$\sigma$$ -monotonicity of the $$\sigma$$ -subdifferential of a function and its $$\sigma$$ -convexity. Moreover, we obtain some particular relationships between the $$\sigma$$ -subdifferential and the $$\left( \sigma ,y\right)$$ -conjugate.
PubDate: 2021-01-16

• Bounds of the solution set of the tensor complementarity problem
• Abstract: Abstract Recently, the estimation problem of upper and lower bounds of the solution set of the tensor complementarity problem has been studied when the tensor involved is a strictly semi-positive tensor or one of its subclasses. This paper aims to study such an estimation problem in a larger scope. First, we propose a lower bound formula under the condition that the tensor complementarity problem has a solution. When the problem under consideration falls back to several types of problems that have been studied, the achieved result improves the relevant known results. Second, by means of a newly introduced quantity, we give an upper bound formula of the solution set when the problem has a solution and the tensor involved is an $$R_0$$ -tensor. This formula is new even when the concerned problem falls back to several problems that have already been discussed. Several examples are also given to confirm our theoretical findings.
PubDate: 2021-01-12

• Bi-objective optimization model for the heterogeneous dynamic dial-a-ride
problem with no rejects
• Abstract: Abstract This work proposes a bi-objective mathematical optimization model and a two-stage heuristic for a real-world application of the heterogeneous Dynamic Dial-a-Ride Problem with no rejects, i.e., a patient transportation system. The problem consists of calculating route plans to meet a set of transportation requests by using a given heterogeneous vehicle fleet. These transportation requests can be either static or dynamic, and all of them must be attended to. In the first stage of the proposed heuristic, the problem’s static part is solved by applying a General Variable neighborhood Search based algorithm. In the second stage, the dynamic requests are dealt with by implementing a simple insertion heuristic. We create different instances based on the real data provided by a Brazilian city’s public health care system and test the proposed approach on them. The analysis of the results shows that the higher the level of dynamism, i.e., the number of urgent requests on each instance, the smaller the objective function value will be in the static part. The results also demonstrate that a higher level of dynamism increases the chance of a time window violation happening. Besides, we use the weighted sum method of the two conflicting objectives to analyze the trade-off between them and create an approximation for the Pareto frontier.
PubDate: 2021-01-08

• DC programming and DCA for enhancing physical layer security via relay
beamforming strategies
• Abstract: Abstract Beside of cryptography-the primary traditional methods for ensuring information security and confidentiality, the appearance of the physical layer security approach plays an important role for not only enabling the data transmission confidentially without relying on higher-layer encryption, but also enhancing confidentiality of the secret key distribution in cryptography. Many techniques are employed in physical layers to improve secure transmission including cooperative relaying and beamforming technique. In this paper, we consider the secrecy rate maximization problems using two techniques mentioned above with two different relaying protocols: Amplify-and-Forward and Decode-and-Forward. The optimization problems with the aim of maximizing secrecy rate subject to total and individual relay power constraints are formulated as nonconvex problems, which can be reformulated as DC (difference of two convex functions) programs and thus can be solved by DC Algorithms (DCA). The special structure of feasible set is exploited which results to an efficient DC decomposition in the sense that it leads to convex subproblems that can be explicitly solved. The numerical results show that the proposed DCA schemes are better than the existing methods in terms of both runtime and secrecy rate.
PubDate: 2021-01-08

• A difference-of-convex programming approach with parallel branch-and-bound
for sentence compression via a hybrid extractive model
• Abstract: Abstract Sentence compression is an important problem in natural language processing with wide applications in text summarization, search engine and human–AI interaction system etc. In this paper, we design a hybrid extractive sentence compression model combining a probability language model and a parse tree language model for compressing sentences by guaranteeing the syntax correctness of the compression results. Our compression model is formulated as an integer linear programming problem, which can be rewritten as a difference-of-convex (DC) programming problem based on the exact penalty technique. We use a well-known efficient DC algorithm—DCA to handle the penalized problem for local optimal solutions. Then a hybrid global optimization algorithm combining DCA with a parallel branch-and-bound framework, namely PDCABB, is used for finding global optimal solutions. Numerical results demonstrate that our sentence compression model can provide excellent compression results evaluated by F-score, and indicate that PDCABB is a promising algorithm for solving our sentence compression model.
PubDate: 2021-01-07

• An efficient algorithm for large-scale extended trust-region subproblems
with non-intersecting linear constraints
• Abstract: Abstract In this paper, we study the extended trust-region subproblem in which the trust-region intersects the ball with m linear inequality constraints (m-eTRS). We assume that the linear constraints do not intersect inside the ball. We show that the optimal solution of m-eTRS can be found by solving one TRS, computing the local non-global minimizer of TRS if it exists and solving at most two TRSs with an additional linear equality constraint (1-eqTRS). Both TRS and (1-eqTRS) are polynomially and efficiently solvable, thus the new algorithm significantly improves over the SOCP/SDP relaxation of Burer and Yang [Math Program 149(1-2):253–264, 2015]. on two classes of test problems, the efficiency of the proposed approach is compared with the SOCP/SDP relaxation and branch and bound algorithm of Beck and Pan [J Global Optim 69(2):309–342, 2017].
PubDate: 2021-01-06

• Second order variational analysis of disjunctive constraint sets and its
applications to optimization problems
• Abstract: Abstract In this paper, we examine the properly twice epi-differentiability and compute the second order epi-subderivative of the indicator function to a class of sets including the finite union of parabolically derivable and parabolically regular sets. In this way, we provide no-gap second order optimality conditions for a disjunctive constrained problem. Moreover, we derive applications of our results to some types of disjunctive programs.
PubDate: 2021-01-06

• The vertex colourability problem for $$\{claw,butterfly\}$$ { c l a w , b
u t t e r f l y } -free graphs is polynomial-time solvable
• Abstract: Abstract The vertex colourability problem is to determine, for a given graph and a given natural k, whether it is possible to split the graph’s vertex set into at most k subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for $$\{claw,butterfly\}$$ -free graphs. A claw is the star graph with three leaves, a butterfly is obtained by coinciding a vertex in a triangle with a vertex in another triangle.
PubDate: 2021-01-06

• Maximum shortest path interdiction problem by upgrading edges on trees
under hamming distance
• Abstract: Abstract We consider the maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance (denoted by (MSPITH)), which has wide applications in transportation network, network war and terrorist network. The problem (MSPITH) aims to maximize the length of the shortest path from the root of a tree to all its leaves by upgrading edge weights such that the upgrade cost under sum-Hamming distance is upper-bounded by a given value. We show that the problem (MSPITH) under weighted sum-Hamming distance is NP-hard. We consider two cases of the problem (MSPITH) under unit sum-Hamming distance based on the number K of critical edges. We propose a greedy algorithm within $$O(n+l\log l)$$ time when $$K=1$$ and a dynamic programming algorithm within $$O(n(\log n+K^3))$$ time when $$K>1$$ , where n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we consider a minimum cost shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary search algorithm within $$O(n^4\log n)$$ time, where a dynamic programming algorithm is executed in each iteration to solve its corresponding problem (MSPITH). Finally, we design numerical experiments to show the effectiveness of the algorithms.
PubDate: 2021-01-06

• A new concave minimization algorithm for the absolute value equation
solution
• Abstract: Abstract In this paper, we study the absolute value equation (AVE) $$Ax-b= x$$ . One effective approach to handle AVE is by using concave minimization methods. We propose a new method based on concave minimization methods. We establish its finite convergence under mild conditions. We also study some classes of AVEs which are polynomial time solvable.
PubDate: 2021-01-05

• Optimization approach to Berge equilibrium for bimatrix game
• Abstract: Abstract The paper deals with a Berge equilibrium (Théorie générale des jeux à-personnes, Gauthier Villars, Paris, 1957; Some problems of non-antagonistic differential games, 1985) in the bimatrix game for mixed strategies. Motivated by Nash equilibrium (Ann Math 54(2):286, 1951; Econometrica 21(1):128–140, 1953), we prove an existence of Berge equilibrium in the bimatrix game. Based on Mills theorem (J Soc Ind Appl Math 8(2):397–402, 1960), we reduce the bimatrix game to a nonconvex optimization problem. We illustrate the proposed approach on an example.
PubDate: 2021-01-04

• A variable neighborhood search for the last-mile delivery problem during
major infectious disease outbreak
• Abstract: Abstract During major infectious disease outbreak, such as COVID-19, the goods and parcels supply and distribution for the isolated personnel has become a key issue worthy of attention. In this study, we propose a delivery problem that arises in the last-mile delivery during major infectious disease outbreak. The problem is to construct a Hamiltonian tour over a subset of candidate parking nodes, and each customer is assigned to the nearest parking node on the tour to pick up goods or parcels. The aim is to minimize the total cost, including the routing, allocation, and parking costs. We propose three models to formulate the problem, which are node-based, flow-based and bilevel programing formulations. Moreover, we develop a variable neighborhood search algorithm based on the ideas from the bilevel programing formulations to solve the problem. Finally, the proposed algorithm is tested on a set of randomly generated instances, and the results indicate the effectiveness of the proposed approach.
PubDate: 2021-01-04

• Optimization on fractal sets
• Abstract: Abstract In the sequel, we outline necessary and sufficient condition to the existence of extremas of a function on a self-similar set, and we describe discrete gradient algorithm to find the extrema.
PubDate: 2021-01-04

• On the approximability of the fixed-tree balanced minimum evolution
problem
• Abstract: Abstract The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret’s proof of the $$\mathcal {NP}$$ -hardness of the BMEP suffice to prove the general $$\mathcal {NP}$$ -hardness of the FT-BMEP as well as its strong inapproximability.
PubDate: 2021-01-02

pseudomonotone variational inequalities
• Abstract: Abstract The purpose of this paper is to introduce a new modified subgradient extragradient method for finding an element in the set of solutions of the variational inequality problem for a pseudomonotone and Lipschitz continuous mapping in real Hilbert spaces. It is well known that for the existing subgradient extragradient methods, the step size requires the line-search process or the knowledge of the Lipschitz constant of the mapping, which restrict the applications of the method. To overcome this barrier, in this work we present a modified subgradient extragradient method with adaptive stepsizes and do not require extra projection or value of the mapping. The advantages of the proposed method only use one projection to compute and the strong convergence proved without the prior knowledge of the Lipschitz constant of the inequality variational mapping. Numerical experiments illustrate the performances of our new algorithm and provide a comparison with related algorithms.
PubDate: 2021-01-02

• Maximizing recyclable materials and user utility in waste collection: a
• Abstract: Abstract In this paper, we present the problem in which a municipal company operating in the waste management sector willing to encourage users to use differentiated waste collection facilities, designs a utility user function to attain such a goal. The problem is modeled in terms of bilevel optimization where the leader is the municipal firm which aims at maximizing the concurrent fraction of user waste demand thrown in recycling facilities, and the follower are users aiming at maximizing the utility function proposed by the leader. The resulting bilevel model is analysed in terms of stability showing that its optimistic solution value equals the pessimistic solution value. A solution approach is presented. Finally, a computational study shows the effectiveness of our proposal.
PubDate: 2021-01-02

• A multi-objective parallel variable neighborhood search for the
bi-objective obnoxious p-median problem
• Abstract: Abstract Researchers and practitioners have addressed many variants of facility locations problems. Each location problem can be substantially different from each other depending on the objectives and/or constraints considered. In this paper, the bi-objective obnoxious p-median problem (Bi-OpM) is addressed given the huge interest to locate facilities such as waste or hazardous disposal facilities, nuclear power or chemical plants and noisy or polluting services, among others. The Bi-OpM aims to locate p facilities maximizing two different objectives: the distance between each customer and their nearest facility center and the dispersion among facilities. To address the Bi-OpM problem a Multi-objective Parallel Variable Neighborhood Search approach (Mo-PVNS) is implemented. Computational results indicate the superiority of the Mo-PVNS compared to the state-of-art algorithms.
PubDate: 2021-01-02

• On the solution existence to convex polynomial programs and its
applications
• Abstract: Abstract In this paper, we present necessary/sufficient conditions for the convex polynomial programming (CPP) problems. Some new stability results for parametric CPP problems are characterized under a regular condition. We give a positive answer for the open question in Kim et al. (Optim Lett 6:363–373, 2012) for the solution existence of convex quadratic programming problems.
PubDate: 2021-01-02

• Dual optimal design and the Christoffel–Darboux polynomial
• Abstract: Abstract The purpose of this short note is to show that the Christoffel–Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Geometric interpretations and algorithmic consequences are mentioned.
PubDate: 2021-01-01

• An efficient heuristic for a hub location routing problem
• Abstract: Abstract This paper examines a new model for hub location known as the hub location routing problem. The problem shares similarities with the well studied uncapacitated single allocation p-hub median problem except that the hubs are now connected to each other by a cyclical path (or tour) known as the global route, each cluster of non-hub nodes and assigned hub is also connected by a single tour known as a local route, and the length of the local routes is constrained to a maximum number of nodes. Thus, aside from the normal tasks of hub selection and allocation of non-hub nodes, up to p + 1 travelling salesman problems need to be solved. A heuristic based on the general variable neighborhood search framework is proposed here to solve this very complicated problem. The improvement phase of the algorithm uses a sequential variable neighborhood descent with multiple neighborhoods required to suit the complex nature of the problem. A best sequencing of the neighborhoods is established through empirical testing. The perturbation phase known as the shaking procedure also uses a well-structured selection of neighborhoods in order to effectively diversify the search to different regions of the solution space. Extensive computational testing shows that the new heuristic significantly outperforms the state-of-the-art. Out of 912 test instances from the literature, we are able to obtain 691 new best known solutions. Not only are the improvements in objective values quite impressive, but also these new solutions are obtained in a small fraction of the time required by the competing algorithms.
PubDate: 2020-11-28

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762


text:
# How does one go from measure P to Q(risk-neutral) when modeling an asset paying dividends?

I am really having a terrible time applying Girsanov's theorem to go from the real-world measure $P$ to the risk-neutral measure $Q$. I want to determine the payoff of a derivative based an asset which is paying dividends, so the dividends will affect the value of the asset by changing the drift negatively, but aren't considered when calculating the payoff because it's just derived from the asset prices over time.

We begin in the real-world measure $P$. We are interested in some index, $S_t$, which I believe we can just treat as a single entity like a stock and which we can observe in the real world. It has volatility $\sigma$. We also know that this index is paying dividends continuously at a rate of $\delta$. The index is described as "following a geometric Brownian motion", which to me says that the there is no other drift going on, so I take $\mu$ to be $0 - \delta$. First question: Is it normal to assume no other drift?

$dSt = (-\delta) St dt + \sigma St dWt$

Where $dWt$ are standard Wiener increments.

So clearly under $P$, our index asset has drift $-\delta$ because it is paying dividends out.

If someone actually holds the asset then they can reinvest those dividends, but we are only concerned with the value of the asset in order to determine the payoff of a derivative.

So what we want to do now is determine the expected value of the asset under the risk neutral measure, $Q$. We want this expected value, discounted by the value of a bond earning the risk free rate, to be a martingale in this measure, so the asset must also drift at the risk free rate. In this way, an asset under the risk neutral measure with volatility 0 is equivalent to a bond.

In order to achieve this, we want to change the drift of our process from $-\delta$ under $P$ to $r$ under $Q$. We define a new process

$X_t = \theta t + W_t$

where

$\theta = \frac{(-\delta - r)}{\sigma}$

If we now consider the discounted asset price $S_t^* = S_t / Bt = S_t e^{-rt}$ we have the following.

$dSt^* = (-\delta - r) St^* dt + \sigma St^* dWt$

$dSt^* = (-\delta - r) St^* dt + \sigma St^* (X_t - \theta)$

$dSt^* = (-\delta - r) St^* dt + \sigma St^* (X_t - \frac{-\delta - r}{\sigma})$

$dSt^* = \sigma St^* X_t$

Where now we have the process $St^*$ as a geometric Brownian with no drift if we are under $Q$ and with the same drift as before under $P$. All we have done was put $(X_t-\theta)$ in for $W_t$ and these are equal by definition.

So under $Q$, and without discounting, the process for the asset $S_t$ should follow

$dSt = r St dt + \sigma St dXt$

The dividend being payed by the asset is thus somehow 'inside' the brownian motion $X_t$ and that's apparently all we see of it?

At this point, I'd like to stop and ask "at what point do we consider ourselves 'under $Q$'?". By google-fu, I found an example program in R where they make a binomial approximation to Brownian motion by taking constant size steps up or down with different propbabilities. The relevant portion of code looks like:

n = 2000
t = (0:n)/n  # [0/n, 1/n, .... n/n]
dt = 1/n
theta = 1
p = 0.5 * (1 - sqrt(dt) * theta)

u = runif(n)  # Random uniform variates
dWP = ((u < .5) - (u > .5))*sqrt(dt)    # increments under P
dWQ = ((u < p) - (u > p))*sqrt(dt)      # increments under Q

WP[1:n+1] = cumsum(dWP)
WQ[1:n+1] = cumsum(dWQ)
XP = WP + theta*t      # Theta exactly offsets the change in measure
XQ = WQ + theta*t      # Now XQ == WP

I see that they are using $p$ instead of 0.5 to make decisions about the sign in the binary discretization, but if we have access to actual random normal variates is this necessary? Shouldn't it be a enough to simply define $\theta$ appropriately as above and then use it and $W_t$ to derive $X_t$, directly? Although, if we do that, then we go from $W$ to $X$ but I don't understand how we got from $P$, to $Q$ if that happened at all.

The payoff of our asset then, is the discounted expectation under the risk-neutral measure. So we evolve the process $S_t$ under measure $Q$ until expiry time T, calculate the payoff. Repeat this a few thousand times and then take the average and discount it back to $t = 0$ to get the price.

I thought all of this seemed pretty reasonable and was making sense, but when I try to implement it, I get nothing like what I expect. Can anyone confirm that the story I just presented about how we arrive at the risk neutral measure is correct?

A more general question: $W_t$ is a martingale under $P$. We shift it and change measures to create $X_t$ and have that be a martingale under $Q$. We then model the asset based on the process $X_t$ with drift r. If all we wanted was a process under which the stock drifts at the risk free rate, what do we gain by changing from $W$ to $X$ and $P$ to $Q$ if they exactly offset each other? Why don't we just use $W_t$? And what happened to the dividend?

If the stock process is drifting downward at $-\delta dt$ under $P$, what does it really look like under $Q$? It can't just look like it's drifting at the risk-free-rate because then the dividend would have had no effect at all.

Further search produced some suggestions that it should be drifting at $r-\delta$, because we assume that the dividends are invested into bonds. Why would we make such an assumption? Is it because we want to consider a portfolio containing the asset and not the asset itself?

-

ad) "Is it normal to assume no other drift?" Under measure P you might have drift. You could use it as a working assumption, but in general indices drift every now and then. So, no, usually you do not assume away the drift.

"The index is described as "following a geometric Brownian motion", which to me says that the there is no other drift going on" geometric Brownian motion: S follows a gBm if it satisfies the well-known dS/S SDE, drift non-zero, contrary to your deduction.

ad) "at what point do we consider ourselves 'under Q '?". Q is the risk-neutral measure: when you insert your X-expression for W, you switch to drift r and to Q. Btw, see the link for getting notation and derivation right.

ad) "If the stock process is drifting downward at −δdt under P , what does it really look like under Q ?" Insert mu=mu*-delta in here. This yields drift coefficient (r+delta)S_t under X.

ad) "because we assume that the dividends are invested into bonds." Here the dividend is an average yield over the holding period. You reinvest it in the underlying.

ad) "I thought all of this seemed pretty reasonable and was making sense": Sounds good.

-
So if I am understanding you correctly here, the dividend payments will result in the stock drifting higher under Q than it would without them: (r+delta) instead of (r-delta)? I don't see how that works. Taking the dividends out of the stock should lower the value of the stock right? If they are being reinvested into the stock, our portfolio will reflect that we own more shares, but I don't see why the value of the stock should also be going up. –  John Tyree May 18 '12 at 13:40
Also, when you say that "S follows a gBm if it satisfies the well-known dS/S SDE, drift non-zero...", I assume you are referring to dS/S = mu dt + sig dz, but why does this stop being gBm if mu = 0? –  John Tyree May 18 '12 at 13:43
ad) "I assume you are referring to dS/S = mu dt + sig dz, but why does this stop being gBm if mu = 0?": In "The index is described as "following a geometric Brownian motion", which to me says that the there is no other drift going on" you seemed to deduce that mu=0 from the fact that the index is supposed to follow a gBm. I wanted to make clear to you, that although the index is supposed to follow a gBm, this does not imply that mu=0. –  Konsta May 18 '12 at 18:28
Yes, you are right. It should've been mu=mu*-r, i.e. theta=(mu*-r)/sigma with mu*=0 with your gBm assumption. This would've yielded (r-delta) under X. –  Konsta May 18 '12 at 21:34
Ok I think I understand now. The drift is not 0, but it will be incorporated into the process X under Q, such that the SDE will always take the form that you described with (r-delta). –  John Tyree May 18 '12 at 23:01

Just following Musiela Rutkowski (the link redirects to Amazon). The risk neutral measure is derived form imposing that the present value of a self financed portfolio (i.e.; no infusion or withdraw of money) is a martingale. A portfolio can be seen as a stochastic process where its value at time $t$ is given by $$V_t = \phi^0_tP_t + \phi^1_tS_t\ ,$$ this is, the value is equal to the number of cash $\phi^0_t$ times the growth of the money $P_t=e^{rt}$ plus the number of shares $\phi_t^1$ times the value of the share $S_t$ at time $t$. If we assume a constant dividend yield $q$ (proportional to the spot) the increment in value is given by $$dV_t = \phi_t^0 dP_t + \phi_t^1dS_t + \phi_t^1qS_tdt$$ that is the change of value of every component plus the dividend amount we receive $\phi_t^1qS_t$ in cash at every instant increment $dt$. We are assuming a geometric Brownian motion for the price of the share described by $dS_t=S_t(\mu dt + \sigma dW_t)$ under the physical measure, therefore $$dV_t = \phi_t^0 dP_t + \phi_t^1S_t((\mu + q)dt + \sigma dW_t)\ .$$ Now just follow the same steps as the non dividend paying stock. To make the discounted value of our portfolio follow a martingale we will need $$d(e^{-rt}V_t) = \phi_t^1dS^*_t\ ,\quad \mbox{with},\qquad dS_t^*=S_t^*\sigma dX_t$$ $$X_t = W_t - \frac{r-q-\mu}{\sigma}t$$ Replacing $dW_t=dX_t + \frac{1}{\sigma}(r-q-\mu)dt$ in the equation of $dS_t$ yields $$dS_t = S_t((r-q)dt + \sigma dX_t)$$ the evolution under the risk neutral measure.

-


text:
# Cumulative Integration with regard to Vasicek Model's Bond Price and its Forward Price

## (My Question)

Please show me how to compute the following expectation with its computation process. Besides, $$B_t$$ is S.B.M.

$$E\left[ \exp \left( - \int^T_t \int^u_0 \sigma e^{-b(u-s)} d B_s du \right) \right]$$

I have posted the same question on https://math.stackexchange.com/questions/3343590/cumulative-integration-with-regard-to-vasicek-models-bond-price-and-its-forward

## (Original Question)

Solve $$P(t, T)$$ with the following model

$$dr_t=-br_t dt + \sigma dB_t$$

## (My consideration)

• Fist,

$$r_u=e^{-bu} r_0 + \int^u_0 \sigma e^{-b(u-s)} dB_s$$

• Second,

$$\begin{eqnarray} P(t, T) &=& E \left[ \exp \left( - \int^T_t r_u du \right) \middle| \mathcal{F}_t \right] \\ &=& E\left[ \exp \left( - \int^T_t \left(e^{-bu} r_0 + \int^u_0 \sigma e^{-b(u-s)} dB_s \right) du \right) \middle| \mathcal{F}_t \right] \\ &=& E\left[ \exp \left( - \int^T_t e^{-bu} r_0 du - \int^T_t \int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \\ &=& \frac{r_0}{b} (e^{-bT}-e^{-bt}) E\left[ \exp \left(- \int^T_t \int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \end{eqnarray}$$

• Third, I assume to use the following formula, but I cannot have any idea to replace the integration order.

$$E\left[ \exp \left( \int^T_t f(s) dB_s \right) \middle| \mathcal{F}_t \right] = \exp \left( \frac{1}{2} \int^T_t f(s)^2 ds \right)$$

• just curious, what is the textbook that is used in class? – AK88 Sep 6 '19 at 4:09
• It is An Elementary Introduction to Stochastic Interest Rate Modeling (Advanced Series on Statistical Science & Applied Probability). – koji Sep 6 '19 at 12:01

• ## I have developed formulas to solve this by myself!

$$\begin{eqnarray} \int^t_0 \int^u_0 dB_s \ du &=& \int^t_0 \int^u_s du \ dB_s \\ \int^T_t \int^u_0 dB_s \ du &=& \int^T_0 \int^u_s du \ dB_s - \int^t_0 \int^u_s du \ dB_s \end{eqnarray}$$

• ## Therefore, we can use the following formula as I assume.

$$E\left[ \exp \left( \int^T_t f(s) dB_s \right) \middle| \mathcal{F}_t \right] = \exp \left( \frac{1}{2} \int^T_t f(s)^2 ds \right)$$

## the Vasicek Bond Price and its Forward Price

• Recall the result of Exercise 5.2.(1) or Exercise 4.5.(10). $$\begin{eqnarray} P(t, T) &=& E \left[ \exp \left( - \int^T_t r_u du \right) \middle| \mathcal{F}_t \right] \\ &=& E \left[ \exp \left( - \int^T_t \left( e^{-bu} r_0 + \sigma \int^u_0 e^{-b(u-s)} dB_s \right) du\right) \middle| \mathcal{F}_t \right] \\ &=& E \left[ \exp \left( - r_0 \int^T_t e^{-bu} du - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \\ &=& E \left[ \exp \left( - r_0 \left[ -\frac{1}{b} e^{-bu} \right]^T_t - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \\ %&=& E \left[ \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \\ &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \qquad E \left[ \exp \left( - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \end{eqnarray}$$

• Here, one computes the exponential part inside of expectation using the following formula (Cumulative Integration Formula Replacing $$du$$ and $$dB_s$$. (Developed on Sep 5, 2019 by Kojima)) $$\begin{eqnarray} \int^t_0 \int^u_0 dB_s \ du &=& \int^t_0 \int^u_s du \ dB_s \\ \int^T_t \int^u_0 dB_s \ du &=& \int^T_0 \int^u_s du \ dB_s - \int^t_0 \int^u_s du \ dB_s \end{eqnarray}$$

• Therefore, $$\begin{eqnarray} && - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s \ du \nonumber \\ && \qquad = - \int^T_0 \int^u_0 \sigma e^{-b(u-s)} dB_s \ du + \int^t_0 \int^u_0 \sigma e^{-b(u-s)} dB_s \ du \\ && \qquad = - \int^T_0 \int^T_s \sigma e^{-b(u-s)} du \ dB_s + \int^t_0 \int^t_s \sigma e^{-b(u-s)} du \ dB_s \\ && \qquad = - \int^T_0 \left[ -\frac{ \sigma }{b} e^{-b(u-s)} \right]^T_s dB_s + \int^t_0 \left[ -\frac{ \sigma }{b} e^{-b(u-s)} \right]^t_s dB_s \\ && \qquad = \int^T_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \\ && \qquad = \int^T_t \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s \nonumber \\ && \qquad \qquad + \int^t_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \end{eqnarray}$$

• Substitute the above results into the exponential part. $$\begin{eqnarray} P(t, T) &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \qquad E \left[ \exp \left( - \int^T_t\int^u_0 \sigma e^{-b(u-s)} dB_s du \right) \middle| \mathcal{F}_t \right] \\ &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \ \cdot \exp \left( \int^t_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \right) \\ && \ E \left[ \exp \left( \int^T_t \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s \right) \middle| \mathcal{F}_t \right] \end{eqnarray}$$

• Here, use the following formula. $$\begin{eqnarray} E\left[ \exp \left( \int^T_t f(s) dB_s \right) \middle| \mathcal{F}_t \right] = \exp \left( \frac{1}{2} \int^T_t f(s)^2 ds \right) \end{eqnarray}$$

• Therefore, $$\begin{eqnarray} P(t, T) &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \ \cdot \exp \left( \int^t_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \right) \\ && \ E \left[ \exp \left( \int^T_t \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s \right) \middle| \mathcal{F}_t \right] \\ &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \ \cdot \exp \left( \int^t_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \right) \\ && \ \cdot \exp \left( \frac{1}{2} \int^T_t \frac{ \sigma^2 }{b^2} \left( e^{-b(T-s)} -1 \right)^2 ds \right) \end{eqnarray}$$

• One computes the exponential part with letting it $$\mathscr{P}(t, T, r)$$. $$\begin{eqnarray} \mathscr{P}(t, T, r) &=& \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \nonumber \\ && \qquad + \int^t_0 \frac{ \sigma }{b} \left( e^{-b(T-s)} -1 \right) dB_s - \int^t_0 \frac{ \sigma }{b} \left( e^{-b(t-s)} -1 \right) dB_s \nonumber \\ && \qquad + \frac{1}{2} \int^T_t \frac{ \sigma^2 }{b^2} \left( e^{-b(T-s)} -1 \right)^2 ds \\ &=& \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \nonumber \\ && \qquad + \int^t_0 \frac{ \sigma }{b} e^{-b(T-s)} dB_s - \int^t_0 \frac{ \sigma }{b} e^{-b(t-s)} dB_s \nonumber \\ && \qquad + \frac{ \sigma^2 }{2b^2} \int^T_t \left( e^{-2b(T-s)} -2e^{-b(T-s)} + 1 \right) ds \\ &=& \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \nonumber \\ && \qquad + \frac{1}{b} e^{-bT} e^{bt}\int^t_0 \sigma e^{-b(t-s)} dB_s - \frac{1}{b} \int^t_0 \sigma e^{-b(t-s)} dB_s \nonumber \\ && \qquad + \frac{ \sigma^2 }{2b^2} \left[ \frac{1}{2b} e^{-2b(T-s)} - \frac{2}{b} e^{-b(T-s)} + s \right]^T_t \end{eqnarray}$$

• Here, use the result. $$\begin{eqnarray} \sigma \int^t_0 e^{-b(t-s)} dB_s &=& r_t - e^{-bt} r_0 \\ \mathscr{P}(t, T, r) &=& \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \nonumber \\ && \qquad + \frac{1}{b} e^{-bT} e^{bt}\int^t_0 \sigma e^{-b(t-s)} dB_s - \frac{1}{b} \int^t_0 \sigma e^{-b(t-s)} dB_s \nonumber \\ && \qquad + \frac{ \sigma^2 }{2b^2} \left[ \frac{1}{2b} e^{-2b(T-s)} - \frac{2}{b} e^{-b(T-s)} + s \right]^T_t \\ &=& \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \nonumber \\ && \qquad + \frac{1}{b} e^{-b(T-t)} (r_t - e^{-bt} r_0 )- \frac{1}{b} (r_t - e^{-bt} r_0 ) \nonumber \\ && \qquad + \frac{ \sigma^2 }{2b^2} \frac{1}{2b} ( 1- e^{-2b(T-t)} ) \nonumber \\ && \qquad - \frac{ \sigma^2 }{2b^2} \frac{2}{b} ( 1- e^{-b(T-t)} ) + \frac{ \sigma^2 }{2b^2} (T-t) \end{eqnarray}$$

• Substitute the above results into the exponential part. Hence, one reaches the following result for $$P(t, T)$$. $$\begin{eqnarray} P(t, T) &=& \exp \left( \frac{r_0}{b} (e^{-bT} -e^{-bt} ) \right) \nonumber \\ && \qquad \cdot \exp \left( \frac{1}{b} e^{-b(T-t)} (r_t - e^{-bt} r_0 )- \frac{1}{b} (r_t - e^{-bt} r_0 ) \right) \nonumber \\ && \qquad \cdot \exp \left(\frac{ \sigma^2 }{4b^3} ( 1- e^{-2b(T-t)} ) \nonumber \right) \\ && \qquad \cdot \exp \left( -\frac{ \sigma^2 }{b^3} ( 1- e^{-b(T-t)} ) + \frac{ \sigma^2 }{2b^2} (T-t) \right) \end{eqnarray}$$

• Recall the definition of the forward rate $$f(t, T, S)$$. $$\begin{eqnarray} f(t, T, S) &\equiv& - \frac{ \log P(t, S) - \log P(t, T)}{S-T} \\ f(t, T_1, T_2) &\equiv& - \frac{ \log P(t, T_2) - \log P(t, T_1)}{T_2-T_1} \end{eqnarray}$$

• Here, one reaches $$-\log P(t, T_2)$$. $$\begin{eqnarray} -\log P(t, T_2) &=& - \frac{r_0}{b} e^{-bT_2} + \frac{r_0}{b} e^{-bt} -\frac{1}{b} e^{-b(T_2-t)} r_t + \frac{1}{b} e^{-b(T_2-t)} e^{-bt} r_0 \nonumber \\ && \qquad + \frac{1}{b} r_t - \frac{1}{b} e^{-bt} r_0 - \frac{\sigma^2}{4b^3} + \frac{\sigma^2}{4b^3} e^{-2b(T_2 -t)} \nonumber \\ && \qquad + \frac{\sigma^2}{b^3} -\frac{\sigma^2}{b^3}e^{-b(T_2 -t)} - \frac{\sigma^2}{2b^2} T_2 + \frac{\sigma^2}{2b^2} t \\ &=& - \frac{r_0}{b} e^{-bT_2} + \frac{r_0}{b} e^{-bt} -\frac{1}{b} e^{-b(T_2-t)} r_t + \frac{1}{b} e^{-bT_2} r_0 \nonumber \\ && \qquad + \frac{1}{b} r_t - \frac{1}{b} e^{-bt} r_0 - \frac{\sigma^2}{4b^3} + \frac{\sigma^2}{4b^3} e^{-2b(T_2 -t)} \nonumber \\ && \qquad + \frac{\sigma^2}{b^3} -\frac{\sigma^2}{b^3}e^{-b(T_2 -t)} - \frac{\sigma^2}{2b^2} T_2 + \frac{\sigma^2}{2b^2} t \end{eqnarray}$$

• Moreover, one reaches $$\log P(t, T_1)$$. $$\begin{eqnarray} \log P(t, T_1) &=& \frac{r_0}{b} e^{-bT_1} - \frac{r_0}{b} e^{-bt} + \frac{1}{b} e^{-b(T_1-t)} r_t - \frac{1}{b} e^{-bT_1} r_0 \nonumber \\ && \qquad - \frac{1}{b} r_t + \frac{1}{b} e^{-bt} r_0 + \frac{\sigma^2}{4b^3} - \frac{\sigma^2}{4b^3} e^{-2b(T_1 -t)} \nonumber \\ && \qquad - \frac{\sigma^2}{b^3} + \frac{\sigma^2}{b^3}e^{-b(T_1 -t)} + \frac{\sigma^2}{2b^2} T_1 - \frac{\sigma^2}{2b^2} t \end{eqnarray}$$

• Therefore, one reaches the following equation. $$\begin{eqnarray} -\log P(t, T_2) + \log P(t, T_1) &=& - \frac{r_t}{b} ( e^{-b(T_2-t)} - e^{-b(T_1-t)} ) \nonumber \\ && \qquad + \frac{\sigma^2}{4b^3} ( e^{-2b(T_2-t)} - e^{-2b(T_1-t)} ) \nonumber \\ && \qquad - \frac{\sigma^2}{b^3} ( e^{-b(T_2-t)} - e^{-b(T_1-t)} ) \nonumber \\ && \qquad - \frac{\sigma^2}{2b^2} (T_2 -T_1) \\ &=& - \frac{\sigma^2}{2b^2} (T_2 -T_1) \nonumber \\ && \qquad - \left( \frac{r_t}{b} + \frac{\sigma^2}{b^3} \right) ( e^{-b(T_2-t)} - e^{-b(T_1-t)} ) \nonumber \\ && \qquad + \frac{\sigma^2}{4b^3} ( e^{-2b(T_2-t)} - e^{-2b(T_1-t)} ) \end{eqnarray}$$

• Hence, substitute the above result into the definition of the forward rate $$f(t, T_1, T_2)$$. $$\begin{eqnarray} f(t, T_1, T_2) &\equiv& - \frac{ \log P(t, T_2) - \log P(t, T_1)}{T_2-T_1} \\ &=& - \frac{\sigma^2}{2b^2} - \frac{1}{T_2 -T_1 } \left( \frac{r_t}{b} + \frac{\sigma^2}{b^3} \right) ( e^{-b(T_2-t)} - e^{-b(T_1-t)} ) \nonumber \\ && \qquad + \frac{1}{T_2 -T_1 } \frac{\sigma^2}{4b^3} ( e^{-2b(T_2-t)} - e^{-2b(T_1-t)} ) \end{eqnarray}$$

$$\square$$