King on reduced chessboard $2times 2$ moving randomly, what is the probability that it ends up in one of the corners after $1000$ moves?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
As mentioned in the title, we have a chessboard $2times2$, the king moves with equal probability to each square on the chessboard. King begins from the left upper corner. What is the approximate probability that the king will be standing in the bottom right corner after a thousand moves? I know how to solve it when the number of steps goes to infinity, which would make the probability $1/4$. But is there any trick to do it for a $1000$ moves or is it just "relatively" large number so that I would use my method to solve it as $n$ goes to infinity?
probability markov-chains
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
$endgroup$
|
show 5 more comments
$begingroup$
As mentioned in the title, we have a chessboard $2times2$, the king moves with equal probability to each square on the chessboard. King begins from the left upper corner. What is the approximate probability that the king will be standing in the bottom right corner after a thousand moves? I know how to solve it when the number of steps goes to infinity, which would make the probability $1/4$. But is there any trick to do it for a $1000$ moves or is it just "relatively" large number so that I would use my method to solve it as $n$ goes to infinity?
probability markov-chains
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
$endgroup$
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30
|
show 5 more comments
$begingroup$
As mentioned in the title, we have a chessboard $2times2$, the king moves with equal probability to each square on the chessboard. King begins from the left upper corner. What is the approximate probability that the king will be standing in the bottom right corner after a thousand moves? I know how to solve it when the number of steps goes to infinity, which would make the probability $1/4$. But is there any trick to do it for a $1000$ moves or is it just "relatively" large number so that I would use my method to solve it as $n$ goes to infinity?
probability markov-chains
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
$endgroup$
As mentioned in the title, we have a chessboard $2times2$, the king moves with equal probability to each square on the chessboard. King begins from the left upper corner. What is the approximate probability that the king will be standing in the bottom right corner after a thousand moves? I know how to solve it when the number of steps goes to infinity, which would make the probability $1/4$. But is there any trick to do it for a $1000$ moves or is it just "relatively" large number so that I would use my method to solve it as $n$ goes to infinity?
probability markov-chains
probability markov-chains
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
edited Feb 13 at 12:25
Asaf Karagila♦
306k33437768
306k33437768
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
asked Feb 13 at 9:17
ryszard egginkryszard eggink
406110
406110
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30
|
show 5 more comments
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30
|
show 5 more comments
2 Answers
2
active
oldest
votes
$begingroup$
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $frac13$). Thus $p_n+1=frac13(1-p_n)$.
If $e_n=p_n-frac14$, we then get $e_n+1+frac14=frac13(frac34-e_n)=frac14-frac13e_n$, so $e_n+1=-frac13 e_n$. Since $p_0=0$ and $e_0=-frac14$, we get $e_1000=-frac14cdot left(-frac13right)^1000=frac-14cdot 3^1000$ and $p_1000=frac14-frac14cdot 3^1000=frac3^1000-13^1000cdot 4$.
There it is. Exact, even.
edited Feb 13 at 9:57
jvdhooft
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
$endgroup$
add a comment |
$begingroup$
The following is a Markov chain approach, since OP tagged it:
There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=beginpmatrix2/3&1\1/3&0endpmatrix$$ What is being asked is the value of $$p=beginpmatrix0&1endpmatrixcdot A^1000beginpmatrix1\0endpmatrix=frac14beginpmatrix0&1endpmatrixbeginpmatrix1&-1\1&3endpmatrixbeginpmatrix1&0\0&(-frac13)^1000endpmatrixbeginpmatrix3&1\-1&1endpmatrixbeginpmatrix1\0endpmatrix=frac14left(1-frac13^1000right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3111169%2fking-on-reduced-chessboard-2-times-2-moving-randomly-what-is-the-probability%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $frac13$). Thus $p_n+1=frac13(1-p_n)$.
If $e_n=p_n-frac14$, we then get $e_n+1+frac14=frac13(frac34-e_n)=frac14-frac13e_n$, so $e_n+1=-frac13 e_n$. Since $p_0=0$ and $e_0=-frac14$, we get $e_1000=-frac14cdot left(-frac13right)^1000=frac-14cdot 3^1000$ and $p_1000=frac14-frac14cdot 3^1000=frac3^1000-13^1000cdot 4$.
There it is. Exact, even.
edited Feb 13 at 9:57
jvdhooft
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
$endgroup$
add a comment |
$begingroup$
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $frac13$). Thus $p_n+1=frac13(1-p_n)$.
If $e_n=p_n-frac14$, we then get $e_n+1+frac14=frac13(frac34-e_n)=frac14-frac13e_n$, so $e_n+1=-frac13 e_n$. Since $p_0=0$ and $e_0=-frac14$, we get $e_1000=-frac14cdot left(-frac13right)^1000=frac-14cdot 3^1000$ and $p_1000=frac14-frac14cdot 3^1000=frac3^1000-13^1000cdot 4$.
There it is. Exact, even.
edited Feb 13 at 9:57
jvdhooft
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
$endgroup$
add a comment |
$begingroup$
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $frac13$). Thus $p_n+1=frac13(1-p_n)$.
If $e_n=p_n-frac14$, we then get $e_n+1+frac14=frac13(frac34-e_n)=frac14-frac13e_n$, so $e_n+1=-frac13 e_n$. Since $p_0=0$ and $e_0=-frac14$, we get $e_1000=-frac14cdot left(-frac13right)^1000=frac-14cdot 3^1000$ and $p_1000=frac14-frac14cdot 3^1000=frac3^1000-13^1000cdot 4$.
There it is. Exact, even.
edited Feb 13 at 9:57
jvdhooft
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
$endgroup$
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $frac13$). Thus $p_n+1=frac13(1-p_n)$.
If $e_n=p_n-frac14$, we then get $e_n+1+frac14=frac13(frac34-e_n)=frac14-frac13e_n$, so $e_n+1=-frac13 e_n$. Since $p_0=0$ and $e_0=-frac14$, we get $e_1000=-frac14cdot left(-frac13right)^1000=frac-14cdot 3^1000$ and $p_1000=frac14-frac14cdot 3^1000=frac3^1000-13^1000cdot 4$.
There it is. Exact, even.
edited Feb 13 at 9:57
jvdhooft
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
edited Feb 13 at 9:57
jvdhooft
5,68561641
edited Feb 13 at 9:57
jvdhooft
5,68561641
edited Feb 13 at 9:57
jvdhooft
5,68561641
5,68561641
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
answered Feb 13 at 9:43
jmerryjmerry
12.8k1628
12.8k1628
add a comment |
add a comment |
$begingroup$
The following is a Markov chain approach, since OP tagged it:
There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=beginpmatrix2/3&1\1/3&0endpmatrix$$ What is being asked is the value of $$p=beginpmatrix0&1endpmatrixcdot A^1000beginpmatrix1\0endpmatrix=frac14beginpmatrix0&1endpmatrixbeginpmatrix1&-1\1&3endpmatrixbeginpmatrix1&0\0&(-frac13)^1000endpmatrixbeginpmatrix3&1\-1&1endpmatrixbeginpmatrix1\0endpmatrix=frac14left(1-frac13^1000right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
$endgroup$
add a comment |
$begingroup$
The following is a Markov chain approach, since OP tagged it:
There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=beginpmatrix2/3&1\1/3&0endpmatrix$$ What is being asked is the value of $$p=beginpmatrix0&1endpmatrixcdot A^1000beginpmatrix1\0endpmatrix=frac14beginpmatrix0&1endpmatrixbeginpmatrix1&-1\1&3endpmatrixbeginpmatrix1&0\0&(-frac13)^1000endpmatrixbeginpmatrix3&1\-1&1endpmatrixbeginpmatrix1\0endpmatrix=frac14left(1-frac13^1000right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
$endgroup$
add a comment |
$begingroup$
The following is a Markov chain approach, since OP tagged it:
There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=beginpmatrix2/3&1\1/3&0endpmatrix$$ What is being asked is the value of $$p=beginpmatrix0&1endpmatrixcdot A^1000beginpmatrix1\0endpmatrix=frac14beginpmatrix0&1endpmatrixbeginpmatrix1&-1\1&3endpmatrixbeginpmatrix1&0\0&(-frac13)^1000endpmatrixbeginpmatrix3&1\-1&1endpmatrixbeginpmatrix1\0endpmatrix=frac14left(1-frac13^1000right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
$endgroup$
The following is a Markov chain approach, since OP tagged it:
There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=beginpmatrix2/3&1\1/3&0endpmatrix$$ What is being asked is the value of $$p=beginpmatrix0&1endpmatrixcdot A^1000beginpmatrix1\0endpmatrix=frac14beginpmatrix0&1endpmatrixbeginpmatrix1&-1\1&3endpmatrixbeginpmatrix1&0\0&(-frac13)^1000endpmatrixbeginpmatrix3&1\-1&1endpmatrixbeginpmatrix1\0endpmatrix=frac14left(1-frac13^1000right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
answered Feb 13 at 17:02
ChrystomathChrystomath
1,388512
1,388512
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3111169%2fking-on-reduced-chessboard-2-times-2-moving-randomly-what-is-the-probability%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I don't see why $1000$ should be special in any way.
$endgroup$
– Arthur
Feb 13 at 9:23
$begingroup$
Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4?
$endgroup$
– James
Feb 13 at 9:24
$begingroup$
Just getting to know them, I solved the first part using it.
$endgroup$
– ryszard eggink
Feb 13 at 9:24
$begingroup$
@James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares.
$endgroup$
– Arthur
Feb 13 at 9:24
$begingroup$
It cannot be exactly $frac14$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $fracm3^n$ which cannot be $frac14$ though it could be very close.
$endgroup$
– badjohn
Feb 13 at 9:30