What is the Markowitz model and why is the Mean-Variance-Skewness-Kurtosis model better?

Let’s suppose that you have managed, agianst all the expectation, to climb out of debt and the hand-to-mouth lifestyle. You listened to Minority Mindset, settled your high interest loans and built up a cash safety cushion. You have a few pennies spare and decide to invest in stocks. Fire up the old online brokerage, scan for the highest returns stock you can recognize and sink all your funds into it. A few days pass, you check up on your investment only to see red. You bought high and the price is down along with your will to exist.

Assuming you don’t quit, you learn of something called “diversification”. The idea is to buy stocks that don’t rise and, more importantly, don’t fall all at the same time. But how do I know if stocks are casually linked in such a manner? You don’t, it’s too hard to answer, so we answer an easier question, hoping that it has bearing on the original. We check to see to what extent the returns on our various stocks correlate. The idea now is to get the right mixture of stocks in your portfolio to minimize the total variance of the mix while getting some nice returns.

Enter the Markowitz model for portfolio optimization. Back in the 1950’s a guy called Harry Markowitz modeled the problem of portfolio optimization as

Where

  • \lambda \in [0,1] models your risk aversion. 0 if you don’t care about returns you just want to minimize variability. 1 if you are all in on returns, variance be damned. Note if you choose this path you end up where we began in the first paragraph, sinking all your money into a single stock.
  • \mu := \mathbb{E}[r] where r is the returns data matrix. Thus, \mu, is just the average returns for each of your stocks.
  • V:= \mathbb{E}[(r-\mu)(r-\mu)^T] is the covariance matrix of your portfolio.
  • w is the the weight allocation of your portfolio, i.e. w_i is the percentage of your current total portfolio value that comes from the i^{\mathrm{th}} stock.

The model is predicated on a few assumptions that have been shown not to hold in reality but don’t let that stop you from throwing your hard earned money away. I highlight only two assumptions:

  1. The underlying distribution of your stock returns is Gaussian.
  2. The variance of your portfolio is a proxy for risk and minimizing it should make you safer.

If you want to know more about the topic of risk but you don’t want to touch math. I refer you to Nicholas Nassim Taleb and his many great books.

Assuming you still want to go through with this how do you solve (MV)? Simple just solve the optimization problems and recover the maximizers w. It’s not that simple. Quadratic programs contain the max-cut problem and are hence NP-hard to solve. Which is the math way of saying you may have to wait a while for your computer to solve the problem. However, there are techniques and computational approaches around this but that is for another video. Let us assume you get through all of that. Are you done now? nope.

The Markowitz model consider exceptionally bad (or good) returns more unlikely than they really are. There is no account for fat tails. As a result your portfolio is at risk that you don’t know about.

So what are “fat-tails”? First, in case you missed it, the tapering ends of the Gaussian distribution are called tails, don’t ask me why. When either of them is fat it indicates that the likelihood of events occurring there is higher than expected using only the pure Gaussian. What does this mean to you. It means that you could experience heavy losses more often than you had planned for. In the world of finance this could ruin you on all levels of existence.

Don’t despair, we can extend the Markowitz model by including what are called higher order moments namely skewness and kurtosis. The skewness of can be seen as a leaning to one side or the other, see the gif below. Kurtosis is a bit harder to visualize but it is contributes fatter tails. In general investors want more positive skewness and no kurtosis.

So the optimization problem becomes.

