Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $x=\left(x_t\right)_{t=1}^n$ be a vector such that $$ x_t = \prod_{i=1}^t u_i, \tag{1} $$ where each parameters $u_i$ can take any of two value $$ u_i \in \left\{a,b \right\} = \left\{ 1.3, 0.8 \right\}. $$ Each vector $x$ represents a path in a binomial tree.

Given an arbitrary vector $y=\left(y_t\right)_{t=1}^n$, where each $y_t$ is in $\mathbb R^+$, how to solve the problem $$ \min_{x \in X} \lVert y - x \rVert^2 = \sum_{t=1}^n \left(y_t - x_t \right)^2 $$ where $X$ is the set of all possible vector of the form (1).
So, given a realization of the stock, find the closest binomial path.

The only way I see to solve this problem is to do Gram-Schmidt on $X$, and then project $y$ on the orthonormal basis found.
But, my $n$ is large, say $100$.
This induces $$\mathrm{cardinality} X = 2^{100},$$ so I don't think Gram-Schmidt is viable.

I would use least-square or Newton-Raphson, but the variable are not continuous.

share|cite|improve this question
I don't know how to find the closest $x$, but a reasonable solution may be obtainable with the following binary tree algorithm. Let $R(a,b)$ be the number of $1.3$-multiplications in the interval $ a\le t \le b$. Note that $R(1,t)$ determines $y_t$. Choose $R(1,n)$ to minimize $|x_n-y_n|$. Then choose $R(1,n/2)$ to minimize $|x_{n/2}-y_{n/2}|$. Then choose $R(1,n/4)$ based on $y_{n/4}$ and choose $R(n/2+1,3n/4)$ based on $y_{3n/4}$. And so on. This works better if $n$ is a power of $2$, but you can always divide in halves approximately. – user127096 Mar 24 '14 at 0:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.