February | 2008 | Rod Carvalho

Archive for February, 2008

Rolling dice

February 28, 2008

You and I play a game. We each have 1 die. I win if I roll a 4. You win if you roll a 5. If I go first, what is the probability that I win?

Some quick remarks:

the game is over when I roll a 4 or when you roll a 5. Until that happens, the game is played ad infinitum.

the game is played in rounds. At each round, I roll the die, and only then you roll the die. If I get a 4, I win the game and you don’t get to roll your die.

the probability that I win is the same as the probability that you lose. And vice-versa.

if you go first, the probability that I win is different (of course).

note that there are two dice! However, since we roll the dice in a non-simultaneous manner, we actually only need one die. I can borrow yours, or lend you mine.

__________

The Dice Brain Teaser

Hat-tip: Nuclear Phynance

Tags:Games, Puzzles
Posted in Games, Puzzles | 6 Comments »

Optimal Downloading Strategies

February 24, 2008

Imagine that you go on a road trip with some friends. One of your friends has a video camera and films the best moments of the trip. After the trip, your friend edits the footage and creates a movie with the very best moments. Your friend could then burn a CD (or a DVD) containing the movie, and send it to you via post-mail. However, that solution involves:

wasting time to go to the mail office.

spending money on CD’s, stamps, and envelopes.

We could do better than that: why not compress the movie into one or more ZIP files and upload them to a hosting website such as Rapidshare? Bandwidth is cheap these days, and downloading involves only a few mouseclicks. Your friend uploads the ZIP files to a hosting website and sends you the list of URL’s via email, including the size of each file next to each URL. Let us assume that:

in this hosting website, you need to wait 1 minute for each MB you downloaded in the previous file download.

you need to download all ZIP files before you can unzip them and watch the movie your friend created.

You then think: “in which order should I download the files”? This is a decision problem under certainty. Let us try to model it!

__________

Mathematical Model

Let us say that we have a total of $n$ files to download, where $n \geq 2$ . We consider the following variables and parameters (and respective units):

$x_i$ : size of the $i$ -th file (unit: Megabytes).

$T_i^D$ : time it takes to download the $i$ -th file (unit: seconds).

$T_i^W$ : time one needs to wait after downloading the $i$ -th file (unit: seconds).

$R$ : downloading speed (unit: Megabytes per second)

for all $i \in \mathcal{I}$ , where $\mathcal{I} = \{1, 2, \dots, n\}$ . The time it takes to download the $i$ -th file is

$T_i^D = \displaystyle\frac{x_i}{R}$

and the time one needs to wait after downloading the $i$ -th file is

$T_i^W = 60 x_i$ .

The total downloading time is the sum of each file’s downloading time plus the time one needs to wait after downloading each file. Note that after we download the last file, we can unzip the $n$ files and obtain the full-length movie. Therefore, when counting the total downloading time, we do not need to include the waiting time of the last downloaded file. Let us denote by $j \in \mathcal{I}$ the index of the last downloaded file. Thus, the total downloading time is

$T = \displaystyle\sum_{i \in \mathcal{I}} T_i^D + \displaystyle\sum_{i \in \mathcal{I} \setminus \{j\} } T_i^W$ ,

which can also be written as

$T = \displaystyle\sum_{i \in \mathcal{I}} \left(T_i^D + T_i^W\right) - T_j^W$ ,

or, then, as follows

$T = \left(60 + \frac{1}{R}\right)\displaystyle\sum_{i \in \mathcal{I}} x_i - 60 x_j$ .

__________

Optimal Downloading Strategies

Suppose that our objective is to minimize the total downloading time $T$ . Let us introduce the cost function $C: \mathcal{I} \to \mathbb{R}_0^+$ defined by

$C(j) = T = \left(60 + \frac{1}{R}\right)\displaystyle\sum_{i \in \mathcal{I}} x_i - 60 x_j$ .

Note that our decision variable is $j \in \mathcal{I}$ , i.e., our goal is to find the value of $j \in \mathcal{I}$ that minimizes the total downloading time $T$ . Note also that:

