# A New Multivariate Markov Chain Model for Adding a New Categorical Data Sequence

Authors: Chao Wang; Ting-Zhu Huang; Wai-Ki Ching
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We propose a new multivariate Markov chain model for adding a new categorical data sequence. The number of the parameters in the new multivariate Markov chain model is only𝒪(3s) less than 𝒪
(
(
s
+
1
)
2
) the number of the parameters in the former multivariate Markov chain model. Numerical experiments demonstrate the benefits of the new multivariate Markov chain model on saving computational resources.


---

## Body

## 1. Introduction

Markov chains are of interest in a wide range of applications, for example, telecommunication systems [1, 2], remanufacturing and inventory systems [3], speech recognition [4], PageRank [5–7], microbial gene [8], and AIDS [9]. In recent years, the predictions of data sequences have become more and more useful in other applications such as sales demand prediction [10], DNA sequencing [11], credit risk [12], and stock prices [13].Different models have been proposed for multiple categorical data sequences prediction. A multivariate Markov chain model was proposed in [10] by Ching et al.; they constructed a new matrix by means of the transition probability matrices among different sequences. An improved multivariate Markov chain model had also been studied to speed up the convergent speed for computing the stationary or steady-state solutions [14]. In the improved multivariate Markov chain model, Ching et al. incorporated positive and negative association parts. The extensions of intensity-based models for pricing credit risk and derivative securities to the simulation and valuation of portfolios were discussed in [15]. Moreover, there are many other papers contributing to the multivariate Markov chain model, for example, [16–22] and so on.With the developments of Markov chain models and their applications, the number of the sequences may be larger. It is inevitable that a large categorical data sequence group will cause high computational cost in multivariate Markov chain model. Thus, reducing the number of parameters in the models is useful in numerical computation. For the above reasons, we present a new multivariate Markov chain model for detecting the relations between the previous data sequences and the following data sequence.The rest of the paper is organized as follows. In Section2, we review two lemmas and several Markov chain models. In Section 3, the new multivariate Markov chain model is proposed for adding a new categorical sequence. Moreover, the convergence of the new multivariate Markov chain model is proved. Section 4 gives parameter estimation method for the new multivariate Markov chain model. Numerical experiments on sales demand prediction and stock prices prediction are presented to test the efficiency of the new multivariate Markov chain model in Section 5. Concluding remarks are given in Section 6. The data of the stocks’ prices are provided in the Appendix.


## 2. A Review on Markov Chain Models

In this section, we briefly introduce two lemmas, the Markov chain model [23] and the multivariate Markov chain model [10].Lemma 1 (see [24, Perron-Frobenius theorem]).
LetA
∈
ℝ
m
×
m be a nonnegative and irreducible matrix. Then,(1)
Ahas a positive real eigenvalue λ equal to its spectral radius; that is, λ
=
max
⁡
k
|
λ
k
(
A
)
| where λ
k
(
A
) denotes the kth eigenvalue of A;
(2)
toλ there corresponds an eigenvector z of its entries being real and positive, such that A
z
=
λ
z;
(3)
λ is a simple eigenvalue of A.Lemma 2 (see [22]).
LetB be the iterative matrix of multivariate Markov chain model and let X
t be the state distribution at time t. If B is irreducible and aperiodic, then there is a unique stationary distribution π satisfying π
=
B
π and lim
⁡
t
→
∞
X
t
=
π.


### 2.1. The Markov Chain Model

Let the state set of the categorical data sequence beℳ
=
{
1,2
,
…
,
m
}. The Markov chain satisfise the following relations:
(1)
Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
0
=
θ
0
,
x
1
=
θ
1
,
…
,
x
t
=
θ
t
)
=
Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
t
=
θ
t
)
,
where θ
t
∈
ℳ, t
∈
{
0,1
,
2
,
…
}. The conditional probability Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
t
=
θ
t
) is called one-step transition probability. If we rewrite the transition probability as
(2)
p
i
,
j
=
Prob
(
x
t
+
1
=
i
∣
x
t
=
j
)
,
∀
i
,
j
∈
ℳ
,
the Markov chain model can be presented as follows:
(3)
X
t
+
1
=
P
X
t
,
where
(4)
P
=
[
p
i
,
j
]
,
0
≤
p
i
j
≤
1
,
∀
i
,
j
∈
ℳ
,
∑
i
=
1
m
‍
p
i
,
j
=
1
,
∀
j
∈
ℳ
.
Here, X
0 is the initial probability distribution and X
t
=
(
x
t
1
,
x
t
2
,
…
,
x
t
m
)
T is the state probability distribution at time t.


### 2.2. The Multivariate Markov Chain Model

