Implementation of Stratified Sampling in Monte Carlo

Question

Background

I am trying to implement Monte Carlo Simulation with Stratified Sampling for barrier option under Black Scholes Model. I understand there is an analytic formula for this instrument and we can directly simulate the integration from time 0 to maturity because we have the distribution of stock price under this model. However, I would like to simulate it with daily step, i.e looping $S_{t_i} = S_{t_{i-1}}e^{(r-\frac{1}{2}\sigma^2)(t_i - t_{i-1})+\sigma\sqrt{(t_i - t_{i-1})}X}, X\sim N(0,1)$

Lecture notes found on google

I am trying to implement Martin Haugh's guideline. When applying the "Result 2" on page 52, we have

$\vec{a} = (1,1,...,1)^T$(column vector), Then we have $\vec{V} = w\vec{a} + MVN(\vec{0},I_m - \vec{a}\vec{a}^T)$

Question

1. $I_m - \vec{a}\vec{a}^T$ is not symmetric positive semi-definite.
2. Why do we have $\Sigma = I_m - \vec{a}\vec{a}^T$?

Thanks!

Answer 1

Your vector $a=(1,\ldots,1)^T$ does not satisfy

$$\| a \|^2=a_1^2 + \ldots + a_m^2=1, $$

as assumed by authors in Result 2.

(Q1) For $m=2$, we see it is needed when computing the eigenvalues of $I_2 - aa^T$, that is the roots $\lambda$ of equation

$$ 0=\det \begin{pmatrix} 1-\lambda- a_1^2 & -a_1 a_2 \\ -a_1 a_2 & 1-\lambda- a_2^2 \end{pmatrix} = (1-\lambda)(1-\lambda - a_1^2 -a_2^2).$$

We get $\lambda_1 = 1$ and $\lambda_2 = 1- a_1^2 -a_2^2$, which must be non-negative (as $I_2 - aa^T$ is positive semi-definite). With your vector you would get $\lambda_2 = -1$.

(Q2) Same property, $a_1^2 +a_2^2=1$, allows for:

$$ (a^Ta)^2 = \begin{pmatrix} a_1^4+a_1^2 a_2^2 & -a_1^3 a_2 -a_1 a_2^3 \\ -a_1^3 a_2 -a_1 a_2^3 & a_1^4+a_1^2 a_2^2 \end{pmatrix}$$ $$=(a_1^2 +a_2^2)\begin{pmatrix} a_1^2 & -a_1 a_2 \\ -a_1 a_2 & a_2^2 \end{pmatrix} =a^Ta$$

This in turn gives:

$$ (I_2-a^Ta)(I_2-a^Ta)^T = (I_2-a^Ta)(I_2-aa^T) $$

$$= I_2 - a^Ta -a^Ta + (a^Ta)^2 = I_2 - a^Ta$$

So, for $\Sigma:= I_2 - a^Ta$ we have:

$$ \Sigma = \Sigma \Sigma^T$$

which provides one of the matrices respecting equality:

$$ \Sigma = CC^T.$$ That is $\Sigma$ itself: $$C= \Sigma.$$