$\left(60 + \frac{1}{R}\right)\displaystyle\sum_{i \in \mathcal{I}} x_i$ is the “fixed cost”.

$\left(- 60 x_j \right)$ is the “variable cost”.

We cannot “control” the fixed cost, but we can try to minimize the variable cost. The minimal cost is thus

$C^* = \displaystyle\min_{j \in \mathcal{I}} C(j) = \left(60 + \frac{1}{R}\right)\displaystyle\sum_{i \in \mathcal{I}} x_i - \max_{j \in \mathcal{I}} \left\{60 x_j \right\}$ .

Hence, we can conclude that the optimal $j \in \mathcal{I}$ is

$j^* = \displaystyle\arg\max_{j \in \mathcal{I}} \left\{ x_j \right\}$ ,

i.e., we should leave the biggest of all $n$ files for last! This is quite intuitive. Given that

the downloading speed, $R$ , is assumed to be constant.

we need to download all the $n$ files.

we can conclude that the only way to minimize the total downloading time is to minimize the total waiting time, and the way to do that is to download the biggest file at the end.

Alternatively, we could have used the following cost function

$C(j) = \displaystyle\sum_{i \in \mathcal{I} \setminus \{j\} } T_i^W = \left(\displaystyle\sum_{i \in \mathcal{I}} 60 x_i\right) - 60 x_j$

where cost equals waiting time (i.e., we ignore the fixed cost). The optimal solution will be the same as before

$j^* = \displaystyle\arg\max_{j \in \mathcal{I}} \left\{ x_j \right\}$ ,

and the only difference will be that the minimum cost will now be the minimum waiting time, not the minimum total downloading time.

__________

Concluding Remarks

The solution we have computed only tells us which file to download in the $n$ -th download. The solution tells us nothing on which files to download on the previous $n-1$ downloads. We can then conclude that:

there are $n!$ distinct ways of downloading the files.

out of those $n!$ ways, $(n-1)!$ of them are optimal.

If all the files have the same size (i.e., if $x_i = \bar{x}, \, \forall i \in \mathcal{I}$ ), then there are $n!$ optimal ways of downloading them. In other words, when all files have the same size, the order in which one downloads them is irrelevant, which is somewhat obvious.

This problem could perhaps be generalized. Any ideas?

__________

DISCLAIMER: please note that downloading copyrighted material is illegal under U.S. law. I do not advocate downloading copyrighted material.

Tags:Operations Research
Posted in Operations Research | 3 Comments »

Modeling Ponzi Schemes II

February 7, 2008

As I wrote a few days ago, one of my ongoing projects is to devise mathematical models of Ponzi schemes. On my previous post I briefly explained what a Ponzi scheme is, so I will now focus on building a first model which, though somewhat simplistic and crude, will hopefully give us some insight.

__________

Model Variables

For starters, let us introduce some variables:

$c(t)$ : cash in the scammer’s pockets at time $t \in [0,\infty)$ .

$q(t)$ : cash influx rate at time $t \in [0,\infty)$ . Note that this is a rate! Thus, the amount of cash that flows into the scammer’s pockets in a time interval of infinitesimal duration $[t, t + dt]$ is $q(t) dt$ . You may wonder why I chose letter $q$ to denote influx: the reason is that I have used letter $q$ to denote influx since I started using it years ago to denote heat flow. Habits are hard to change.

$T$ : lock-up period ( $T > 0$ ). The scammer promises to return the money to the investors after a lock-up period of $T$ units of time.

$R$ : promised return on investment ( $R > 0$ ). The scammer promises to return to the investors $1+R$ times the money they invested, $T$ units of time after they invested.

Keeping track of the influx and outflow of cash, we can build a conservation law.

__________

Money Dynamics and the Law of Conservation of Cash

We can now write the “law of conservation of cash”: if more money comes in than it goes out, then the scammer’s pile of cash will be increasing (and so will his debt). We will assume that the scammer does not deposit the cash in a bank to earn interest on it, though we may consider that possibility in a more elaborate model. For the time being, our “law of conservation of cash” is given by the following differential equation

