# Implementation of Stratified Sampling in Monte Carlo

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)$$

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!

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.$$