PCA for classification

Question

Assume that our samples are high dimensional points (i.e., d is large) and we use PCA to reduce it to k = 10 dimensions. After this step, we found that all the 10 new dimensions have continuous values (e.g., in other words, each feature in the transformed dimension is not from discrete domain, but rather, continuous domain). Describe in detail, how we can now use parametric method to train our model to do classification. In particular, discuss how we can compute the correlation matrix estimation, and when a new point arrive, what procedure we need to do so to make a classification prediction (assume in general, we have K > 2 classes).

Answer 1

The circle is just a distraction, since the result is determined as soon as the chain reaches either $0$ or the neighbour it didn’t visit in the first step. Thus this is equivalent to a linear simple symmetric random walk in one dimension. Such a walk on $[0,m]$ starting at $k$ has probability $\frac km$ to reach $m$ before it reaches $0$. In the present case $k=1$ and $m=4$.

Answer 2

By symmetry, we can assume the first move lands at $1$, not $4$.

With that assumption, for $1\le k\le 3$, let $p_k$ be the probability, starting at $k$, of reaching $4$ before reaching $0$.

The goal is to find $p_1$.

From the given transition probabilities, we have the system \begin{align*} p_1&=\frac{1}{2}p_2\\[4pt] p_2&=\frac{1}{2}p_1+\frac{1}{2}p_3\\[4pt] p_3&=\frac{1}{2}p_2+\frac{1}{2}\\[4pt] \end{align*} of $3$ linear equations in $3$ unknowns.

Solving the system yields $p_1={\large{\frac{1}{4}}}$.