The multivariate Markov chain model has the following form:(5)
x
t
+
1
(
j
)
=
∑
k
=
1
s
‍
λ
j
,
k
P
(
j
,
k
)
x
t
(
k
)
,
∀
j
=
1,2
,
…
,
s
,
t
=
0,1
,
…
,
where
(6)
λ
j
k
≥
0
,
∀
j
,
k
=
1,2
,
…
,
s
,
∑
k
=
1
s
‍
λ
j
,
k
=
1
,
∀
j
=
1,2
,
…
,
s
.
x
0
(
j
) is the initial probability distribution of the jth sequence, x
t
(
k
) is the state probability distribution of the kth sequence at time t, x
t
+
1
(
j
) is the state probability distribution of the jth sequence at time t
+
1, and P
(
j
,
k
) is the one-step transition probability matrix from the states in the kth sequence at time t to the states in the jth sequence at time t
+
1. In the matrix form, (5) has
(7)
X
t
+
1
=
(
x
t
+
1
(
1
)
x
t
+
1
(
2
)
⋮
x
t
+
1
(
s
)
)
=
(
λ
1,1
P
(
1,1
)
λ
1,2
P
(
1,2
)
⋯
λ
1
,
s
P
(
1
,
s
)
λ
2,1
P
(
2,1
)
λ
2,2
P
(
2,2
)
⋯
λ
1,1
P
(
2
,
s
)
⋮
⋮
⋮
⋮
λ
s
,
1
P
(
s
,
1
)
λ
s
,
2
P
(
s
,
2
)
⋯
λ
s
,
s
P
(
s
,
s
)
)
(
x
t
(
1
)
x
t
(
2
)
⋮
x
t
(
s
)
)
.
Entries P
(
j
,
k
) can be obtained directly from the categorical data sequences, and λ
j
,
k can be got by the linear programming [10].


## 2.1. The Markov Chain Model

Let the state set of the categorical data sequence beℳ
=
{
1,2
,
…
,
m
}. The Markov chain satisfise the following relations:
(1)
Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
0
=
θ
0
,
x
1
=
θ
1
,
…
,
x
t
=
θ
t
)
=
Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
t
=
θ
t
)
,
where θ
t
∈
ℳ, t
∈
{
0,1
,
2
,
…
}. The conditional probability Prob
(
x
t
+
1
=
θ
t
+
1
∣
x
t
=
θ
t
) is called one-step transition probability. If we rewrite the transition probability as
(2)
p
i
,
j
=
Prob
(
x
t
+
1
=
i
∣
x
t
=
j
)
,
∀
i
,
j
∈
ℳ
,
the Markov chain model can be presented as follows:
(3)
X
t
+
1
=
P
X
t
,
where
(4)
P
=
[
p
i
,
j
]
,
0
≤
p
i
j
≤
1
,
∀
i
,
j
∈
ℳ
,
∑
i
=
1
m
‍
p
i
,
j
=
1
,
∀
j
∈
ℳ
.
Here, X
0 is the initial probability distribution and X
t
=
(
x
t
1
,
x
t
2
,
…
,
x
t
m
)
T is the state probability distribution at time t.


## 2.2. The Multivariate Markov Chain Model

The multivariate Markov chain model has the following form:(5)
x
t
+
1
(
j
)
=
∑
k
=
1
s
‍
λ
j
,
k
P
(
j
,
k
)
x
t
(
k
)
,
∀
j
=
1,2
,
…
,
s
,
t
=
0,1
,
…
,
where
(6)
λ
j
k
≥
0
,
∀
j
,
k
=
1,2
,
…
,
s
,
∑
k
=
1
s
‍
λ
j
,
k
=
1
,
∀
j
=
1,2
,
…
,
s
.
x
0
(
j
) is the initial probability distribution of the jth sequence, x
t
(
k
) is the state probability distribution of the kth sequence at time t, x
t
+
1
(
j
) is the state probability distribution of the jth sequence at time t
+
1, and P
(
j
,
k
) is the one-step transition probability matrix from the states in the kth sequence at time t to the states in the jth sequence at time t
+
1. In the matrix form, (5) has
(7)
X
t
+
1
=
(
x
t
+
1
(
1
)
x
t
+
1
(
2
)
⋮
x
t
+
1
(
s
)
)
=
(
λ
1,1
P
(
1,1
)
λ
1,2
P
(
1,2
)
⋯
λ
1
,
s
P
(
1
,
s
)
λ
2,1
P
(
2,1
)
λ
2,2
P
(
2,2
)
⋯
λ
1,1
P
(
2
,
s
)
⋮
⋮
⋮
⋮
λ
s
,
1
P
(
s
,
1
)
λ
s
,
2
P
(
s
,
2
)
⋯
λ
s
,
s
P
(
s
,
s
)
)
(
x
t
(
1
)
x
t
(
2
)
⋮
x
t
(
s
)
)
.
Entries P
(
j
,
k
) can be obtained directly from the categorical data sequences, and λ
j
,
k can be got by the linear programming [10].


## 3. A New Multivariate Markov Chain Model

