Mixing
What is the expected change of the purchasing game?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Denote the price of item as $N$ cents. The player has infinite coin supply of $1$, $5$, $10$ or $25$ cents. The player keeps drawing one coin of these four types with equal probability, until accumulated value reaches $N$ or beyond.
Question 1: What is the expected change the player could have for $N = 30$?
For example, if the player keeps drawing until he/she has $29$ cents. He/she draws another $5$ cent. Then he/she keeps the change of $4$ cents.
(My thought: for small $N$, such as $N = 30$, we might use Markov chain and solve all adsorbing state probabilities by hand. However, this is unpleasant.)
Question 2: What if the $N$ goes really large?
probability expectation markov-chains dynamic-programming
asked Jul 14 at 20:13
Yi Bao
359
add a comment |Â
up vote
1
down vote
favorite
Denote the price of item as $N$ cents. The player has infinite coin supply of $1$, $5$, $10$ or $25$ cents. The player keeps drawing one coin of these four types with equal probability, until accumulated value reaches $N$ or beyond.
Question 1: What is the expected change the player could have for $N = 30$?
For example, if the player keeps drawing until he/she has $29$ cents. He/she draws another $5$ cent. Then he/she keeps the change of $4$ cents.
(My thought: for small $N$, such as $N = 30$, we might use Markov chain and solve all adsorbing state probabilities by hand. However, this is unpleasant.)
Question 2: What if the $N$ goes really large?
probability expectation markov-chains dynamic-programming
asked Jul 14 at 20:13
Yi Bao
359
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Denote the price of item as $N$ cents. The player has infinite coin supply of $1$, $5$, $10$ or $25$ cents. The player keeps drawing one coin of these four types with equal probability, until accumulated value reaches $N$ or beyond.
Question 1: What is the expected change the player could have for $N = 30$?
For example, if the player keeps drawing until he/she has $29$ cents. He/she draws another $5$ cent. Then he/she keeps the change of $4$ cents.
(My thought: for small $N$, such as $N = 30$, we might use Markov chain and solve all adsorbing state probabilities by hand. However, this is unpleasant.)
Question 2: What if the $N$ goes really large?
probability expectation markov-chains dynamic-programming
asked Jul 14 at 20:13
Yi Bao
359
Denote the price of item as $N$ cents. The player has infinite coin supply of $1$, $5$, $10$ or $25$ cents. The player keeps drawing one coin of these four types with equal probability, until accumulated value reaches $N$ or beyond.
Question 1: What is the expected change the player could have for $N = 30$?
For example, if the player keeps drawing until he/she has $29$ cents. He/she draws another $5$ cent. Then he/she keeps the change of $4$ cents.
(My thought: for small $N$, such as $N = 30$, we might use Markov chain and solve all adsorbing state probabilities by hand. However, this is unpleasant.)
Question 2: What if the $N$ goes really large?
probability expectation markov-chains dynamic-programming
asked Jul 14 at 20:13
Yi Bao
359
asked Jul 14 at 20:13
Yi Bao
359
asked Jul 14 at 20:13
Yi Bao
359
asked Jul 14 at 20:13
Yi Bao
359
359
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23
add a comment |Â
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
I'll answer Question $2$ on the limit of the expected change as $Ntoinfty$.
In a quasisteady state, the process is expected to progress by the average coin value $frac1+5+10+254=frac414$ in each step. It follows that each sum has probability $frac441$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.
This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $Nle vle N+24$ can be reached with $k$ different coins before the game ends, it contributes $frac k4cdotfrac441(v-N)=frac k41(v-N)$ to the change.
The sum $N$ can be reached with any coin value, but it contributes $0$ change.
The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $frac341sum_k=1^4k=frac3041$.
The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $frac241sum_k=5^9k=frac7041$.
The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $frac141sum_k=10^24k=frac25541$.
So the total expected change in the limit $Ntoinfty$ is $frac30+70+25541=frac35541approx8.66$.
I really do have to share my favourite change joke with you at this point:
A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?†The Zen monk replies: “Make me one with everything.†Afterwards, the Zen monk pays and says: “Where's my change?†The vendor replies: “Change comes from within.â€
answered Jul 14 at 20:43
joriki
165k10180328
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
 |Â
show 5 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
I'll answer Question $2$ on the limit of the expected change as $Ntoinfty$.
In a quasisteady state, the process is expected to progress by the average coin value $frac1+5+10+254=frac414$ in each step. It follows that each sum has probability $frac441$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.
This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $Nle vle N+24$ can be reached with $k$ different coins before the game ends, it contributes $frac k4cdotfrac441(v-N)=frac k41(v-N)$ to the change.
The sum $N$ can be reached with any coin value, but it contributes $0$ change.
The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $frac341sum_k=1^4k=frac3041$.
The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $frac241sum_k=5^9k=frac7041$.
The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $frac141sum_k=10^24k=frac25541$.
So the total expected change in the limit $Ntoinfty$ is $frac30+70+25541=frac35541approx8.66$.
I really do have to share my favourite change joke with you at this point:
A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?†The Zen monk replies: “Make me one with everything.†Afterwards, the Zen monk pays and says: “Where's my change?†The vendor replies: “Change comes from within.â€
answered Jul 14 at 20:43
joriki
165k10180328
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
 |Â
