Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Markov paper

Views: 535
1
\documentclass[12pt]{amsart}
2
3
% special math macros ------------------------------
4
\usepackage{amsmath, setspace, amsrefs, amssymb, amsthm, latexsym, hyperref, verbatim, amsfonts, graphicx, xcolor, float, wrapfig, tabu, tikz}
5
\usetikzlibrary{automata, positioning}
6
%\usepackage{showkeys} %comment this line out for your final version
7
8
% Define Theorem Styles ----------------------------------
9
\theoremstyle{plain}
10
\newtheorem{theorem}{Theorem}[section]
11
\newtheorem{proposition}[theorem]{Proposition}
12
\newtheorem{lemma}[theorem]{Lemma}
13
\newtheorem{corollary}[theorem]{Corollary}
14
\newtheorem{conjecture}[theorem]{Conjecture}
15
16
\theoremstyle{definition}
17
\newtheorem{definition}{\mdseries\scshape Definition}
18
19
\theoremstyle{remark}
20
\newtheorem*{note}{\mdseries\scshape Note}
21
\newtheorem{remark}{\mdseries\scshape Remark}
22
\newtheorem{notation}{\mdseries\scshape Notation}
23
\newtheorem{example}{\mdseries\scshape Example}
24
25
% New Commands ---------------------------------------------------------
26
27
\newcommand{\Z}{\mathbb{Z}}
28
\newcommand{\Zp}{\mathbb{Z}_p}
29
\newcommand{\m}[1]{\marginpar{\addtolength{\baselineskip}{-3pt}{\footnotesize \it #1}}}
30
31
\definecolor{mhcblue}{HTML}{0077CC}
32
33
\begin{document}
34
35
\title{Markov Chains}
36
\author{William J. McMillian}
37
\date{\today}
38
\email{wmcmillian20@amherst.edu}
39
\address{16 Barrett Hill Drive Amherst, MA 01002}
40
\begin{abstract}
41
In this paper we will employ the Asch Conformity experiment to provide a detailed summary of some concepts revolving around Markov chains.
42
\end{abstract}
43
44
\maketitle
45
46
\section{Introduction}
47
48
\textbf{Markov Chains} are a way for us to model a set of sequential processes using a combination of probabilities and matrix operations. Scenarios are modeled as independent states and the transitions between them. Each transition between two states, including a state to itself, has a probability that is independent of the previous states. The probability of transitioning from state A to state B is denoted, $P_{AB}$. The set of all states and probabilities of transitioning between them is called the \textbf{state space}. The state space of the state of the American stock market over a year may look like:
49
50
51
\begin{figure}[h]
52
\includegraphics[width = .75\linewidth]{marketexample.png}
53
\caption{Example Markov chain modeling states of the stock market}
54
\label{fig:Market}
55
\end{figure}
56
\vspace{.5\baselineskip}
57
58
The figure above shows a state space for the three simplified states of a market. The three states are Bull Market(Bu), Bear Market(Be), and Stagnant Market(S). It is visible that from any state, there are three possible transitions. For example from the Bull Market, we can either retain the state of Bull Market, with probability $P_{BuBu} = .9$; or transition from the Bull Market to the Bear Market, with probability $P_{BuBe} = .075$; or transition from the Bull Market to the Stagnant Market, with probability $P_{BuS} = .025$
59
\vspace{.5\baselineskip}
60
61
We use Markov chains to model the real world, from the movement of notes in the music of Bach, to psychological studies like the Asch conformity experiments which we will cover later in this paper. The ability for us to use linear algebra saves us the time, and evades the complexity of large drawing large probability trees with numerous branches.
62
\vspace{.5\baselineskip}
63
64
In the rest of this paper, we will use one of the Asch conformity experiments to define properties of Markov chains. In \S 2 we will gain an understanding of the Asch Conformity Experiment, and in \S 3 we will determine how matrices can be applied to Markov chains to find probabilities of future states.
65
66
67
68
69
70
\section{Asch Conformity Experiment}
71
72
The \textbf{Asch conformity experiments} were series of studies led by Solomon Asch noting the tendencies of subjects to yield to or defy a majority group.
73
\vspace{.5\baselineskip}
74
75
The study was conducted like so. The experimenter, standing at the front of a room, revealed two large white cards: one card with a single line called the standard line, and another card with three lines of varying lengths, the comparison lines. Of the three lines on the second card, one was the same length as the single line on the first. The other lines varied from three quarters of an inch to an inch and three quarters longer or shorter. In a room full of unbeknownst actors, subjects were prompted to verbally announce which of the three comparison lines was the same length as the standard line. On the first two trials, the group unanimously answered correctly, but on the third trial, the actors all gave the wrong answer. The actors gave correct answers occasionally so that the participant would not suspect collusion. By experiment aimed to test the conformity of subjects to the majority in the face of clear physical evidence.
76
\vspace{.5\baselineskip}
77
78
We can model the agreeability of the subject using a 4-state Markov chain. The correct answer will be denoted as A, and the incorrect answer, as B. State 1 is means that the test subject is and will always give answer A, the correct answer. The subject has thus made the decision to select the clearly correct answer despite their counterparts. State 2 is the uncertain A, the subject is not completely confident that they are right, but answers correctly at the time. State 3 is uncertain B, where the subject is erring on the side of the collective, but not certain that they are right. State 4 is permanent B, and the subject has now decided to place their trust in the incorrect collective. These states, respectively, are called permanent A, uncertain A, uncertain B, and permanent B.
79
\vspace{.5\baselineskip}
80
81
82
\begin{center}
83
\begin{figure}[h]
84
\begin{tikzpicture}[font=\sffamily]
85
86
% Add the states
87
\node[state,
88
text=black,
89
draw=none,
90
fill=white!50!black] (1) {1};
91
\node[state,
92
right=2cm of 1,
93
text=black,
94
draw=none,
95
fill=white!50!black] (2) {2};
96
\node[state,
97
right=2cm of 2,
98
text=black,
99
draw=none,
100
fill=white!50!black] (3) {3};
101
\node[state,
102
right=2cm of 3,
103
text=black,
104
draw=none,
105
fill=white!50!black] (4) {4};
106
107
% Connect the states with arrows
108
\draw[every loop,
109
auto=right,
110
line width=1mm,
111
>=latex,
112
draw=black,
113
fill=black]
114
(1) edge[loop above] node {1} (1)
115
(2) edge[auto=left] node {0.06} (1)
116
(2) edge[loop above] node {0.63} (2)
117
(2) edge[bend right, auto=right] node {0.31} (3)
118
(3) edge[bend right, auto=left] node {0.46} (2)
119
(3) edge[loop above] node {0.49} (3)
120
(3) edge[auto=right] node {0.05} (4)
121
(4) edge[loop above] node {1} (4);
122
\end{tikzpicture}
123
\caption{Markov chain model of Asch Conformity Experiment.}
124
\label{fig:Asch Markov}
125
\end{figure}
126
\end{center}
127
\vspace{.5\baselineskip}
128
129
We assume all subjects begin in state 2 because they know the correct answer but have not yet been able to decide how they will react to the actors. Our Markov chain aobve displays the paths and their probabilities, but we can reorganize these into a table like the one below.
130
\vspace{.5\baselineskip}
131
132
\begin{center}
133
\begin{figure}[h]
134
\begin{tabu}{ | X[c] | X[c] | X[c] | X[c] | X[c] | }
135
\hline
136
$i/j$ & 1 & 2 & 3 & 4\\
137
\hline
138
1 & 1 & 0 & 0 & 0 \\
139
\hline
140
2 & 0.06 & 0.63 & 0.31 & 0 \\
141
\hline
142
3 & 0 & 0.46 & 0.49 & 0.05 \\
143
\hline
144
4 & 0 & 0 & 0 & 1\\
145
\hline
146
\end{tabu}
147
\caption{Table of probabilities of changing from state i to state j.}
148
\label{fig:Probability Table}
149
\end{figure}
150
\end{center}
151
\vspace{.5\baselineskip}
152
153
We will continue to discuss these probabilities as $P_{ij}$, where the probability of transitioning from state $i$ to state $j$ between responses.
154
We call states 1 and 4 \textbf{absorbing states}, because once the subject enters that state, the probability of them changing is 0.
155
156
\section {Transition Matrices}
157
158
One question that me may have about this experiment is: How can we accurately predict the probability that a subject will be in a given state in 5 turns? 10 turns? 100?
159
\vspace{.5\baselineskip}
160
161
Let's start with just 2 turns. To do this, we must combine and sum all paths or combinations of 2 steps that begin at 2 and end at a given state.
162
\vspace{2\baselineskip}
163
164
165
State 1: $P_{22} \cdot P_{21} + P_{21} \cdot P_{11} = (.63)(.06) + (.06)(1) = 0.0978$
166
\vspace{.1\baselineskip}
167
168
State 2: $P_{22} \cdot P_{22} + P_{23} \cdot P_{32} = (.63)(.63) + (.31)(.46) = 0.5395$
169
\vspace{.1\baselineskip}
170
171
State 3: $P_{22} \cdot P_{23} + P_{23} \cdot P_{33} = (.63)(.63) + (.31)(.49) = 0.5488$
172
\vspace{.1\baselineskip}
173
174
State 4: $P_{23} \cdot P_{34} = (.31)(.05) = 0.0155$
175
\vspace{.5\baselineskip}
176
177
178
The expression for state 1 can be rewritten as:
179
\vspace{.5\baselineskip}
180
181
182
$= P_{21} \cdot P_{11} + P_{22} \cdot P_{21} + P_{23} \cdot P_{31} + P_{24} \cdot P_{41}$
183
\vspace{.1\baselineskip}
184
185
$= (.06)(1) + (.63)(.06) + (.31)(0) + (0)(0)$
186
\vspace{.1\baselineskip}
187
188
$= 0.0978$
189
\vspace{.5\baselineskip}
190
191
192
Firstly, notice that the expanded form contains all of the paths from state 2 to state 1 that could possibly exist. The non-existent paths contain probabilities equal to 0, and are therefore arithmetically disposed.
193
\vspace{.25\baselineskip}
194
195
The pattern of this multiplication however, strongly resembles matrix multiplication. Let's try to understand why. If we were to convert our table of probabilities into a matrix, it would look like this:
196
\vspace{.5\baselineskip}
197
198
199
\begin{center}
200
\begin{figure}[h]
201
\[
202
P_1 =
203
\left[ {\begin{array}{cccc}
204
1 & 0 & 0 & 0 \\
205
.06 & .63 & .31 & 0 \\
206
0 & .46 & .49 & .05 \\
207
0 & 0 & 0 & 0 \\
208
\end{array} } \right]
209
\]
210
\caption{Transition Matrix of Asch Conformity Experiment.}
211
\label{fig:Transition 1}
212
\end{figure}
213
\end{center}
214
\vspace{.5\baselineskip}
215
216
We call this matrix a \textbf{transition matrix} or \textbf{stochastic matrix}, as we use it to describe the transitions between states. The rewritten expression of state 2 after two rounds of the experiment looks like row 2 multiplied by column 1. This would be the number in the second row and first column if we multiplied our matrix by itself, or $P^2_{21}$
217
\vspace{.5\baselineskip}
218
219
This operation of matrix multiplication does, in fact, produce these combinations of outcomes. Because each transition is treated independently in Markov chain models, we can simply continue to multiply by the original $P^1$ matrix by itself $n$ times, to retrieve the probabilities of states after n rounds. This operation takes all of the paths of $n - 1$ rounds and adds one more step, allowing us to have the probabilities of ending in a given state. Due to the fact that we assume all subject begin in state two, the end probabilities will always lay in row two of the transition matrix.
220
\vspace{.5\baselineskip}
221
222
So to answer the questions we asked at the beginning of this section, our possibilities for all states after 5, 10, and 100 are:
223
\vspace{.5\baselineskip}
224
225
\begin{center}
226
\begin{figure}[h]
227
\[
228
P^5 =
229
\left[ {\begin{array}{cccc}
230
1 & 0 & 0 & 0 \\
231
.19 & .44 & .30 & .07 \\
232
.12 & .45 & .31 & .13 \\
233
0 & 0 & 0 & 1 \\
234
\end{array} } \right]
235
,
236
P^{10} =
237
\left[ {\begin{array}{cccc}
238
1 & 0 & 0 & 0 \\
239
.31 & .33 & .23 & .13 \\
240
.24 & .34 & .23 & .20 \\
241
0 & 0 & 0 & 1 \\
242
\end{array} } \right]
243
\]
244
\end{figure}
245
\vspace{.1\baselineskip}
246
247
\begin{figure}[h]
248
\[
249
P^{100} =
250
\left[ {\begin{array}{cccc}
251
1 & 0 & 0 & 0 \\
252
.66 & 0 & 0 & .34 \\
253
.6 & 0 & 0 & .4 \\
254
0 & 0 & 0 & 1 \\
255
\end{array} } \right]
256
\]
257
\caption{Transition matrices for $n = 5, 10, 100$.}
258
\label{fig: Transition Matrices}
259
\end{figure}
260
\end{center}
261
\vspace{.5\baselineskip}
262
263
\section{Conclusion}
264
In this paper we have explored the Asch Conformity Experiment and the Markov chain used to model it. We discussed transition matrices and how they allow us to determine of the probability of future states. Markov chains are important in the field of statistical modeling. One application of Markov chains is in the creation of music. Markov chains can be assembled where the each node is a chord tone, and music is made by continuing to transition from note to note. This is only one of the uses of Markov chains, as there are many other things in our physical and virtual worlds to be probabilistically modeled.
265
\vspace{.5\baselineskip}
266
267
\begin{thebibliography}{9}
268
269
\bibitem{Market}
270
Markov chain of the stock market,
271
\texttt{https://en.wikipedia.org/wiki/Markov_chain#/media/File:Finance_Markov_chain_example_state_space.svg}
272
\end{thebibliography}
273
274
\end{document}
275
276