In order to reduce the number of the parameters in multivariate Markov chain model, a new multivariate Markov chain model is proposed. Moreover, the convergent property of the new model is also analyzed.Suppose that there ares categorical data sequences and each of the sequences has m possible states in ℳ. The multivariate Markov chain model for s categorical data sequences has the form
(8)
x
r
+
1
(
j
)
=
∑
k
=
1
s
‍
λ
j
,
k
′
P
(
j
,
k
)
x
r
(
k
)
∀
1
≤
j
≤
s
,
r
≥
0
,
where
(9)
λ
j
,
k
′
≥
0
,
∀
1
≤
j
,
k
≤
s
,
∑
k
=
1
s
‍
λ
j
,
k
′
=
1
,
∀
j
=
1,2
,
…
,
s
,
where x
0
(
j
),x
r
(
k
),x
r
+
1
(
j
)
, and P
(
j
k
) are defined the same as those in Section 2.2. In the matrix form, (8) is
(10)
X
r
+
1
=
(
x
r
+
1
(
1
)
x
r
+
1
(
2
)
⋮
x
r
+
1
(
s
)
)
=
(
λ
1,1
′
P
(
1,1
)
λ
1
,
2
′
P
(
1,2
)
⋯
λ
1
,
s
′
P
(
1
,
s
)
λ
2,1
′
P
(
2,1
)
λ
2
,
2
′
P
(
2,2
)
⋯
λ
1,1
′
P
(
2,1
)
⋮
⋮
⋮
⋮
λ
s
,
1
′
P
(
1,1
)
λ
s
,
2
′
P
(
s
,
2
)
⋯
λ
s
,
s
′
P
(
s
,
s
)
)
(
x
r
(
1
)
x
r
(
2
)
⋮
x
r
(
s
)
)
.
Transition probability matrix P
(
j
,
k
) can be obtained directly by the s categorical data sequences. The parameters λ
j
,
k
′ can be solved from the corresponding linear programming.Assuming that the multivariate Markov chain model for previous sequences is obtained, we add a new sequence at the back of the previous sequences. For detecting the relations between the previouss categorical data sequences and the new categorical data sequence, a new multivariate Markov chain model is proposed and has the following form:
(11)
x
r
+
1
(
j
)
=
{
l
j
∑
k
=
1
s
‍
λ
j
,
k
′
P
(
j
,
k
)
x
r
(
k
)
+
λ
j
,
s
+
1
P
(
j
,
s
+
1
)
x
r
(
s
+
1
)
∀
j
=
1,2
,
…
,
s
,
∑
k
=
1
s
+
1
‍
λ
j
,
k
P
(
j
,
k
)
x
r
(
k
)
∀
j
=
s
+
1
,
where
(12)
l
j
≥
0
,
l
j
λ
j
,
k
′
=
λ
j
,
k
,
λ
j
,
s
+
1
≥
0
,
λ
s
+
1
,
k
≥
0
∀
1
≤
j
,
k
≤
s
,
r
=
0,1
,
…
,
∑
k
=
1
s
+
1
‍
λ
j
,
k
=
1
∀
j
=
1,2
,
…
,
s
+
1
.
In the matrix form, (11) has
(13)
(
x
r
+
1
(
1
)
⋮
x
r
+
1
(
s
)
x
r
+
1
(
s
+
1
)
)
=
(
l
1
λ
11
′
P
(
11
)
⋯
l
1
λ
1
,
s
′
P
(
1
,
s
)
λ
1
,
s
P
(
1
,
s
+
1
)
⋮
⋮
⋮
⋮
l
s
λ
s
,
1
′
P
(
s
,
1
)
⋯
l
s
λ
s
,
s
′
P
(
s
,
s
)
λ
s
,
s
+
1
P
(
s
,
s
+
1
)
λ
s
+
1,1
P
(
s
+
1,1
)
⋯
λ
s
+
1
,
s
P
(
s
+
1
,
s
)
λ
s
+
1
,
s
+
1
P
(
s
+
1
,
s
+
1
)
)
×
(
x
r
(
1
)
⋮
x
r
(
s
)
x
r
(
s
+
1
)
)
.
Let
(14)
X
r
+
1
=
(
x
r
+
1
(
1
)
,
…
,
x
r
+
1
(
s
)
,
x
r
+
1
(
s
+
1
)
)
T
,
B
=
(
l
1
λ
11
′
P
(
11
)
⋯
l
1
λ
1
,
s
′
P
(
1
,
s
)
λ
1
,
s
P
(
1
,
s
+
1
)
⋮
⋮
⋮
⋮
l
s
λ
s
,
1
′
P
(
s
,
1
)
⋯
l
s
λ
s
,
s
′
P
(
s
,
s
)
λ
s
,
s
+
1
P
(
s
,
s
+
1
)
λ
s
+
1,1
P
(
s
+
1,1
)
⋯
λ
s
+
1
,
s
P
(
s
+
1
,
s
)
λ
s
+
1
,
s
+
1
P
(
s
+
1
,
s
+
1
)
)
.
Equation (13) is abbreviated as
(15)
X
r
+
1
=
B
X
r
.Theorem 3.
Letl
j
≥
0
,
λ
j
,
k
′
≥
0
,
l
j
λ
j
,
k
′
=
λ
j
,
k. If λ
j
,
s
+
1
>
0
,
λ
s
+
1
,
k
>
0
∀
1
≤
j
,
k
≤
s, then the iterative matrix B has an eigenvalue equal to one and the modulus of all its eigenvalues are less than or equal to one.Proof.
Suppose that(16)
Λ
=
(
λ
(
1,1
)
⋯
λ
(
1
,
s
)
λ
(
1
,
s
+
1
)
⋮
⋮
⋮
⋮
λ
(
s
,
1
)
⋯
λ
(
s
,
s
)
λ
(
s
,
s
+
1
)
λ
(
s
+
1,1
)
⋯
λ
(
s
+
1
,
s
)
λ
(
s
+
1
,
s
+
1
)
)
=
(
l
1
λ
′
(
1,1
)
⋯
l
1
λ
′
(
1,2
)
λ
(
1
,
s
+
1
)
⋮
⋮
⋮
⋮
l
2
λ
′
(
s
,
1
)
⋯
l
s
λ
′
(
s
,
s
)
λ
(
s
,
s
+
1
)
λ
(
s
+
1,1
)
⋯
λ
(
s
+
1
,
s
)
λ
(
s
+
1
,
s
+
1
)
)
.
From (9) and (12), each column sum of this matrix is equal to one and the matrix Λ is nonnegative and irreducible. According to Lemma 1, there exists a positive vector
(17)
y
=
[
y
1
,
y
2
,
…
,
y
s
]
T
satisfying
(18)
Λ
y
=
y
,
y
T
Λ
T
=
y
T
.
Let 1
m
=
[
1
,
…
,
1
]
∈
ℝ
1
×
m. Since P
(
j
k
) is a transition probability matrix, it has
(19)
1
m
P
(
j
,
k
)
=
1
m
.
It is clear that
(20)
[
y
1
1
m
,
y
2
1
m
,
…
,
y
s
1
m
]
B
=
[
y
1
1
m
,
y
2
1
m
,
…
,
y
s
1
m
]
,
with 1 an eigenvalue of B.
Now, our aim is to prove that the modulus of all the eigenvalues ofBare less than or equal to one. Suppose that D
v
=
Diag
(
v
), v
T
=
y
⊗
1
m
=
[
y
1
1
m
,
y
2
1
m
,
…
,
y
s
1
m
] satisfying v
T
B
=
v
T. B
^
=
D
v
B
D
v
-
1 is similar to B. From (20), it has ∥
B
^
∥
1
=
1. Then
(21)
ρ
(
B
)
=
ρ
(
B
^
)
≤
∥
B
^
∥
1
=
1
.Theorem 4.
Assume that∀
1
≤
j
,
k
≤
s
+
1
,
p
(
j
,
k
) is irreducible,∀
1
≤
j
,
k
≤
s
,
l
j
λ
j
,
k
′
=
λ
j
,
k
≥
0, and λ
(
j
,
s
+
1
)
>
0
,
λ
(
s
+
1
,
k
)
>
0. Then there is a vector X
=
[
x
(
1
)
,
x
(
2
)
,
…
,
x
(
s
+
1
)
]
T satisfying X
=
B
X and
(22)
∑
i
=
1
m
‍
[
x
(
i
)
]
j
=
1
∀
i
=
1,2
,
…
,
m
.Proof.
The proof is similar to Proposition  2 in [1] and therefore it is omitted.To keep the irreducibility ofB, we fill the column of P
(
j
,
k
) with 1
/
m when the column sum of B is zero.Theorem 5.
LetX be the stationary probability of the new multivariate Markov chain model. Then X
=
B
X and lim
⁡
t
→
∞
X
t
=
X.Proof.
From Lemma2, our goal is to prove that B is irreducible and aperiodic. Since B is connected, B is irreducible. Then we only need to prove that B is aperiodic. Let S
1
=
{
1,2
,
…
,
s
-
1
},S
=
{
1,2
,
…
,
s
}. There exists t
1 such that (
B
(
i
j
)
)
t
1
>
0
∀
i
,
j
∈
S
1. From the form of B, we obtain B
(
s
j
)
>
0
,
B
(
j
s
)
>
0. There exists t
2, t
3, t
4 satisfying B
i
j
t
2
>
0, B
i
i
t
3
>
0
,
B
k
i
t
4
>
0. Therefore, B
k
j
t
2
+
t
3
+
t
4
≥
B
i
j
t
2
B
i
i
t
3
B
k
i
t
4
>
0. Because B
k
j
n
>
0
∀
n
>
t
2
+
t
3
+
t
4
,
(
B
)
n is a positive matrix. Then B is aperiodic. According to the above results, the conclusions of this theorem are obtained.


## 4. Parameter Estimation Method of the New Multivariate Markov Chain Model

Letℳ
=
{
1,2
,
…
,
m
} be the states set and let f
i
j
,
i
k
(
j
,
k
) be frequency from the i
k state in the kth sequence at time t
=
r to the i
j state in the jth sequence at time t
=
r
+
1
∀
1
≤
i
j
,
i
k
≤
m. The transition frequency matrix F
(
j
,
k
) is
(23)
F
(
j
,
k
)
=
(
f
1,1
(
j
,
k
)
f
1,2
(
j
,
k
)
⋯
f
1
,
m
(
j
,
k
)
f
2,1
(
j
,
k
)
f
2,1
(
j
,
k
)
⋯
f
2
,
m
(
j
,
k
)
⋮
⋮
⋮
⋮
f
m
,
1
(
j
,
k
)
f
m
,
1
(
j
,
k
)
⋯
f
m
,
m
(
j
,
k
)
)
m
×
m
.
The transition probability matrix P
(
j
,
k
) can be obtained by normalizing the transition frequency matrix F
(
j
,
k
) as follows:
(24)
P
(
j
,
k
)
=
(
p
1,1
(
j
,
k
)
p
1,2
(
j
,
k
)
⋯
p
1
,
m
(
j
,
k
)
p
2,1
(
j
,
k
)
p
2,1
(
j
,
k
)
⋯
p
2
,
m
(
j
,
k
)
⋮
⋮
⋮
⋮
p
m
,
1
(
j
,
k
)
p
m
,
1
(
j
,
k
)
⋯
p
m
,
m
(
j
,
k
)
)
m
×
m
,
where
(25)
p
i
j
,
i
k
(
j
,
k
)
=
{
f
i
j
,
i
k
(
j
,
k
)
∑
i
j
=
1
m
‍
f
i
j
,
i
k
(
j
,
k
)
,
if
∑
i
j
=
1
m
‍
f
i
j
,
i
k
(
j
,
k
)
≠
0
,
0
,
otherwise
.Subsequently, the way of estimating the parameterλ
j
,
k will be introduced. Consider X to be a joint stationary probability distribution. X can be presented as
(26)
X
=
(
(
X
(
1
)
)
T
,
(
X
(
2
)
)
T
,
…
,
(
X
(
s
)
)
T
)
m
s
×
1
T
satisfying
(27)
B
X
≡
X
.
One would expect that
(28)
(
B
(
1,1
)
B
(
1,2
)
⋯
B
(
1
,
s
)
B
(
2,1
)
B
(
2,2
)
⋯
B
(
2
,
s
)
⋮
⋮
⋮
⋮
B
(
s
,
1
)
B
(
s
,
2
)
⋯
B
(
s
,
s
)
)
X
≈
X
.
Certainly, (28) can be interpreted as
(29)
|
B
X
-
X
|
≤
ω
,
where ω is small enough.One way of estimatingλ
j
,
k is to transform (29) into a minimization problem as the following form:
(30)
min
⁡
λ
i
,
j
∥
B
X
-
X
∥
subject
to
∑
k
=
1
s
+
1
‍
λ
j
,
k
=
1
,
∀
j
∈
{
1,2
,
…
,
s
+
1
}
,
λ
j
,
k
≥
0
,
∀
j
,
k
∈
{
1,2
,
…
,
s
+
1
}
.
The minimization problem (30) is identical to the following form:
(31)
min
⁡
λ
i
,
j
max
⁡
i
(
|
[
∑
k
=
1
s
‍
l
j
λ
j
,
k
′
P
(
j
,
k
)
x
(
k
)
+
λ
j
,
s
+
1
(
h
)
P
(
j
,
s
+
1
)
x
(
s
+
1
)
-
x
(
j
)
∑
k
=
1
s
‍
]
i
|
)
subject
to
∑
k
=
1
s
‍
l
j
λ
j
,
k
′
+
λ
j
,
s
+
1
=
1
,
∀
j
∈
{
1,2
,
…
,
s
}
,
∑
k
=
1
s
+
1
‍
λ
s
+
1
,
k
=
1
,
λ
j
,
s
+
1
,
λ
s
+
1
,
k
≥
0
,
∀
j
,
k
∈
{
1,2
,
…
,
s
+
1
}
,
where [
·
]
i is the ith entry of the vector. Let the norm be ∥
·
∥
2. The above problem can be rewritten as a linear programming problem
(32)
min
⁡
λ
ω
j
subject
to
(
ω
j
ω
j
)
≥
x
(
j
)
-
B
(
l
j
λ
j
,
s
+
1
)
(
ω
j
ω
j
)
≥
-
x
(
j
)
+
B
(
l
j
λ
j
,
s
+
1
)
,
∀
j
∈
{
1,2
,
…
,
s
}
(
ω
j
ω
j
⋮
ω
j
)
≥
x
(
j
)
-
B
(
λ
j
,
1
λ
j
,
2
⋮
λ
j
,
s
+
1
)
(
ω
j
ω
j
⋮
ω
j
)
≥
-
x
(
j
)
+
B
(
λ
j
,
1
λ
j
,
2
⋮
λ
j
,
s
+
1
)
,
∀
j
=
s
+
1
,
ω
j
≥
0
,
l
j
∑
k
=
1
s
λ
j
,
k
+
λ
j
,
s
+
1
‍
=
1
,
∀
j
∈
{
1,2
,
…
,
s
}
,
∑
k
=
1
s
+
1
λ
s
+
1
,
k
‍
=
1
,
λ
j
,
s
+
1
,
λ
s
+
1
,
k
≥
0
,
∀
j
,
k
∈
{
1,2
,
…
,
s
+
1
}
,
where
(33)
B
=
{
[
λ
j
,
1
p
(
j
,
1
)
x
(
1
)
+
λ
j
,
2
p
(
j
,
2
)
x
(
2
)
+
⋯
+
λ
j
,
s
p
(
j
,
s
)
x
(
s
)
∣
p
(
j
,
s
+
1
)
x
(
s
+
1
)
]
,
if
1
≤
j
≤
s
,
[
p
(
j
,
1
)
x
(
1
)
∣
p
(
j
,
2
)
x
(
2
)
∣
⋯
∣
p
(
j
,
s
)
x
(
s
)
∣
p
(
j
,
s
+
1
)
x
(
s
+
1
)
]
,
if
j
=
s
+
1
.


## 5. Numerical Experiments

In this section, numerical experiments with different multivariate Markov chain models on sales demand prediction and stock prices prediction are given. We report on numerical results obtained with a Matlab 7.0.1 implementation on Windows XP with 2.93 GHz 64-bit processor and 1 GB memory.


### 5.1. Sales Demand Prediction

In this section, the sales demand sequences are presented to show the benefits of the new multivariate Markov chain model. Since the requirement of the market fluctuates heavily, the production planning and the inventory control directly affect the estate cost. Thus, studying the interplay between the storage space requirement and the overall growing sales demand is a pressing issue for the company. Here, our goal is to predict the sales demand of the market for minimizing the estate cost. Assume that products are classified into six possible states(
1,2
,
3,4
,
5,6
); for example, 1
= no sale volume, 2
= very low sale volume, 3
= low sale volume, 4
= standard sale volume, 5
= high sale volume, and 6
= very high sale volume. The customers’ sales demand data of five important products can be found in [10].The multivariate Markov chain model of four categorical data sequences,P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D, will be given. By computing the proportions of the occurrences of each state in each sequence, we formulate the initial probability distributions of four categorical data sequences
(34)
x
0
(
1
)
=
(
0.0818,0.4052,0.0483,0.0335,0.0037,0.4275
)
T
,
x
0
(
2
)
=
(
0.3680,0.1970,0.0335,0.0000,0.0037,0.3978
)
T
,
x
0
(
3
)
=
(
0.1450,0.2045,0.0186,0.0000,0.0037,0.6283
)
T
,
x
0
(
4
)
=
(
0.0000,0.3569,0.1338,0.1896,0.0632,0.2565
)
T
.
The transition probability matrix P
(
j
,
k
) can be obtained after normalizing the transition frequency matrix. By solving the corresponding linear programming problem, one can obtain λ
i
,
j. The multivariate Markov chain model is presented as follows:
(35)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
P
(
3,4
)
x
r
(
4
)
,
x
r
+
1
(
4
)
=
P
(
4,4
)
x
r
(
4
)
.
In order to uncover the relations of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E, we add a new categorical data sequence P
r
o
d
u
c
t
E at the back of the original categorical data sequences. With the data sequence ofP
r
o
d
u
c
t
E, the initial probability distribution of P
r
o
d
u
c
t
E is obtained as follows:
(36)
x
0
(
5
)
=
(
0.0000,0.3569,0.1227,0.2268,0.0520,0.2416
)
T
.In the multivariate Markov chain model,λ
j
,
k can be calculated by a corresponding linear programming problem. The multivariate Markov chain model is
(37)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
P
(
3,5
)
x
r
(
5
)
,
x
r
+
1
(
4
)
=
0.2783
P
(
4,4
)
x
r
(
4
)
+
0.7217
P
(
4,5
)
x
r
(
5
)
,
x
r
+
1
(
5
)
=
P
(
5,4
)
x
r
(
4
)
.After calculatingλ
j
,
k by a corresponding linear programming problem, the new multivariate Markov chain model can be presented as follows:
(38)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
0.0007
P
(
3,4
)
x
r
(
4
)
+
0.9993
P
(
3,5
)
x
r
(
5
)
,
x
r
+
1
(
4
)
=
0.4706
P
(
4,4
)
x
r
(
4
)
+
0.5294
P
(
4,5
)
x
r
(
5
)
,
x
r
+
1
(
5
)
=
P
(
5,4
)
x
r
(
4
)
.
From the results of the new multivariate Markov model, P
r
o
d
u
c
t
A and P
r
o
d
u
c
t
B are closely related. Moreover, the sales demand of P
r
o
d
u
c
t
A depends strongly on P
r
o
d
u
c
t
B. The reason is that the chemical nature of P
r
o
d
u
c
t
A and P
r
o
d
u
c
t
B is the same, only used for different packaging of marketing purposes. P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E are closely related. The fact is that P
r
o
d
u
c
t
s
C and P
r
o
d
u
c
t
E have the same product flavor, only different in packaging.In the following, we use the new multivariate Markov chain model and the multivariate Markov chain model to predict the state of thekth sequence x
t
(
k
) at time t. The maximum probability,
(39)
x
t
(
k
)
=
j
,
if
[
x
t
(
k
)
]
i
≤
[
x
t
(
k
)
]
j
,
∀
1
≤
i
≤
m
,
t
>
1
,
is taken as the state at time t. For evaluating the effectiveness of the new multivariate Markov chain model, prediction results are measured by the prediction accuracy r defined as
(40)
r
=
1
T
-
n
×
∑
t
=
n
+
1
T
‍
δ
t
×
100
%
,
where T is the length of the data sequence and
(41)
δ
t
=
{
1
,
if
x
t
(
k
)
=
θ
t
(
k
)
,
0
,
otherwise
.Note that “t
i
m
e” is CPU time, “ω” is the object function value of the corresponding linear programming problem, “n
p” is the number of the parameters in the models, and the prediction accuracies of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E are “A,” “B,” “C,” “D,” and “E,” respectively. Suppose that the results of the multivariate Markov chain model of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D are obtained. The new multivariate Markov chain model for P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D adding P
r
o
d
u
c
t
E is denoted as “A,B,C,D add E.” The multivariate Markov chain model is denoted as “Mmodel.” Stop criterion can be found in Matlab function l
i
n
p
r
o
g. The results are presented in Table 1.Table 1
Numerical results of the multivariate Markov chain model and the new multivariate Markov chain model on sales demand prediction.
A
B
C
D
E
T
i
m
e
n
p
ω
M
m
o
d
e
l
0.4176
0.3985
0.6207
0.3525
0.3525
0.0938
25
0.0095
B
,
C
,
D
,
E
a
d
d
A
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
C
,
D
,
E
a
d
d
B
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
D
,
E
a
d
d
C
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
C
,
E
a
d
d
D
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
C
,
D
a
d
d
E
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095Observing the results from Table1, we find that the object function values of the new model and the multivariate Markov chain model are the same. The prediction accuracies of our new models are comparable to the prediction accuracy of the multivariate Markov chain model. The new multivariate Markov chain model performs better than the multivariate Markov chain model in time consumption and controlled parameters.


### 5.2. Stock Prices Prediction

The data of 12 American stocks’ price from December 17, 2013, to January 16, 2014, are given in the Appendix. They are divided equally into 6 regions as 6 states between maximum price and minimum price of the stocks. The state set of 12 stocks isℳ
=
{
0,1
,
2,3
,
4,5
}. The data of 12 stocks in the Appendix are transformed into categorical data sequences.“t
i
m
e,” “ω,” “
n
p,” and “M
m
o
d
e
l” are denoted the same as those in Section 5.2. Note that “
M
m
o
d
e
l
-
1” is the multivariate Markov chain model of all stocks except AMAP. Suppose that the results of “
M
m
o
d
e
l
-
1” are obtained. The new multivariate Markov chain model which is denoted as “
N
M
m
o
d
e
l” can detect the relations of BIDU, CTRP, GA, EDU, SINA, SOHU, YOKU, XRS, QIHU, HTHT, HMIN, and AMAP. Stop criterion can be found in Matlab order l
i
n
p
r
o
g. The results are presented in Table 2.Table 2
Numerical results of the multivariate Markov chain model and the new multivariate Markov chain model on stock prices prediction.
Time
np
ω
Mmodel
0.7354
144
0.3095
NMmodel
0.1406
34
0.3099From Table2, the object function values of the new multivariate Markov chain model and the multivariate Markov chain model are nearly the same. The CPU time of the new multivariate Markov chain model is the CPU time of the multivariate Markov chain model’s1
/
5. The number of the parameters in the new multivariate Markov chain model is one-third of those in the multivariate Markov chain model. The new multivariate Markov chain model is better than the multivariate Markov chain model in time consumption and controlled parameters.


## 5.1. Sales Demand Prediction

In this section, the sales demand sequences are presented to show the benefits of the new multivariate Markov chain model. Since the requirement of the market fluctuates heavily, the production planning and the inventory control directly affect the estate cost. Thus, studying the interplay between the storage space requirement and the overall growing sales demand is a pressing issue for the company. Here, our goal is to predict the sales demand of the market for minimizing the estate cost. Assume that products are classified into six possible states(
1,2
,
3,4
,
5,6
); for example, 1
= no sale volume, 2
= very low sale volume, 3
= low sale volume, 4
= standard sale volume, 5
= high sale volume, and 6
= very high sale volume. The customers’ sales demand data of five important products can be found in [10].The multivariate Markov chain model of four categorical data sequences,P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D, will be given. By computing the proportions of the occurrences of each state in each sequence, we formulate the initial probability distributions of four categorical data sequences
(34)
x
0
(
1
)
=
(
0.0818,0.4052,0.0483,0.0335,0.0037,0.4275
)
T
,
x
0
(
2
)
=
(
0.3680,0.1970,0.0335,0.0000,0.0037,0.3978
)
T
,
x
0
(
3
)
=
(
0.1450,0.2045,0.0186,0.0000,0.0037,0.6283
)
T
,
x
0
(
4
)
=
(
0.0000,0.3569,0.1338,0.1896,0.0632,0.2565
)
T
.
The transition probability matrix P
(
j
,
k
) can be obtained after normalizing the transition frequency matrix. By solving the corresponding linear programming problem, one can obtain λ
i
,
j. The multivariate Markov chain model is presented as follows:
(35)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
P
(
3,4
)
x
r
(
4
)
,
x
r
+
1
(
4
)
=
P
(
4,4
)
x
r
(
4
)
.
In order to uncover the relations of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E, we add a new categorical data sequence P
r
o
d
u
c
t
E at the back of the original categorical data sequences. With the data sequence ofP
r
o
d
u
c
t
E, the initial probability distribution of P
r
o
d
u
c
t
E is obtained as follows:
(36)
x
0
(
5
)
=
(
0.0000,0.3569,0.1227,0.2268,0.0520,0.2416
)
T
.In the multivariate Markov chain model,λ
j
,
k can be calculated by a corresponding linear programming problem. The multivariate Markov chain model is
(37)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
P
(
3,5
)
x
r
(
5
)
,
x
r
+
1
(
4
)
=
0.2783
P
(
4,4
)
x
r
(
4
)
+
0.7217
P
(
4,5
)
x
r
(
5
)
,
x
r
+
1
(
5
)
=
P
(
5,4
)
x
r
(
4
)
.After calculatingλ
j
,
k by a corresponding linear programming problem, the new multivariate Markov chain model can be presented as follows:
(38)
x
r
+
1
(
1
)
=
P
(
1,2
)
x
r
(
2
)
,
x
r
+
1
(
2
)
=
P
(
2,2
)
x
r
(
2
)
,
x
r
+
1
(
3
)
=
0.0007
P
(
3,4
)
x
r
(
4
)
+
0.9993
P
(
3,5
)
x
r
(
5
)
,
x
r
+
1
(
4
)
=
0.4706
P
(
4,4
)
x
r
(
4
)
+
0.5294
P
(
4,5
)
x
r
(
5
)
,
x
r
+
1
(
5
)
=
P
(
5,4
)
x
r
(
4
)
.
From the results of the new multivariate Markov model, P
r
o
d
u
c
t
A and P
r
o
d
u
c
t
B are closely related. Moreover, the sales demand of P
r
o
d
u
c
t
A depends strongly on P
r
o
d
u
c
t
B. The reason is that the chemical nature of P
r
o
d
u
c
t
A and P
r
o
d
u
c
t
B is the same, only used for different packaging of marketing purposes. P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E are closely related. The fact is that P
r
o
d
u
c
t
s
C and P
r
o
d
u
c
t
E have the same product flavor, only different in packaging.In the following, we use the new multivariate Markov chain model and the multivariate Markov chain model to predict the state of thekth sequence x
t
(
k
) at time t. The maximum probability,
(39)
x
t
(
k
)
=
j
,
if
[
x
t
(
k
)
]
i
≤
[
x
t
(
k
)
]
j
,
∀
1
≤
i
≤
m
,
t
>
1
,
is taken as the state at time t. For evaluating the effectiveness of the new multivariate Markov chain model, prediction results are measured by the prediction accuracy r defined as
(40)
r
=
1
T
-
n
×
∑
t
=
n
+
1
T
‍
δ
t
×
100
%
,
where T is the length of the data sequence and
(41)
δ
t
=
{
1
,
if
x
t
(
k
)
=
θ
t
(
k
)
,
0
,
otherwise
.Note that “t
i
m
e” is CPU time, “ω” is the object function value of the corresponding linear programming problem, “n
p” is the number of the parameters in the models, and the prediction accuracies of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, P
r
o
d
u
c
t
D, and P
r
o
d
u
c
t
E are “A,” “B,” “C,” “D,” and “E,” respectively. Suppose that the results of the multivariate Markov chain model of P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D are obtained. The new multivariate Markov chain model for P
r
o
d
u
c
t
A, P
r
o
d
u
c
t
B, P
r
o
d
u
c
t
C, and P
r
o
d
u
c
t
D adding P
r
o
d
u
c
t
E is denoted as “A,B,C,D add E.” The multivariate Markov chain model is denoted as “Mmodel.” Stop criterion can be found in Matlab function l
i
n
p
r
o
g. The results are presented in Table 1.Table 1
Numerical results of the multivariate Markov chain model and the new multivariate Markov chain model on sales demand prediction.
A
B
C
D
E
T
i
m
e
n
p
ω
M
m
o
d
e
l
0.4176
0.3985
0.6207
0.3525
0.3525
0.0938
25
0.0095
B
,
C
,
D
,
E
a
d
d
A
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
C
,
D
,
E
a
d
d
B
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
D
,
E
a
d
d
C
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
C
,
E
a
d
d
D
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095
A
,
B
,
C
,
D
a
d
d
E
0.4176
0.3985
0.6207
0.3525
0.3525
0.0469
13
0.0095Observing the results from Table1, we find that the object function values of the new model and the multivariate Markov chain model are the same. The prediction accuracies of our new models are comparable to the prediction accuracy of the multivariate Markov chain model. The new multivariate Markov chain model performs better than the multivariate Markov chain model in time consumption and controlled parameters.


## 5.2. Stock Prices Prediction

The data of 12 American stocks’ price from December 17, 2013, to January 16, 2014, are given in the Appendix. They are divided equally into 6 regions as 6 states between maximum price and minimum price of the stocks. The state set of 12 stocks isℳ
=
{
0,1
,
2,3
,
4,5
}. The data of 12 stocks in the Appendix are transformed into categorical data sequences.“t
i
m
e,” “ω,” “
n
p,” and “M
m
o
d
e
l” are denoted the same as those in Section 5.2. Note that “
M
m
o
d
e
l
-
1” is the multivariate Markov chain model of all stocks except AMAP. Suppose that the results of “
M
m
o
d
e
l
-
1” are obtained. The new multivariate Markov chain model which is denoted as “
N
M
m
o
d
e
l” can detect the relations of BIDU, CTRP, GA, EDU, SINA, SOHU, YOKU, XRS, QIHU, HTHT, HMIN, and AMAP. Stop criterion can be found in Matlab order l
i
n
p
r
o
g. The results are presented in Table 2.Table 2
Numerical results of the multivariate Markov chain model and the new multivariate Markov chain model on stock prices prediction.
Time
np
ω
Mmodel
0.7354
144
0.3095
NMmodel
0.1406
34
0.3099From Table2, the object function values of the new multivariate Markov chain model and the multivariate Markov chain model are nearly the same. The CPU time of the new multivariate Markov chain model is the CPU time of the multivariate Markov chain model’s1
/
5. The number of the parameters in the new multivariate Markov chain model is one-third of those in the multivariate Markov chain model. The new multivariate Markov chain model is better than the multivariate Markov chain model in time consumption and controlled parameters.


## 6. Conclusions

In this paper, a new multivariate Markov chain model is proposed. The convergence of the new model is proved. With the results of the multivariate Markov chain model fors categorical data sequences, the relations of the s categorical data sequences and the new sequence can be detected by our new model. The new multivariate Markov chain model only needs 𝒪
(
3
s
) parameters less than 𝒪
(
(
s
+
1
)
2
) which is the number of the parameters in multivariate Markov chain model. Numerical experiments illustrate the benefits of our new model in saving computational resources. The performances of the new multivariate Markov chain model are nearly the same as the multivariate Markov chain model in prediction. Certainly, our model can also be applied in credit risk and other research areas.



---

*Source: 502808-2014-03-23.xml*