show 5 more comments
up vote
1
down vote
accepted
I'll answer Question $2$ on the limit of the expected change as $Ntoinfty$.
In a quasisteady state, the process is expected to progress by the average coin value $frac1+5+10+254=frac414$ in each step. It follows that each sum has probability $frac441$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.
This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $Nle vle N+24$ can be reached with $k$ different coins before the game ends, it contributes $frac k4cdotfrac441(v-N)=frac k41(v-N)$ to the change.
The sum $N$ can be reached with any coin value, but it contributes $0$ change.
The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $frac341sum_k=1^4k=frac3041$.
The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $frac241sum_k=5^9k=frac7041$.
The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $frac141sum_k=10^24k=frac25541$.
So the total expected change in the limit $Ntoinfty$ is $frac30+70+25541=frac35541approx8.66$.
I really do have to share my favourite change joke with you at this point:
A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?†The Zen monk replies: “Make me one with everything.†Afterwards, the Zen monk pays and says: “Where's my change?†The vendor replies: “Change comes from within.â€
answered Jul 14 at 20:43
joriki
165k10180328
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
 |Â
show 5 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
I'll answer Question $2$ on the limit of the expected change as $Ntoinfty$.
In a quasisteady state, the process is expected to progress by the average coin value $frac1+5+10+254=frac414$ in each step. It follows that each sum has probability $frac441$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.
This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $Nle vle N+24$ can be reached with $k$ different coins before the game ends, it contributes $frac k4cdotfrac441(v-N)=frac k41(v-N)$ to the change.
The sum $N$ can be reached with any coin value, but it contributes $0$ change.
The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $frac341sum_k=1^4k=frac3041$.
The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $frac241sum_k=5^9k=frac7041$.
The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $frac141sum_k=10^24k=frac25541$.
So the total expected change in the limit $Ntoinfty$ is $frac30+70+25541=frac35541approx8.66$.
I really do have to share my favourite change joke with you at this point:
A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?†The Zen monk replies: “Make me one with everything.†Afterwards, the Zen monk pays and says: “Where's my change?†The vendor replies: “Change comes from within.â€
answered Jul 14 at 20:43
joriki
165k10180328
I'll answer Question $2$ on the limit of the expected change as $Ntoinfty$.
In a quasisteady state, the process is expected to progress by the average coin value $frac1+5+10+254=frac414$ in each step. It follows that each sum has probability $frac441$ of being attained at some point. Also, since all coins are equiprobable, a sum that is attained at some point is equally likely to be attained by any of the coins.
This, together with linearity of expectation, allows you to sum up the expected change contributions from the sums exceeding $N$. If an attainable final value $Nle vle N+24$ can be reached with $k$ different coins before the game ends, it contributes $frac k4cdotfrac441(v-N)=frac k41(v-N)$ to the change.
The sum $N$ can be reached with any coin value, but it contributes $0$ change.
The $4$ sums $N+1$ through $N+4$ can be reached with the three coin values $5$, $10$ and $25$, so they contribute $frac341sum_k=1^4k=frac3041$.
The $5$ sums $N+5$ through $N+9$ can be reached with the two coin values $10$ and $25$, so they contribute $frac241sum_k=5^9k=frac7041$.
The $15$ sums $N+10$ through $N+24$ can be reached with the one coin value $25$, so they contribute $frac141sum_k=10^24k=frac25541$.
So the total expected change in the limit $Ntoinfty$ is $frac30+70+25541=frac35541approx8.66$.
I really do have to share my favourite change joke with you at this point:
A Zen monk orders chips (or, in US-American: fries). The vendor asks: “With ketchup or mayonnaise?†The Zen monk replies: “Make me one with everything.†Afterwards, the Zen monk pays and says: “Where's my change?†The vendor replies: “Change comes from within.â€
answered Jul 14 at 20:43
joriki
165k10180328
edited Jul 14 at 20:48
answered Jul 14 at 20:43
joriki
165k10180328
answered Jul 14 at 20:43
joriki
165k10180328
answered Jul 14 at 20:43
joriki
165k10180328
165k10180328
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
 |Â
show 5 more comments
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Simulation says you are correct. Let me read it through.
– Yi Bao
Jul 14 at 20:44
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
Brilliant! What is your intuition at the beginning?
– Yi Bao
Jul 14 at 20:57
1
1
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
@YiBao: How do you mean? The intuition underlying the beginning of the post, or what my intuition was at the beginning of thinking about the problem?
– joriki
Jul 14 at 21:02
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
I would say the intuition underlying the beginning of the post.
– Yi Bao
Jul 14 at 21:04
1
1
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
Thank you very much for all these helpful comments, joriki!
– Yi Bao
Jul 14 at 21:59
 |Â
show 5 more comments
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%2f2851917%2fwhat-is-the-expected-change-of-the-purchasing-game%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
There is a useful recursion...If $p_n$ is the probability that your total equals $n$ at some point then $p_n=.25times (p_n-25+p_n-10+p_n-5+p_n-1)$ where $p_i=0$ for $i<0$, $p_0=1$. Working with that should resolve your questions.
– lulu
Jul 14 at 20:23