All posts by Jérémie Smaga

C# Parallel Processing for Stock Paths simulation

Good evening everyone!

2013 hasn’t started very well for me as I’ve been sick for the past week and completely unable to work on anything even on a bit of CFA. Thankfully, I’m now starting to get better and I can again put a few words – or pieces of code – together.

I decided to write this quick post because my fiancee’s sister Elsa forwarded me a few questions she had about the material of an exam she had this morning in Embedded Systems. As you might guess, some of the material was dedicated to handling concurrency issues which made me realize that I never discussed parallel programming in C#.

Besides, I just bought a brand new laptop as my previous one was really looking like it was going to die any minute and, without a computer to play around with, I would really be like a professional hockey player without a stick  (I hope you like the metaphor). As a matter of fact, this new computer (an Asus G55V) is quite powerful: it has an Intel i7 2.4 Ghz processor with 12 GB of RAM. With this kind of setup, I should be able to run 7 computations at a time (using each of the 7 cores of the Intel i7). Cool huh?

Therefore, I decided to create a little, very simple example of parallel processing in C# applied to quantitative finance. The classic case of parallel processing in this field is usually referring to so-called Monte-Carlo simulations, where you simulate a very large amount of different paths for the price of a stock price according to a given model.

I will split this post in two distinct parts: the model and the simulation. For those of you who are not interested about the financial aspects of this post, feel free to just jump to Part II.

Part I : the model

Definition

I chose the model to be the Geometric Brownian Motion, which is used for the well-known Black-Scholes famework. The model states the dynamics of a price process $S_t$ as follows:

$$ dS_t = \mu S_t dt + \sigma S_t dW_t $$

Note that the return are intrinsically modeled like this:

$$\frac{dS_t}{S_t} = \mu dt + \sigma dW_t \sim \mathcal{N}(\mu ~ dt, \sigma^2 dt)$$

To simulate this price process using a programming language, I need to discretize the equation:

$$ \Delta S_t = S_{t + \Delta t} – S_t = \mu S_t \Delta t + \sigma S_t W_{\Delta t} $$

For simplicity’s sake, I’ll assume my model to be looking at daily prices and I will simulate prices every day so $\Delta t = 1$:

$$ \Delta S_t = S_{t + 1} – S_t = \mu S_t + \sigma S_t Z_t \quad \text{with} \quad Z_t \sim \mathcal{N}(0,1) $$

The implementation

The implementation is very simple: I created a very simple StockPath class which is supposed to simulate a the path of the prices of an arbitrary stock. I gave it the following private methods:

/// <summary>
/// Computes the change in price (delta S) between two points in the paths.
/// </summary>
/// <param name="currentStockPrice">The price of the stack at the first (known) point.</param>
/// <param name="randomNoise">The random noise used to estimate the change.</param>
/// <returns>The absolute change in price between two points according to the model.</returns>
/// <remarks>The underlying model assumes a geometric brownian motion.</remarks>
private double _computeStockPriceChange(double currentStockPrice, double randomNoise)
{
    return currentStockPrice * _mean * _timeInterval + _standardDeviation * currentStockPrice * randomNoise;
}

/// <summary>
/// Computes the next stock price given a <paramref name="currentStockPrice"/>.
/// </summary>
/// <param name="currentStockPrice">The price of the stack at the first (known) point.</param>
/// <param name="randomNoise">The random noise used to estimate the change.</param>
/// <returns>The next stock price according to the model. This value will never be less than 0.0.</returns>
/// <remarks>
/// The model makes sure that a price cannot actually go below 0.0.
/// The underlying model assumes a geometric brownian motion.
private double _computeNextStockPrice(double currentStockPrice, double randomNoise)
{
    return Math.Max(currentStockPrice + _computeStockPriceChange(currentStockPrice, randomNoise), 0.0);
}

Note that I also made sure that the stock price $S_t$ would never go below 0.0 (this is not the case in the mathematical model I stated above).

The computation of the path is performed using Math.Net library to generate the normal variables, and is done in the constructor:

/// <summary>
/// Initializes a stock path.
/// </summary>
/// <param name="nbrSteps">The number of steps in the path.</param>
/// <param name="mean">The mean of the returns.</param>
/// <param name="std">The standard deviation of the returns.</param>
/// <param name="timeInterval">The time between two evaluation points.</param>
/// <param name="initialPoint">The starting point of a path.</param>
public StockPath(int nbrSteps, double mean, double std, double timeInterval, double initialPoint)
{
	//Assigns internal setup variables
	_timeInterval = timeInterval;
	_mean = mean;
	_standardDeviation = std;

	//Using Math.Net library to compute the required random noise.
	Normal normal = Normal.WithMeanStdDev(0, 1);
	IEnumerable<double> returns = normal.Samples().Take(nbrSteps);

	//Explicit implementation of aggregation mechanism.
	_lastPrice = returns.Aggregate(initialPoint, _computeNextStockPrice);
}

Note that for simplicity and to diminish the computation time, I do not save each step of the price computation: I save only the last price.

Part II: simulation

For those of you who weren’t interested in the model specifics, this is where the main topic of this posts starts. We previously defined how we compute each path. The main problem with path computation is that you cannot parallelize it because you need to know $S_t$ to compute $S_{t+1}$. However, you can compute different paths in parallel, as they are completely independent from each other. To demonstrate the advantage of using parallel computations, I will want to simulate a very large amount of paths (100’000 of them) each of which will have 10 years of daily data (2520 points).

Why is it useful to compute the paths in parallel?

Let’s take a simple real-life example: cooking. Assume you invited a group of friends for dinner. You decided to have smoked salmon and toasts for appetizers and a pizza for the main. Now, what you would most probably do is prepare the pizza, put it in the oven, and while it is cooking, you would make the toasts, and while the toasts are in the toaster, you would put the salmon in a plate and so on. Once everything is done, you put everything in the table. In classic programming, you just cannot do that.

Haven’t we already been doing exactly that forever?

No, but everything was made to make you believe so. To keep it simple, a processor (CPU) can only do a single thing at a time: that is, if you were a processor, you would be stuck in front of the oven while the pizza is cooking. Some of you might argue that old computers (who had only a single CPU) managed to do several things at a time: you could still move the mouse or open a text editor while running an installation. That’s not really true! Actually, what the computer was doing was to alternate between different tasks. To come back to the kitchen example, if you were a computer, you could stop the oven, put the first glass on the table, switch back the oven, wait a little, stop the oven again, put the second glass on the table, restart the oven, wait again a little, and so on… This could look like you’re doing several things at the same time, but in fact, you’re splitting your time between several tasks. In short, a CPU performs computations sequentially. The problem with this “fake” parallelization is that although it looks like everything happens at the same time, you actually waste a lot of time because you can’t do many things at the same time.

What about today?

Modern computers are equipped with multiple cores. For example, my computer has an Intel i7 processor: it has 7 different cores that can process computations on their own. This means that you can compute 7 different things in parallel. They work as a team; for the kitchen example the team in the kitchen. This does not mean that I can compute anything in parallel, I need the tasks to be independent (at least to some extent). Now, this doesn’t mean that I can really compute things 7 times quicker. The reason for that is because the computer needs to perform some operations to make synchronize the results together once they are done. In the kitchen example, the team need to make sure that they do not do things recklessly; they need the plates to be ready at a given time; they need to organize themselves. Overall, there is an organisational overhead, but it is offset by the ability of being able to perform several things at the same time.

Is it difficult to perform parallel computations in C#?

There are several ways to perform parallel computing in C#. Today, I would like to discuss the simplest one: PLINQ. In my functional programming post,  I already showed how to use the classical LINQ framework to handle collections functionally. What is incredible about PLINQ is that it automatically handles the parallel aspect of collection operations after the function AsParallel() is called. So, first, I define a creator function which creates a new stock path for a given index (the index is actually useless in our case, but enables us to treat the computations functionally):

Func<int,StockPath> creator = x => new StockPath(nbrPoints, mean, stdDev);

What I want to do is to make sure that this creator is called in parallel several times. Here is now the function I implemented to run a simulation of several paths of a given amounts of points:

/// <summary>
/// Runs a simulation and prints results on the console.
/// </summary>
/// <param name="nbrPoints">The number of points for each path to be generated.</param>
/// <param name="nbrPaths">The number of paths to be generated.</param>
/// <param name="simulationName">The name of the simulation</param>
/// <param name="creator">The function used to create the <seealso cref="StockPath"/> from a given index.</param>
/// <param name="mode">The <see cref="Program.ExecutionMode"/></param>
public static void RunSimulation(int nbrPoints, int nbrPaths, string simulationName, Func<int,StockPath> creator, ExecutionMode mode)
{
	Stopwatch stopWatch = new Stopwatch();
	StockPath[] paths = new StockPath[nbrPaths];
	IEnumerable<int> indices = Enumerable.Range(0, nbrPaths - 1);
	Console.WriteLine("Starting " + simulationName + " simulation.");
	stopWatch.Start();

	switch (mode)
	{
		case ExecutionMode.CLASSIC:
			paths = indices.Select(creator).ToArray();
			break;
		case ExecutionMode.PARALLEL:
			paths = indices.AsParallel().Select(creator).ToArray();
			break;
		default:
			throw new ArgumentException("Unknown execution mode", "mode");
	}

	stopWatch.Stop();
	Console.WriteLine("End of " + simulationName + " simulation.");
	var lastPrices = paths.Select(x => x.LastPrice);
	Console.WriteLine("Min price: " + lastPrices.Min().ToString("N2"));
	Console.WriteLine("Max price: " + lastPrices.Max().ToString("N2"));
	Console.WriteLine("Computation time: " + stopWatch.Elapsed.TotalSeconds.ToString("N2") + " sec");
}

The two most important lines are the number #20 and #23. The rest of the function basically computes the executions time and prints the results on the console. Running the simulation in both modes (sequential and parallel) gives me the following results:

Execution mode Computation time
Sequential 32.33 sec
Parallel 06.29 sec

As you can see, running the paths in parallel improved greatly the computation time of the simulation; it’s about 5 times quicker. As expected, we did not perform 7 times better (the number of available cores) because we had to do the extra background work of synchronizing the results at the end of the computation.

Summary

Given the extreme simplicity (only adding the AsParallel() call) of the code to get into parallel mode, using PLINQ seems to be a very good and very accessible solution for simple cases such as this one.

Of course the performance will vary with the processor being used but in general, I would recommend using this PLINQ solution. There are a few important things to think about when using parallelism: think about whether it is really useful:

  • Are the computations really independent?
  • Are there enough computations to compensate for the extra work required to synchronize the results?

The whole project is available on my GitHub account here: https://github.com/SRKX/ParallelStockPaths.

I hope you enjoyed the demo,

See you next time,

Jeremie

Your chance to get to know Game Theory!


Warning: DOMDocument::loadXML(): Space required after the Public Identifier in Entity, line: 1 in /home/clients/d6bcc13f01d956648e26ee7f6a76facd/blog/wp-content/plugins/wordpress-amazon-associate/APaPi/AmazonProduct/Result.php on line 149

Warning: DOMDocument::loadXML(): SystemLiteral " or ' expected in Entity, line: 1 in /home/clients/d6bcc13f01d956648e26ee7f6a76facd/blog/wp-content/plugins/wordpress-amazon-associate/APaPi/AmazonProduct/Result.php on line 149

Warning: DOMDocument::loadXML(): SYSTEM or PUBLIC, the URI is missing in Entity, line: 1 in /home/clients/d6bcc13f01d956648e26ee7f6a76facd/blog/wp-content/plugins/wordpress-amazon-associate/APaPi/AmazonProduct/Result.php on line 149

Warning: Invalid argument supplied for foreach() in /home/clients/d6bcc13f01d956648e26ee7f6a76facd/blog/wp-content/plugins/wordpress-amazon-associate/APaPi/AmazonProduct/Result.php on line 160

Good evening,

There is a section in this blog that I haven’t been able to fill with new content for a long time: the part dedicated to Game Theory. The main reason is that I’m not using that field in my day-to-day job, so it’s a bit difficult to find good and accessible topics to discuss here.

However, I have good news for those of you who are eager to discover more about this topic. A few months ago, I told you about Coursera in this post. For those of you who missed it, Coursera provides users with free high quality online classes from top-tier universities.

By now, you probably guessed what this post is all about! As a matter of fact, starting January 7th 2013, there will be a Game Theory from Stanford University available to us. You can check out all the details and register for the class on the official page. Here is the abstract of the class:

Popularized by movies such as “A Beautiful Mind”, game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call ‘games’ in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model eBay, Google keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We’ll include a variety of examples including classic games and a few applications.

For those of you who haven’t seen the movie “A beautiful mind” yet, I strongly encourage you to do it, and if you’re not yet convinced, here is the trailer:

[youtube:http://www.youtube.com/watch?v=Q3G9lnyXJGU&rel=0]

About the class itself, the description says it is based on a book I extensively used for my paper on Penalty Shots in Ice Hockey, and which is available on Amazon:

Essentials of Game Theory: A Concise, Multidisciplinary Introduction (Synthesis Lectures on Artificial Intelligence and Machine Learning)

Both authos, Kevin Leyton-Brown and Yoav Shoham are two leading contributors of the game theory field and they are both professors of the class. Hence, I can’t emphasize enough how good I think this class will be.

I do not expect I will be available to take all the exercises because my spare time will be mainly dedicated to the CFA Level II (see the countdown at the top of the menu on the right), but if you wish to do so, don’t forget you can get a certificate of completion.

That’s it for now! Please let me know what you think of the class!

See you next time!

What’s up? What’s next?

Good afternoon everyone,

I decided to write a very quick post since I haven’t been posting much lately, for several reasons.

As a matter of fact, I’ve been pretty busy at work and my mind was always caught between two thoughts so it’s been difficult for me to come up with complete posts. However, I have started a few of them and they’re now waiting in my drafts section; they just need to be polished a bit. So, there is content ready to be coming your way quite soon during this holidays period.

A few weeks ago, I received the Schweser books for the CFA Level II and I am just starting to have covered enough material to produce my first post about this year’s program so it should appear online rather sooner than later. In order to keep in mind the time left before the exam on June 1st 2013, I decided to put a countdown at the top of the menu on the right hand side of the blog. Hopefully this will help me staying motivated during the next 5 months.

Anyway, I don’t know if I’ll have the time to write my wishes for 2013 – although I’ll try to – so I take the opportunity to wish you all a merry Christmas and a very happy new year 2013!

See you next time,

Jeremie

Free top quality online classes

Good afternoon everyone!

I decided today to take the opportunity to write this post about a new resource I discovered a few month ago and which I have been using ever since then, Coursera.

The idea behind Coursera is to provide free online video classes to be accessed by students all over the world at any time, for free. The first question that storms to mind is What kind of class does it provide?. I’d say that the scope would be anything that you can learn in an Undergraduate program and beyond (Graduate, Phd, …), and that’s the beauty of it. The second question is Who’s teaching the class? Well fasten you seat belts, because here is the answer:

United States

  • Stanford University
  • Princeton University
  • University of Michigan
  • University of Pennsylvania
  • University of Virginia
  • University of Washington
  • University of Illinois at Urbana-Champaign
  • University of California, San Francisco
  • California Institute of Technology
  • Duke University
  • Georgia Institute of Technology
  • John Hopkins University
  • Rice University

Canada

  • University of Toronto

Scotland:

  • University of Edinburgh

Switzerland:

  • Ecole Polytechnique Federale de Lausanne (EPFL)

Yes, it is astonishing. Don’t even try to think that the universities sent second-zone professors to use the tool, first class academics are teaching you the material through the video as if it was a 1-to-1 session. To name a few, and mostly because they are the one I knew or heard of before discovering the website:

  • Andrew NG (Stanford, Co-founder of Coursera), teaching Machine Learning
  • Dan Boneh (Stanford) teaching Cryptography
  • Martin Odersky (EPFL, whom I have the chance to know) teaching Functional programming

As I mentioned, the scope of the classes is very broad. The first courses that got my attention were focused on computer science and statistics (I’ll come back to the one I took or am planning to take), but I saw medical schools classes, history, mathematics, social engineering, and I believe there is and will be more.

The format of each class is similar and particularly brilliant. The curriculum is split week by week  each of which have particular topic. Your are provided with a series of short videos (called segments) 5 to 25 minutes long from what I’ve seen, which makes it particularly convenient for user who have a day job or students which are already following a heavy program. Each segment will typically start with an introduction where you will see the professor and then switches to displaying slides which are dynamically annotated by the professor while he speaks. Even better, the annotated slides are available from download before the class starts, so you can literally feel as if you were in the classroom although you are … at home.

Another great aspects on Coursera is that it is interactive. During a video, the professor can pause the cast and ask a question to which the viewer can answer either by choosing between several options or by filling in a specific value and then validate. This is not blocking (you can skip the question) but is pretty handy to check whether you understood what was said thus far in the lecture. Most importantly each week is accompanied with an exercise set which is graded (I’ll come back to the grading mechanism) and which also works either on plain value filling or multiple choice picking. Extra assignments for extra points can require either submitting answers to challenging problem or even code (I’ve never done it though).

As I mentioned, the exercises sets are graded and each course ends up with a final exam. If you successfully complete the assignments and the final, you will the “pass” the class and receive a certificate of completion (I think this depends on the class, but all the ones I’ve taken so far provided that option). As certification is purely optional you can enroll to a course and basically just watch the videos, or the specific part you’re interested in.

Finally, I want to share the different courses I enrolled in:

  • Machine Learning
  • Gamification
  • Model Thinking
  • Neural Networks for Machine Learning
  • Probabilistic Graphical Models
  • An introduction to interactive programming using Python
  • Cryptography
  • Basic Behavioral Neurology
  • Computational Investing Part I

To sum up, Coursera is free, interactive, and can provide certification upon completion of assignments and a final exam. Try it out!

See you soon!

You got mail: CFA Level I results….

Good afternoon everyone,

After yesterday night’s post on a somewhat soft topic, let’s get back to business with the CFA exam results I received today.

Let’s kill the suspense straightaway! I am delighted to be able to say that I passed my Level I exam. That’s great news and it’s a huge relief as I am always unsure of the outcome of this kind of exams.

The CFA institute does not provide you with your exact score but rather gives you a range of success ratio for each specific topic.

Unsurprisingly, I didn’t manage to do more than 50% in Economics as the topic is very broad relative to the number of questions that are actually asked, but I’ll try to work on that a bit during this summer. That was for the weak range.

Then comes what I’d call the middle range with 51% – 70% success ratio within which my scores in Derivatives, Fixed Income and Quantitative Methods all lied. That might come as a surprise for some of you as they should be some of my strongest topics, but I think it can be explained by the kind of questions that were asked during the exam. Indeed, questions in these topics were not very quantitative and sometimes relied on terminology or specific definitions. I guess this is where I lost my points because I am fairly confident of the computations I performed.

My scores for the remaining topics ended up in the upper bracket with more than 70% success ratio. I am pretty happy about this because it seems that I got the feeling right in Ethics which is a topic which requires practice, practice and… practice. I’m particularly satisfied to have obtained such a score in Accounting as it is a key topic in the Level I curriculum because of the number of question being asked about it in the exam. I must say, I felt most Accounting questions were really doable since difficult topics such as deferred tax assets/liabilities were represented with relatively easy (or at least quite straightforward) questions.

To sum up my Level I experience, and as I had the time to look back at what I did before they exam and how it paid up, I would like to highlight the importance of having the Schweser notes and particularly the Schweser QBank (the tool which contains tons of practice questions for each topic). Practicing questions definitely looks to be the right way to be successful in the exam, at least for people with a professional activity during the day who have less time available for the exam. Focusing on the key exercise types where easy points can be made by remembering a formula (or at least a process) proved to be a very useful technique at the exam as it secures points, saves time and provides confidence.

I would like to end this post with a word of thanks for those who supported me during my journey towards this CFA Level I exam success. First of all, I would like to thank Unigestion, the company I work for, for trusting me and supporting me as well as providing me with some extra training time. In particular, I would like to thank Pierre Bonart who encouraged me to start this curriculum and who provided me with great advises and showed so much support. I would also like to thank my family and my girlfriend Sarah for helping me mentally and for standing by me during the difficult and stressful pre-exam days and for their great understanding during the whole preparation process.

Finally, I want to underline that I do know that the road to the CFA is far from over, and that this was maybe the easiest step towards the designation. I will be back with more CFA content, this time concerning Level II material, when I receive the new set of notes for the next challenge in June 2013.