$\displaystyle\dot{c}(t) = \displaystyle q(t) - (1+R) q(t-T)$ ,

in which $c: [0,\infty) \rightarrow \mathbb{R}$ is the function to be determined, and $q: [0,\infty) \rightarrow \mathbb{R}$ is the forcing function. Note that the forcing function includes a delayed forcing term. Let us try to interpret this differential equation:

the rate at which cash flows out is higher than the rate at which money flows in. This is NOT good! Imagine a wash basin in which the water influx from the tap is lower than the outflux going down the drain. That’s right, the basin will soon be empty, and that is precisely why Ponzi schemes are unsustainable: either you increase the cash influx over time, or you will soon be out of money. Since the cash influx cannot grow without bound, at some point the cash influx will be insufficient to pay off the debt and the scammer will be owing money to a lot of very angry creditors.

cash flows out with a delay equivalent to the lock-up period.

We can now solve the differential equation.

__________

General solution of the differential equation

If we denote the initial amount of cash by $c(0) = c_0$ and solve the differential equation above, we obtain

$c(t) = c_0 + \displaystyle\int_{0}^t q(\tau) d\tau - (1+R) \displaystyle\int_{0}^{t} q(\tau - T) d\tau$ .

Note that for $t \in [0,T)$

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = 0$ ,

and that for $t > T$

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = \displaystyle\int_{0}^{t -T} q(\tau ) d\tau$ .

Therefore

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$ ,

and therefore the general solution can be written as

$c(t) = c_0 + \displaystyle\int_{0}^t q(\tau) d\tau - (1+R) \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$ .

This might look a bit complicated, but in fact it is very simple: the amount of cash the scammer will have in his pockets at time $t$ will be given by his initial amount of cash, plus the amount of cash his creditors lent him, minus the amount of cash he had to pay to his creditors (which is “amplified” by $R$ ) over time interval $(t-T, t)$ . Note that the scammer only starts returning money to the investors at time $t=T$ .

The aforementioned general solution can also be written as

$c(t) = c_0 + \displaystyle\int_{\max(t-T,0)}^t q(\tau) d\tau - R \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$ .

Before we try out some forcing functions, let’s get the notation straight for the remainder of this post:

the Dirac delta function will be denoted by $\delta(t)$ .

the Heaviside step function will be denoted by $u(t)$ . The Heaviside step function is the integral of the Dirac delta function.

the ramp function will be denoted by $s(t)$ . The ramp function is the integral of the Heaviside step function.

This is the usual notation in signal processing and control systems engineering. To understand the aforementioned general solution, let’s now try out a couple of forcing functions.

__________

Example: single discretionary cash influx at $t=0$

$\displaystyle q(t) = \displaystyle q_0 \delta(t)$

In this case, an amount of cash equal to $q_0$ is credited to the scammer’s pockets at time $t=0$ . The solution will thus be

$\displaystyle c(t) = \displaystyle c_0 + q_0 u(t) - (1+R) q_0 u(t-T)$ ,

which is the Ponzi scheme’s impulse response (borrowing another signal processing expression), so to say. Note that $c(t) = c_0 + q_0$ for $t \in (0, T)$ , while $c(t) = c_0 - R q_0$ for $t > T$ .

__________

Example: constant cash influx rate

$\displaystyle q(t) = \displaystyle q_0 u(t)$

In this case, a constant influx of cash flows to the scammer’s pockets. Unfortunately for the scammer, he will have to repay this cash with interest $T$ units of time later. The solution of the differential equation is now

$c(t) = \displaystyle c_0 + q_0 s(t) - (1+R) q_0 s(t-T)$ ,

which is the Ponzi scheme’s step response (once again borrowing a signals & systems expression). The cash will increase linearly with time for $t \in (0,T)$ , a maximum is reached at $t=T$ (maximum: $c(T) = c_0 + q_0 T$ ), and then the debt-paying time starts and the cash will decrease linearly with slope $- R q_0$ until the amount of cash reaches zero at $t = t_B > T$ . Making $c(t_B) = 0$ we have

