Mixing
![Is it appropriate to say that mathematicians âdiscovered a new shapeâ with the scutoid? [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Cesà ro limit of a stochastic matrix
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Let $A$ be a stochastic matrix. Then
beginalign*
lim_t rightarrowinfty A^t
endalign*
may not exist. For example:
beginalign*
A &= beginbmatrix
0 & 1 \
1 & 0
endbmatrix \
A^2t &= I \
A^2t+1 &= A
endalign*
Now define the Cesàro limit $A^infty$ of $A$ to be
beginalign*
lim_t rightarrow infty frac1t sum_k=0^t-1 A^k
endalign*
Then, for the above example,
beginalign*
A^infty = beginbmatrix
frac12 & frac12 \
frac12 & frac12
endbmatrix
endalign*
Intuitively, $A^infty$ represents the long-run average amount of time spent in each state of the Markov chain described by $A$. My question is this: Does every (finite) stochastic matrix have a Cesàro limit? If so, what is the most efficient algorithm for finding this limit?
According to this article, $R^2 = R = RA = AR$ and rank $R geq $ rank $A^infty$ implies $R = A^infty$.
It appears that the rows of $A^infty$ are the normalized eigenvectors of $A^top$ that have a corresponding eigenvalue of 1. How does one determine the correct order and repetition of such eigenvectors, algorithmically?
EDIT: According to this article, the Cesàro limit is guaranteed to exist and is equal to the eigenprojection for the eigenvalue 1 of $A$.
EDIT 2: According to this article,
$$A^infty = X (Y^* X)^-1 Y^*$$
where $X$ are the eigenvectors of $A$ with eigenvalue 1 and $Y$ are the eigenvectors of $A^top$ with eigenvalue 1. I generally get the right result with this approach but sometimes numerical errors seem to result in the wrong Cesàro limit. Is there a more numerically stable approach?
matrices limits markov-chains markov-process regularization
asked Jul 27 at 4:46
user76284
1,1541021
add a comment |Â
up vote
5
down vote
favorite
Let $A$ be a stochastic matrix. Then
beginalign*
lim_t rightarrowinfty A^t
endalign*
may not exist. For example:
beginalign*
A &= beginbmatrix
0 & 1 \
1 & 0
endbmatrix \
A^2t &= I \
A^2t+1 &= A
endalign*
Now define the Cesàro limit $A^infty$ of $A$ to be
beginalign*
lim_t rightarrow infty frac1t sum_k=0^t-1 A^k
endalign*
Then, for the above example,
beginalign*
A^infty = beginbmatrix
frac12 & frac12 \
frac12 & frac12
endbmatrix
endalign*
Intuitively, $A^infty$ represents the long-run average amount of time spent in each state of the Markov chain described by $A$. My question is this: Does every (finite) stochastic matrix have a Cesàro limit? If so, what is the most efficient algorithm for finding this limit?
According to this article, $R^2 = R = RA = AR$ and rank $R geq $ rank $A^infty$ implies $R = A^infty$.
It appears that the rows of $A^infty$ are the normalized eigenvectors of $A^top$ that have a corresponding eigenvalue of 1. How does one determine the correct order and repetition of such eigenvectors, algorithmically?
EDIT: According to this article, the Cesàro limit is guaranteed to exist and is equal to the eigenprojection for the eigenvalue 1 of $A$.
EDIT 2: According to this article,
$$A^infty = X (Y^* X)^-1 Y^*$$
where $X$ are the eigenvectors of $A$ with eigenvalue 1 and $Y$ are the eigenvectors of $A^top$ with eigenvalue 1. I generally get the right result with this approach but sometimes numerical errors seem to result in the wrong Cesàro limit. Is there a more numerically stable approach?
matrices limits markov-chains markov-process regularization
asked Jul 27 at 4:46
user76284
1,1541021
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Let $A$ be a stochastic matrix. Then
beginalign*
lim_t rightarrowinfty A^t
endalign*
may not exist. For example:
beginalign*
A &= beginbmatrix
0 & 1 \
1 & 0
endbmatrix \
A^2t &= I \
A^2t+1 &= A
endalign*
Now define the Cesàro limit $A^infty$ of $A$ to be
beginalign*
lim_t rightarrow infty frac1t sum_k=0^t-1 A^k
endalign*
Then, for the above example,
beginalign*
A^infty = beginbmatrix
frac12 & frac12 \
frac12 & frac12
endbmatrix
endalign*
Intuitively, $A^infty$ represents the long-run average amount of time spent in each state of the Markov chain described by $A$. My question is this: Does every (finite) stochastic matrix have a Cesàro limit? If so, what is the most efficient algorithm for finding this limit?
According to this article, $R^2 = R = RA = AR$ and rank $R geq $ rank $A^infty$ implies $R = A^infty$.
It appears that the rows of $A^infty$ are the normalized eigenvectors of $A^top$ that have a corresponding eigenvalue of 1. How does one determine the correct order and repetition of such eigenvectors, algorithmically?
EDIT: According to this article, the Cesàro limit is guaranteed to exist and is equal to the eigenprojection for the eigenvalue 1 of $A$.
EDIT 2: According to this article,
$$A^infty = X (Y^* X)^-1 Y^*$$
where $X$ are the eigenvectors of $A$ with eigenvalue 1 and $Y$ are the eigenvectors of $A^top$ with eigenvalue 1. I generally get the right result with this approach but sometimes numerical errors seem to result in the wrong Cesàro limit. Is there a more numerically stable approach?
matrices limits markov-chains markov-process regularization
asked Jul 27 at 4:46
user76284
1,1541021
Let $A$ be a stochastic matrix. Then
beginalign*
lim_t rightarrowinfty A^t
endalign*
may not exist. For example:
beginalign*
A &= beginbmatrix
0 & 1 \
1 & 0
endbmatrix \
A^2t &= I \
A^2t+1 &= A
endalign*
Now define the Cesàro limit $A^infty$ of $A$ to be
beginalign*
lim_t rightarrow infty frac1t sum_k=0^t-1 A^k
endalign*
Then, for the above example,
beginalign*
A^infty = beginbmatrix
frac12 & frac12 \
frac12 & frac12
endbmatrix
endalign*
Intuitively, $A^infty$ represents the long-run average amount of time spent in each state of the Markov chain described by $A$. My question is this: Does every (finite) stochastic matrix have a Cesàro limit? If so, what is the most efficient algorithm for finding this limit?
According to this article, $R^2 = R = RA = AR$ and rank $R geq $ rank $A^infty$ implies $R = A^infty$.
It appears that the rows of $A^infty$ are the normalized eigenvectors of $A^top$ that have a corresponding eigenvalue of 1. How does one determine the correct order and repetition of such eigenvectors, algorithmically?
EDIT: According to this article, the Cesàro limit is guaranteed to exist and is equal to the eigenprojection for the eigenvalue 1 of $A$.
EDIT 2: According to this article,
$$A^infty = X (Y^* X)^-1 Y^*$$
where $X$ are the eigenvectors of $A$ with eigenvalue 1 and $Y$ are the eigenvectors of $A^top$ with eigenvalue 1. I generally get the right result with this approach but sometimes numerical errors seem to result in the wrong Cesàro limit. Is there a more numerically stable approach?
matrices limits markov-chains markov-process regularization
asked Jul 27 at 4:46
user76284
1,1541021
edited Jul 27 at 20:13
asked Jul 27 at 4:46
user76284
1,1541021
asked Jul 27 at 4:46
user76284
1,1541021
asked Jul 27 at 4:46
user76284
1,1541021
1,1541021
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
As any entry of $A^k$ is between $0$ and $1$, the sequence $$S_k=frac1t sum_k=0^t-1$$ consists of matrices with entries bounded between $0$ and $1$, and each entry is monotone (weakly) increasing in $k$. So by the monotone sequence theorem, the Cesàro limit exists for any stochastic matrix $A$.
I have no idea what to do about efficiently computing this limit.
answered Jul 27 at 6:52
Kusma
1,097111
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
As any entry of $A^k$ is between $0$ and $1$, the sequence $$S_k=frac1t sum_k=0^t-1$$ consists of matrices with entries bounded between $0$ and $1$, and each entry is monotone (weakly) increasing in $k$. So by the monotone sequence theorem, the Cesàro limit exists for any stochastic matrix $A$.
I have no idea what to do about efficiently computing this limit.
answered Jul 27 at 6:52
Kusma
1,097111
add a comment |Â
up vote
1
down vote
As any entry of $A^k$ is between $0$ and $1$, the sequence $$S_k=frac1t sum_k=0^t-1$$ consists of matrices with entries bounded between $0$ and $1$, and each entry is monotone (weakly) increasing in $k$. So by the monotone sequence theorem, the Cesàro limit exists for any stochastic matrix $A$.
I have no idea what to do about efficiently computing this limit.
answered Jul 27 at 6:52
Kusma
1,097111
add a comment |Â
up vote
1
down vote
up vote
1
down vote
As any entry of $A^k$ is between $0$ and $1$, the sequence $$S_k=frac1t sum_k=0^t-1$$ consists of matrices with entries bounded between $0$ and $1$, and each entry is monotone (weakly) increasing in $k$. So by the monotone sequence theorem, the Cesàro limit exists for any stochastic matrix $A$.
I have no idea what to do about efficiently computing this limit.
answered Jul 27 at 6:52
Kusma
1,097111
As any entry of $A^k$ is between $0$ and $1$, the sequence $$S_k=frac1t sum_k=0^t-1$$ consists of matrices with entries bounded between $0$ and $1$, and each entry is monotone (weakly) increasing in $k$. So by the monotone sequence theorem, the Cesàro limit exists for any stochastic matrix $A$.
I have no idea what to do about efficiently computing this limit.
answered Jul 27 at 6:52
Kusma
1,097111
answered Jul 27 at 6:52
Kusma
1,097111
answered Jul 27 at 6:52
Kusma
1,097111
answered Jul 27 at 6:52
Kusma
1,097111
1,097111
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864062%2fces%25c3%25a0ro-limit-of-a-stochastic-matrix%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password