Where :

  • \Phi := \mathbb{E}[(r-\mu )((r-\mu )\otimes(r-\mu ))^T] is the centralized skewness matrix.
  • \mu := \mathbb{E}[[(r-\mu )((r-\mu )\otimes (r-\mu ) \otimes (r-\mu))^T] is the centralized kurtosis matrix.

This is called the Mean-Variance-Skewness-Kurtosis model and it is a polynomial goal programming problem. It is not any easier than the (MV) model. It does account for fatter tails. Next times I’ll show you how to solve this (approximately) and use it to “optimize” a portfolio. Until then stay well and keep improving.

P.S. If you have a math topic with practical relevance that you would like me to address please send me a mail.

Jerry-Rigging LaTeX Macros in Obsidian Markdown

Obsidian is a a great tool for taking notes. One of its best features is that it supports LaTeX via MathJax. Essentially LaTeX is a type setting program that is often used in academia to create documents with many funny symbols and equations. MathJax is a JavaScript display engine that allows you to see Latex inside Obsidian.

Suppose you are doing research, you stumble upon an equation and you would like to add it to your notes. The quick and dirty approach would be to take a screenshot and just link it as an image. Like this:

This is unsatisfactory for at least two reasons. First, you have to keep that screenshot around adding to the file clutter. Second, you can’t modify the equation. So how to add the equation in properly? You can use the inbuilt LateX of Obsidian as follows:

\begin{align*} 
    \xi_t^{sep}(\rho) := \inf \Big\{ L(1) ~|~ &L: \mathbb{C}
    [\mathbf{x},\bar{\mathbf{x}},\mathbf{y},\bar{\mathbf{y}}]_{2t}
     \ \text{ s.t. }  \\ 
    & L(\bar{p}) = \overline{L(p)} ~~~\forall~~ p \in \mathbb{C}
    [\mathbf{x},\bar{\mathbf{x}},\mathbf{y},\bar{\mathbf{y}}]\\
    & L(\mathbf{x}\bar{\mathbf{x}}^*\otimes \mathbf{y}\bar{\mathbf{y}}^*) = \rho,  \\
    & L \geq 0 \text{ on }  \mathcal{M}_{2t}(S_\rho),  \\
    & M_{t-2}(G\otimes L)=L(G \otimes 
    [\mathbf{x},\bar{\mathbf{x}},\mathbf{y},\bar{\mathbf{y}}]_{t-2} 
    [\mathbf{x},\bar{\mathbf{x}},\mathbf{y},\bar{\mathbf{y}}]_{t-2}^*) \succeq 0\Big\}.
\end{align*}

This looks good. However, the code is bloated and it is a pain to write \mathbb{R} every time you invoke the reals. LaTeX addresses this with macro’s. The idea is that you encode your own LeTeX commands that are local to your document. Like encoding \mathbb{R} as \R. Doing this for the equation we get:

\newcommand{\C}{\mathbb C}                   
\newcommand{\xidsep}[1]{\xi_{#1}^{\mathrm{sep}}(\rho)}
\newcommand{\bx}{\mathbf{x}}                    
\newcommand{\bbx}{\bar{\mathbf{x}}}             
\newcommand{\by}{\mathbf{y}} 
\newcommand{\bby}{\bar{\mathbf{y}}}             
\newcommand{\monoV}{[\bx,\by,\bbx,\bby]}       
\newcommand{\polyS}{\C\monoV}                    
\newcommand{\calM}{\mathcal {M}}                 

\begin{align*} 
    \xidsep{t} := \inf \Big\{ L(1) ~|~ &L: \polyS_{2t}\to\C \ \text{ s.t. }  \\ 
    & L(\bar{p}) = \overline{L(p)} ~~~\forall~~ p \in \polyS\\
    & L(\bx\bx^*\otimes \by\by^*) = \rho,  \\
    & L \geq 0 \text{ on }  \calM_{2t}(S_\rho),  \\
    & M_{t-2}(G\otimes L)=L(G \otimes \monoV_{t-2} \monoV_{t-2}^*) \succeq 0\Big\}.
\end{align*}

We cleaned up the equation at the cost of those 9 extra lines where we define new LaTeX commands. To get the effect of the macros throughout your vault I have found a trick. You make a note that has all of the macros you want, (mine is called “THE GRAND TEX”). Then you just open it and close it once and then carry on as usual. That is all. I suppose behind the scenes all the macros are loaded into MathJax and you just use them in the notes without having to redefine the macros. This lasts for the duration of the Obsidian session. You can then view and print your pretty math symbols.

To conclude we have seen how to define LateX macros globally in an Obsidian vault.

Graph representation of mathematical statement dependencies part 1

The idea in short

In mathematics, greater results like theorems build on lesser results like lemmas.
In this post we ask if it is possible to represent result dependencies via a directed graph using Julia.


Introduction.

In this world there is an abundance of information but a dearth of insight. One way to separate the wheat from the chaff is to use meta information. The idea is that one can use information about information to gauge the value of the original info. without parsing it. This can you save you time by judiciously deciding whether you want to invest attention or not.

Examples of meta information are: Keywords, Google ranking, Citations, links and a variety of other parameters. There is also a plethora of nice visualization techniques, each trying to simplify the overall picture. This post is about the latter.


Our specific problem

This post will address the task of mapping the dependencies among statements in mathematics papers. What do I mean by this? In a mathematics paper the key points of interest are the results namely: Theorems, Lemmas, Corollaries, Examples Equations etc… These often build on top of each other and external results, i.e, references to results in other papers. Big results are often preceded by several smaller results each of which building on preceding ones. For example: consider the excerpt from the paper Solving moment problems by dimensional extension


This result contains in its proof reference to two previous results in the same paper and one external reference.

As the reader can see mathematics is quite terse and requires time to parse. Hence, one must decide if the the task is worth the effort. This then entails asking what is the effort? and what is the worth? Worth is somewhat subjective but we can use proxies to get a handle on it. The idea is that worthwhile results have many uses, i.e., are referenced a lot by other results. To gauge effort one can use the number of external results that are invoked. A way to see these referencing and dependencies is to use a diagram. Note: these proxies are by no means satisfactory on their own. One would have to use them in conjunction with other methods and a good helping of commonsense.

Another question could be: where to start parsing the paper? Often the best place to start parsing a research paper is not the beginning. The reason being that you could get bogged down with stuff you already know. This is because good writing often eases the reader into the topic. Which is good if your are somewhat new but a waste of time if you are familiar with the subject. At the same time you may not want to jump into the deep end only to backtrack looking for the requisite arguments that you skipped.

In this post we pose the idea of using a graphical representation of the dependencies of results. Using this hopefully confers the following:

  1. An idea of the overall structure
  2. Which results have most subsidiaries
  3. Which references are key to main proofs (without having to look at the proof)

I imagine a diagram like the following:

Let us unpack what the above image tells us:

  • The circle represents the paper, inside it are internal statements and outside it external statements from other sources.
  • The segments represents the sections of the paper: Introduction, Section 1 etc…
  • Internal results are represented nodes:
    • The shape of the node determines the type
    • The arcs between nodes show the direction of the dependency.
    • Note: that cycles and double arrow are not an indication of circular logic but rather of equivalences between statements. There are some philosophical discourses on the fact that mathematics does not need a base truth

” Pure mathematics consists entirely of assertions to the effect that, if such and such a proposition is true of anything, then such and such another proposition is true of that thing. It is essential not to discuss whether the first proposition is really true, and not to mention what the anything is, of which it is supposed to be true. […] Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. People who have been puzzled by the beginnings of mathematics will, I hope, find comfort in this definition, and will probably agree that it is accurate.”

Bertrand Russell, Mysticism and Logic

  • All the nodes outside the circle are external papers
    • The arcs leading from outside into the circle means that they are cited there.

An idea to make such a diagram

Now if you were to construct such a map for a math document “by hand” you would have to parse the document and hence defeat many of the purposes of having such a diagram. Hence, we will see if we can make a machine do it.

I’ll assume that the input is a .pdf from ArxiV. The plan is as follows.

To the best of my knowledge there is no program that does this. Hence, I am coding a crude prototype on github

How do I plan to do this? in a nutshell.

  1. I use Wondershare PDFelement to convert the .pdf to .txt.
  2. I use Regex to extract the results based on known features.
  3. The dependencies are found by examining whether the previous result-regex appears in a block of text associated with the current result.
  4. To construct the diagram I plan to use mermaid, the same thing I used to make the above flow chart.

Closing

Hopefully I have nudged you the reader to be more favourable of these graphical representations and perked your interest. It is my goal to post on this blog weekly. So hopefully I can continue this topic next week.

GETTING SOME EXAMPLE GRAPHS (UNDIRECTED) USING JULIA PACKAGES AND WEB SCRAPING.

One of the core tasks in mathematics is the application of new techniques to known examples in order to investigate both.
In this post we will gather graphs using [Julia]():

Intro

Along with matrices, graphs are widely used to represent relational data. The structure of a graph, i.e. which vertices are connected via edges, determine its properties. These properties often take the form of graph parameters, e.g., regularity, stability number, colouring number. Computing these parameters efficiently is of great interest in industry and academia.

Sometimes a new graph parameter is created/discovered through research. One would then like to see what values it takes for some of the familiar graphs. Which brings us to this post. Imagine you are a curious researcher and you want some graphs to play around with. Where do you get some interesting graphs (well interest is subjective but bare with me)?
You could generate graphs randomly.

Getting inbuilt graphs from packages.

Consider the following Julia packages pertaining to graphs:

Using these packages we can generate random undirected graphs as follows:

using LightGraphs
using GraphPlot

using Cairo # used to render the plot as png
using Compose # used to render the plot as png

nb_vert    = 10
frac_edges = 0.35
nb_edge    = Int(round(frac_edges*binomial(n,2)))
G          = Graph(nb_vert, nb_edge)
Gplt = gplot(G, nodelabel = string.(["v"],1:nb_vert)) # to view


draw(PNG("Random_Graph_n$nb_vert"*"m$nb_edge.png", 16cm, 16cm), Gplt)

The resulting graph in my case was (note this may differ for you as a random seed was not fixed).

Now random graphs may not be what we are looking for. We may be interested in well studdied graph with certain properties. Fortunately LightGraphs.jl also contains many small graph examples:

SymbolDescription
:bullbull graph.
:chvatalChvátal graph.
:cubicalPlatonic cubical graph.
:desarguesDesarguesgraph.
:diamonddiamond graph.
:dodecahedralPlatonic dodecahedral graph.
:fruchtFrucht graph.
:heawoodHeawood graph.
:housegraph mimicing the classic outline of a house.
:housexhouse graph, with two edges crossing the bottom square.
:icosahedralPlatonic icosahedral graph.
:karatesocial network graph called Zachary’s karate club.
:krackhardtkiteKrackhardt-Kite social network graph.
:moebiuskantorMöbius-Kantor graph.
:octahedralPlatonic octahedral graph.
:pappusPappus graph.
:petersenPetersen graph.
:sedgewickmazesimple maze graph used in Sedgewick’s Algorithms in C++: Graph Algorithms (3rd ed.)
:tetrahedralPlatonic tetrahedral graph.
:truncatedcubeskeleton of the truncated cube graph.
:truncatedtetrahedronskeleton of the truncated tetrahedron graph.
:truncatedtetrahedron_dirskeleton of the truncated tetrahedron digraph.
:tutteTutte graph.
G = smallgraph("tutte")
Gplt = gplot(G)
draw(PNG("tutte.png", 16cm, 16cm), Gplt)

So far we have only scratched the surface of JuliaGraphs.jl and its subsidiary packages. There are even more Julia packages out there for you to explore.

Scrapping graphs from online repositories.

Graph theory as you may know is a very rich branch of mathematics. As such, good work has been done on particular graphs and their properties. Here are a few repositories that collect special graphs and meta data on them:

Some of these are quite extensive and far exceed the purposes of a cursory experiment. Hence you may want to scrape only parts. Let’s jump right into it.

Scraping the name and link to graphs from Encyclopedia of Graphs.

**Caveat: Web scraping when done recklessly can slow the website down or crash it.
For this reason some websites disallow web scraping. I leave it to the reader to do their due diligence on the matter. I personally delay my requests by a random amount of seconds (see below).**

I will also make use of the following packages:

using HTTP
using Gumbo
using Cascadia

using CSV
using Pipe
using DataFrames

graph_dict = Dict()
for t in 1:9
    url = "http://atlas.gregas.eu/collections?page=$t"
    sleep(rand(3:20)) # Introduce a random delay before each request
    req = HTTP.get(url)
    h = parsehtml(String(req.body))
    qs = eachmatch(Selector("ul.results-listing"),h.root)
    qs1 = eachmatch(Selector("li"),qs[1])

    for q in qs1
        name_ref = eachmatch(Selector("a"), q)[1]
        ref      = "http://atlas.gregas.eu"*name_ref.attributes["href"]
        name     = name_ref.children[1].text
        graph_dict[name] = ref
    end
end
# Save what we have scraped
df = DataFrame(Any[collect(keys(graph_dict)), collect(values(graph_dict))], [:graph_name, :web_link])

The results (truncated) are:

graph_nameweb_link
Vertex-critical graphshttp://atlas.gregas.eu/collections/35
Countries of the worldhttp://atlas.gregas.eu/collections/49
Chordal graphshttp://atlas.gregas.eu/collections/48
2-arc-transitive tetravalent graphshttp://atlas.gregas.eu/collections/44
Planar graphshttp://atlas.gregas.eu/collections/34
Tetravalent graphshttp://atlas.gregas.eu/collections/59
Snarkshttp://atlas.gregas.eu/collections/24

Now it would be nice if we had a short description of what these graphs are.
Like what the hell is a “snark”?
So the plan is that we take each of the links in the above table, request it and scrape a description.
Here is how I did it:

description = []
for link in df.web_link
    r = HTTP.get(link)
    sleep(rand(3:10))
    h = parsehtml(String(r.body))
    qs = eachmatch(Selector("div#collection-view-description"),h.root)[1]
    qs1 = eachmatch(Selector("div"),qs)
    try
        push!(description, qs1[1].children[2].children[1].text)
    catch
        push!(description, "could not scrape.")
    end
end
description = get_descriptions(df)
df[:description] = description

The results (truncated) are:

graph_nameweb_linkDescription
Vertex-critical graphshttp://atlas.gregas.eu/collections/35A graph is said to be vertex-critical if its chromatic number drops whenever a vertex is deleted.
Countries of the worldhttp://atlas.gregas.eu/collections/49Could not scrape.
Chordal graphshttp://atlas.gregas.eu/collections/48A chordal graph is a simple graph in which every graph cycle of length four and greater has a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle
2-arc-transitive tetravalent graphshttp://atlas.gregas.eu/collections/44This collection contains a list of connected 2-arc-transitive tetravalent graphs on up to 2000 vertices. The list is complete on up to 727 vertices but
Planar graphshttp://atlas.gregas.eu/collections/34A planar graph is a graph that can be embedded in the plane, i.e. it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
Tetravalent graphshttp://atlas.gregas.eu/collections/59Tetravalent, quartic or 4-regular graphs are graphs where every vertex has degree 4. The following collection was calculated by The House of Graphs
Snarkshttp://atlas.gregas.eu/collections/24A snark is a connected bridgeless cubic graph (i.e., a biconnected cubic graph) with edge chromatic number of four (i.e. it cannot be properly edge-coloured using 3 colours).

Well, the results are somewhat mixed. The descriptions are sometimes on point and at other times I fail to scrape anything. Note: The code you write to scrape a website is highly dependent on the HTML structure of the website. So, don’t expect to have a “one size fits all” code.

Conclusion:

In summary we have touched on two methods for getting examples of graphs:
1. Inbuilt in Julia packages.
2. Web scraping.
All of which in a Julia environment. You have my thanks for reading and I hope that this post has set you on a journey of discovery. Coming soon: I plan to use this set of examples as sand in a sandbox to play with some techniques I have read about.