$\displaystyle c_0 + q_0 t_B - (1+R) q_0 (t_b - T) = 0$ ,

which yields

$t_B = \displaystyle\frac{c_0}{R q_0} + \displaystyle\left(1 + \frac{1}{R}\right) T$ ,

which is the “bankruptcy time”. For $t > t_B$ , the scammer will have to go into debt to pay off to his investors.

__________

Concluding remarks

On this post, I presented a simple continuous-time model of a simplified Ponzi scheme. In the two examples I presented, one can conclude that the scammer’s best strategy is to run away at moment $t = T^{-}$ , when he has the most cash in his pockets (and owes the most to his creditors).

However, if we think beyond this model’s assumptions and limitations, it is clear that running away just before the lock-up period has expired might not be the “best strategy”. Note that if the scammer returns the money to the earliest investors, these might believe that the scammer truly has a Midas touch and decide to re-invest their money. In addition to that, if the scammer honors the early contracts and returns the money to his earlist investors, these investors may tell their friends and thus serve as “viral marketers” of the scammer’s investing “ingenuity”. Hence, it would then be natural to expect an increase in the money influx after the scammer returns the money to the earliest investors.

I will be writing more on this topic on future posts.

__________

Disclaimer: I am NOT an accountant, I am an electrical engineer. I have NEVER studied any accounting at all. Please bear with me if I misused technical terms, or if I invented silly new ones. Thank you.

__________

Earlier posts in this series:

Modeling Ponzi Schemes

Tags:Charles Ponzi, Finance, Fraud, Money Dynamics, Ponzi schemes
Posted in Finance | 10 Comments »

Modeling Ponzi Schemes

February 3, 2008

At the height of his success in Boston in 1920, Charles A. Ponzi was hailed by those he was cheating as the greatest Italian who ever lived. “You’re wrong,” he said modestly, “there’s Columbus, who discovered America, and Marconi, who discovered radio.” “But, Charlie, you discovered money,” they told him.

(San Diego Daily Transcript – July 16, 1974)

I admit that it may sound a bit ludicrous, but lately I have been thinking on how to devise mathematical models of Ponzi schemes .

It is clear that a Ponzi scheme is unsustainable and that it will, sooner or later, collapse under its own weight. The scammer promoting such a scheme will be owing ever-increasing amounts of money to the investors, and as soon as the influx of cash is not enough to pay off the debts plus interest, the scheme will collapse.

[ Charles Ponzi in 1920 - photo courtesy of the U.S. government ]

Ponzi schemes have happened for a long time, but the scheme bears the name of its most “illustrious” scammer, Charles Ponzi (1882–1949) , who ran a huge fraudulent operation in the U.S. in 1919 and 1920.

Note that:

the early investors in a Ponzi scheme will make money if they drop out before the whole thing collapses. On the other hand, the later investors will lose money.

there’s a money transfer from the later investors to the scammer promoting the scheme and the earlier investors, so to say. As such, one has the incentive to be an early investor provided that the fraud lasts long enough for one to profit.

an investor might be aware that there’s fraud going on and still invest if he thinks that the scheme will last a bit longer before it collapses so that he can get his money back and earn the interest.

How to devise mathematical models of Ponzi schemes? Which variables to choose? Which assumptions to make? It is not nearly as easy as one might think at first glance, I must say. An over-simplistic model is easy to devise, but it will tell us little. I have been building some models, and I will most likely write about them in future posts.

Tags:Charles Ponzi, Finance, Fraud, Ponzi schemes
Posted in Finance | 1 Comment »

S	M	T	W	T	F	S
« Jan				Apr »
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29

Rod Carvalho

Archive for February, 2008

Rolling dice

Optimal Downloading Strategies

Modeling Ponzi Schemes II

Modeling Ponzi Schemes

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Powered by FeedBurner

Meta

Follow “Rod Carvalho”

Rod Carvalho

Archive for February, 2008

Rolling dice

Optimal Downloading Strategies

Modeling Ponzi Schemes II

Modeling Ponzi Schemes

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Category Cloud

Powered by FeedBurner

Meta

Follow “Rod Carvalho”