Mixing
Candy machines and optimal strategy in terms of expected value
$begingroup$
Problem
We have three candy machines: call them G (good), B (bad) and M (mixed) . G always gives you a candy when you put 1$. B never gives you a candy when you put 1$. M gives you a candy with probability $1/2$ when you put 1$. You want a candy and you approach the three machines but you don't know which one is G, B or M. You use the following strategy. You approach a random machine. If you don't get a candy in $n$ trials, you change a machine. If you don't get a candy from the second machine in $k$ trials, you change to the remaining machine. At most, we can pay for a candy $n+k+1$ $. We want to calculate the expected cost of obtaining a candy using this strategy. Is it the case that $k=n=1$ is the optimal strategy, i.e. yielding the least expected cost of obtaining a candy?
Attempt of solution
Currently, my thinking is the following. Consider the indicator random variable $X_i = 1$ meaning that we pay 1$ at stage $i$. Observe that:
$P(X_1 = 1) = 1$ (we always pay 1$ at the beginning)
$P(X_2 = 1) = frac{1}{3} + frac{1}{3}frac{1}{2}$ (you pay at stage $2$ iff you don't receive a candy at stage $1$ which happens either when you choose $B$ with probability one third or you choose $M$ with probability one third and then $M$ doesn't give you a candy with probability one half)
$P(X_3 = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^2$ (similar justification as previously but keeping in mind that you consider an event of not obtaining a candy at stages $1$ and $2$)- $dots$
- $P(X_{n+1} = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^n$
$P(X_{n+2} = 1) = frac{1}{6} frac{1}{2} + frac{1}{6}(frac{1}{2})^n$ (= the probability that we don't receive a candy at stages up to $n+1$. This could happen either when we first happen to choose B and then M, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6} frac{1}{2}$, or when we first choose M and than B, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6}(frac{1}{2})^n$)- $dots$
$P(X_{n+k+1} = 1) = frac{1}{6} (frac{1}{2})^k + frac{1}{6}(frac{1}{2})^n$
We are interested in $E(Sigma_{i=1}^{n+k+1} X_i)$. Using linearity of expectation, we may write:
$$E(Sigma_{i=1}^{n+k+1} X_i) = 1 + E(Sigma_{i=2}^{n+1}X_i) + E(Sigma_{j=n+2}^{n+k+1}X_j) = $$
$$=1 + Sigma_{i=1}^n(frac{1}{3} + frac{1}{3}(frac{1}{2})^i) + Sigma_{j=1}^k(frac{1}{6}(frac{1}{2})^j + frac{1}{6}(frac{1}{2})^n)=$$
$$= 1 + frac{1}{3}n + frac{1}{3}Sigma_{i=1}^nfrac{1}{2^i} + k frac{1}{6} frac{1}{2^n} + frac{1}{6}Sigma_{j=1}^k frac{1}{2^j}$$
Now, we can easily observe that when $n$ is fixed and we make $k$ bigger, $E$ also grows. This excludes strategies $n < k$ from being optimal. We can go somewhat further by observing that:
$$ Sigma_{i=1}^nfrac{1}{2^i} = frac{1 - frac{1}{2}^{n+1}}{1 - frac{1}{2}}- 1 = 1 - (frac{1}{2})^n$$
This gives you:
$$E(X) = 1 + frac{1}{3}n + frac{1}{3}(1 - (frac{1}{2})^n) + k frac{1}{6} frac{1}{2^n} + frac{1}{6}(1 - (frac{1}{2})^k)=$$
$$ 1 + frac{1}{3}n + frac{1}{3} - frac{1}{3}(frac{1}{2})^n + k frac{1}{6} frac{1}{2^n} + frac{1}{6} - frac{1}{6}(frac{1}{2})^k$$
$$6 E(X) = 9 + 2n - 2 (frac{1}{2})^n + k frac{1}{2^n} - (frac{1}{2})^k$$
$$6 E(X) = 9 + 2n + (k-2)frac{1}{2^n} - (frac{1}{2})^k$$
This makes it clear that when you keep $k$ fixed and make $n$ bigger, $E$ grows as well. This excludes strategies $k < n$ from being optimal. So the optimal strategy should satisfy $n=k$. So let's assume that in the equation for $E$:
$$6 E(X) = 9 + 2n + (n-2)frac{1}{2^n} - (frac{1}{2})^n=$$
$$ 9 + 2n + (n-3)frac{1}{2^n}$$
I will not go further now, but, at least know, it's clear for me that the right hand side of the above equation assumes minimal value for $n=1$ which yields the strategy $n=k=1$ as optimal.
probability probability-distributions optimization recreational-mathematics expected-value
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
$endgroup$
add a comment |
$begingroup$
Problem
We have three candy machines: call them G (good), B (bad) and M (mixed) . G always gives you a candy when you put 1$. B never gives you a candy when you put 1$. M gives you a candy with probability $1/2$ when you put 1$. You want a candy and you approach the three machines but you don't know which one is G, B or M. You use the following strategy. You approach a random machine. If you don't get a candy in $n$ trials, you change a machine. If you don't get a candy from the second machine in $k$ trials, you change to the remaining machine. At most, we can pay for a candy $n+k+1$ $. We want to calculate the expected cost of obtaining a candy using this strategy. Is it the case that $k=n=1$ is the optimal strategy, i.e. yielding the least expected cost of obtaining a candy?
Attempt of solution
Currently, my thinking is the following. Consider the indicator random variable $X_i = 1$ meaning that we pay 1$ at stage $i$. Observe that:
$P(X_1 = 1) = 1$ (we always pay 1$ at the beginning)
$P(X_2 = 1) = frac{1}{3} + frac{1}{3}frac{1}{2}$ (you pay at stage $2$ iff you don't receive a candy at stage $1$ which happens either when you choose $B$ with probability one third or you choose $M$ with probability one third and then $M$ doesn't give you a candy with probability one half)
$P(X_3 = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^2$ (similar justification as previously but keeping in mind that you consider an event of not obtaining a candy at stages $1$ and $2$)- $dots$
- $P(X_{n+1} = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^n$
$P(X_{n+2} = 1) = frac{1}{6} frac{1}{2} + frac{1}{6}(frac{1}{2})^n$ (= the probability that we don't receive a candy at stages up to $n+1$. This could happen either when we first happen to choose B and then M, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6} frac{1}{2}$, or when we first choose M and than B, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6}(frac{1}{2})^n$)- $dots$
$P(X_{n+k+1} = 1) = frac{1}{6} (frac{1}{2})^k + frac{1}{6}(frac{1}{2})^n$
We are interested in $E(Sigma_{i=1}^{n+k+1} X_i)$. Using linearity of expectation, we may write:
$$E(Sigma_{i=1}^{n+k+1} X_i) = 1 + E(Sigma_{i=2}^{n+1}X_i) + E(Sigma_{j=n+2}^{n+k+1}X_j) = $$
$$=1 + Sigma_{i=1}^n(frac{1}{3} + frac{1}{3}(frac{1}{2})^i) + Sigma_{j=1}^k(frac{1}{6}(frac{1}{2})^j + frac{1}{6}(frac{1}{2})^n)=$$
$$= 1 + frac{1}{3}n + frac{1}{3}Sigma_{i=1}^nfrac{1}{2^i} + k frac{1}{6} frac{1}{2^n} + frac{1}{6}Sigma_{j=1}^k frac{1}{2^j}$$
Now, we can easily observe that when $n$ is fixed and we make $k$ bigger, $E$ also grows. This excludes strategies $n < k$ from being optimal. We can go somewhat further by observing that:
$$ Sigma_{i=1}^nfrac{1}{2^i} = frac{1 - frac{1}{2}^{n+1}}{1 - frac{1}{2}}- 1 = 1 - (frac{1}{2})^n$$
This gives you:
$$E(X) = 1 + frac{1}{3}n + frac{1}{3}(1 - (frac{1}{2})^n) + k frac{1}{6} frac{1}{2^n} + frac{1}{6}(1 - (frac{1}{2})^k)=$$
$$ 1 + frac{1}{3}n + frac{1}{3} - frac{1}{3}(frac{1}{2})^n + k frac{1}{6} frac{1}{2^n} + frac{1}{6} - frac{1}{6}(frac{1}{2})^k$$
$$6 E(X) = 9 + 2n - 2 (frac{1}{2})^n + k frac{1}{2^n} - (frac{1}{2})^k$$
$$6 E(X) = 9 + 2n + (k-2)frac{1}{2^n} - (frac{1}{2})^k$$
This makes it clear that when you keep $k$ fixed and make $n$ bigger, $E$ grows as well. This excludes strategies $k < n$ from being optimal. So the optimal strategy should satisfy $n=k$. So let's assume that in the equation for $E$:
$$6 E(X) = 9 + 2n + (n-2)frac{1}{2^n} - (frac{1}{2})^n=$$
$$ 9 + 2n + (n-3)frac{1}{2^n}$$
I will not go further now, but, at least know, it's clear for me that the right hand side of the above equation assumes minimal value for $n=1$ which yields the strategy $n=k=1$ as optimal.
probability probability-distributions optimization recreational-mathematics expected-value
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
$endgroup$
add a comment |
$begingroup$
Problem
We have three candy machines: call them G (good), B (bad) and M (mixed) . G always gives you a candy when you put 1$. B never gives you a candy when you put 1$. M gives you a candy with probability $1/2$ when you put 1$. You want a candy and you approach the three machines but you don't know which one is G, B or M. You use the following strategy. You approach a random machine. If you don't get a candy in $n$ trials, you change a machine. If you don't get a candy from the second machine in $k$ trials, you change to the remaining machine. At most, we can pay for a candy $n+k+1$ $. We want to calculate the expected cost of obtaining a candy using this strategy. Is it the case that $k=n=1$ is the optimal strategy, i.e. yielding the least expected cost of obtaining a candy?
Attempt of solution
Currently, my thinking is the following. Consider the indicator random variable $X_i = 1$ meaning that we pay 1$ at stage $i$. Observe that:
$P(X_1 = 1) = 1$ (we always pay 1$ at the beginning)
$P(X_2 = 1) = frac{1}{3} + frac{1}{3}frac{1}{2}$ (you pay at stage $2$ iff you don't receive a candy at stage $1$ which happens either when you choose $B$ with probability one third or you choose $M$ with probability one third and then $M$ doesn't give you a candy with probability one half)
$P(X_3 = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^2$ (similar justification as previously but keeping in mind that you consider an event of not obtaining a candy at stages $1$ and $2$)- $dots$
- $P(X_{n+1} = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^n$
$P(X_{n+2} = 1) = frac{1}{6} frac{1}{2} + frac{1}{6}(frac{1}{2})^n$ (= the probability that we don't receive a candy at stages up to $n+1$. This could happen either when we first happen to choose B and then M, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6} frac{1}{2}$, or when we first choose M and than B, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6}(frac{1}{2})^n$)- $dots$
$P(X_{n+k+1} = 1) = frac{1}{6} (frac{1}{2})^k + frac{1}{6}(frac{1}{2})^n$
We are interested in $E(Sigma_{i=1}^{n+k+1} X_i)$. Using linearity of expectation, we may write:
$$E(Sigma_{i=1}^{n+k+1} X_i) = 1 + E(Sigma_{i=2}^{n+1}X_i) + E(Sigma_{j=n+2}^{n+k+1}X_j) = $$
$$=1 + Sigma_{i=1}^n(frac{1}{3} + frac{1}{3}(frac{1}{2})^i) + Sigma_{j=1}^k(frac{1}{6}(frac{1}{2})^j + frac{1}{6}(frac{1}{2})^n)=$$
$$= 1 + frac{1}{3}n + frac{1}{3}Sigma_{i=1}^nfrac{1}{2^i} + k frac{1}{6} frac{1}{2^n} + frac{1}{6}Sigma_{j=1}^k frac{1}{2^j}$$
Now, we can easily observe that when $n$ is fixed and we make $k$ bigger, $E$ also grows. This excludes strategies $n < k$ from being optimal. We can go somewhat further by observing that:
$$ Sigma_{i=1}^nfrac{1}{2^i} = frac{1 - frac{1}{2}^{n+1}}{1 - frac{1}{2}}- 1 = 1 - (frac{1}{2})^n$$
This gives you:
$$E(X) = 1 + frac{1}{3}n + frac{1}{3}(1 - (frac{1}{2})^n) + k frac{1}{6} frac{1}{2^n} + frac{1}{6}(1 - (frac{1}{2})^k)=$$
$$ 1 + frac{1}{3}n + frac{1}{3} - frac{1}{3}(frac{1}{2})^n + k frac{1}{6} frac{1}{2^n} + frac{1}{6} - frac{1}{6}(frac{1}{2})^k$$
$$6 E(X) = 9 + 2n - 2 (frac{1}{2})^n + k frac{1}{2^n} - (frac{1}{2})^k$$
$$6 E(X) = 9 + 2n + (k-2)frac{1}{2^n} - (frac{1}{2})^k$$
This makes it clear that when you keep $k$ fixed and make $n$ bigger, $E$ grows as well. This excludes strategies $k < n$ from being optimal. So the optimal strategy should satisfy $n=k$. So let's assume that in the equation for $E$:
$$6 E(X) = 9 + 2n + (n-2)frac{1}{2^n} - (frac{1}{2})^n=$$
$$ 9 + 2n + (n-3)frac{1}{2^n}$$
I will not go further now, but, at least know, it's clear for me that the right hand side of the above equation assumes minimal value for $n=1$ which yields the strategy $n=k=1$ as optimal.
probability probability-distributions optimization recreational-mathematics expected-value
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
$endgroup$
Problem
We have three candy machines: call them G (good), B (bad) and M (mixed) . G always gives you a candy when you put 1$. B never gives you a candy when you put 1$. M gives you a candy with probability $1/2$ when you put 1$. You want a candy and you approach the three machines but you don't know which one is G, B or M. You use the following strategy. You approach a random machine. If you don't get a candy in $n$ trials, you change a machine. If you don't get a candy from the second machine in $k$ trials, you change to the remaining machine. At most, we can pay for a candy $n+k+1$ $. We want to calculate the expected cost of obtaining a candy using this strategy. Is it the case that $k=n=1$ is the optimal strategy, i.e. yielding the least expected cost of obtaining a candy?
Attempt of solution
Currently, my thinking is the following. Consider the indicator random variable $X_i = 1$ meaning that we pay 1$ at stage $i$. Observe that:
$P(X_1 = 1) = 1$ (we always pay 1$ at the beginning)
$P(X_2 = 1) = frac{1}{3} + frac{1}{3}frac{1}{2}$ (you pay at stage $2$ iff you don't receive a candy at stage $1$ which happens either when you choose $B$ with probability one third or you choose $M$ with probability one third and then $M$ doesn't give you a candy with probability one half)
$P(X_3 = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^2$ (similar justification as previously but keeping in mind that you consider an event of not obtaining a candy at stages $1$ and $2$)- $dots$
- $P(X_{n+1} = 1) = frac{1}{3} + frac{1}{3}(frac{1}{2})^n$
$P(X_{n+2} = 1) = frac{1}{6} frac{1}{2} + frac{1}{6}(frac{1}{2})^n$ (= the probability that we don't receive a candy at stages up to $n+1$. This could happen either when we first happen to choose B and then M, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6} frac{1}{2}$, or when we first choose M and than B, in which case the probability of not obtaining a candy in $n+1$ trials is $frac{1}{6}(frac{1}{2})^n$)- $dots$
$P(X_{n+k+1} = 1) = frac{1}{6} (frac{1}{2})^k + frac{1}{6}(frac{1}{2})^n$
We are interested in $E(Sigma_{i=1}^{n+k+1} X_i)$. Using linearity of expectation, we may write:
$$E(Sigma_{i=1}^{n+k+1} X_i) = 1 + E(Sigma_{i=2}^{n+1}X_i) + E(Sigma_{j=n+2}^{n+k+1}X_j) = $$
$$=1 + Sigma_{i=1}^n(frac{1}{3} + frac{1}{3}(frac{1}{2})^i) + Sigma_{j=1}^k(frac{1}{6}(frac{1}{2})^j + frac{1}{6}(frac{1}{2})^n)=$$
$$= 1 + frac{1}{3}n + frac{1}{3}Sigma_{i=1}^nfrac{1}{2^i} + k frac{1}{6} frac{1}{2^n} + frac{1}{6}Sigma_{j=1}^k frac{1}{2^j}$$
Now, we can easily observe that when $n$ is fixed and we make $k$ bigger, $E$ also grows. This excludes strategies $n < k$ from being optimal. We can go somewhat further by observing that:
$$ Sigma_{i=1}^nfrac{1}{2^i} = frac{1 - frac{1}{2}^{n+1}}{1 - frac{1}{2}}- 1 = 1 - (frac{1}{2})^n$$
This gives you:
$$E(X) = 1 + frac{1}{3}n + frac{1}{3}(1 - (frac{1}{2})^n) + k frac{1}{6} frac{1}{2^n} + frac{1}{6}(1 - (frac{1}{2})^k)=$$
$$ 1 + frac{1}{3}n + frac{1}{3} - frac{1}{3}(frac{1}{2})^n + k frac{1}{6} frac{1}{2^n} + frac{1}{6} - frac{1}{6}(frac{1}{2})^k$$
$$6 E(X) = 9 + 2n - 2 (frac{1}{2})^n + k frac{1}{2^n} - (frac{1}{2})^k$$
$$6 E(X) = 9 + 2n + (k-2)frac{1}{2^n} - (frac{1}{2})^k$$
This makes it clear that when you keep $k$ fixed and make $n$ bigger, $E$ grows as well. This excludes strategies $k < n$ from being optimal. So the optimal strategy should satisfy $n=k$. So let's assume that in the equation for $E$:
$$6 E(X) = 9 + 2n + (n-2)frac{1}{2^n} - (frac{1}{2})^n=$$
$$ 9 + 2n + (n-3)frac{1}{2^n}$$
I will not go further now, but, at least know, it's clear for me that the right hand side of the above equation assumes minimal value for $n=1$ which yields the strategy $n=k=1$ as optimal.
probability probability-distributions optimization recreational-mathematics expected-value
probability probability-distributions optimization recreational-mathematics expected-value
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
edited Jan 18 at 10:22
dkalocinski
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
asked Jan 17 at 13:12
dkalocinskidkalocinski
526
526
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Clearly you always want $k = 1$. If you have tried two machines and gotten candy from neither, the last one must be the Good one, so there's no reason not to try that next. This leaves our choice of $n$. Intuitively it's clear that this one should be 1 as well: after failing to get a candy from the machine once, it's either Bad or Mixed with probability 1/2, while both other machines are Good with probability 1/2, so those machines definitely appear more appealing. But let's make this formal.
The strategy $n = k = 1$ nets you an expected value of $5/3$ tries until you obtain a candy. Now suppose that $n geq 2$. Write $X$ for the number of tries, and $B, M, G$ for the event that the first machine you try is the Bad, Mixed, Good one. Then:
$$
begin{align*}
mathbb{E}(X) &= underbrace{mathbb{E}(X mid B)}_{geq n + 1}mathbb P(B) + underbrace{mathbb{E}(X mid M)}_{> 1}mathbb P(M) + underbrace{mathbb{E}(X mid G)}_{=1}mathbb P(G)\
&>(n+1)frac13+ 1times frac13 + 1 times frac13\
& geq frac53.
end{align*}
$$
Here the "strictly greater than" on line 2 stems from the fact that the expected number of tries when the first machine is Mixed is actually strictly greater than 1. Thus $n = k = 1$ is optimal.
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
$endgroup$
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
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%2f3076954%2fcandy-machines-and-optimal-strategy-in-terms-of-expected-value%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Clearly you always want $k = 1$. If you have tried two machines and gotten candy from neither, the last one must be the Good one, so there's no reason not to try that next. This leaves our choice of $n$. Intuitively it's clear that this one should be 1 as well: after failing to get a candy from the machine once, it's either Bad or Mixed with probability 1/2, while both other machines are Good with probability 1/2, so those machines definitely appear more appealing. But let's make this formal.
The strategy $n = k = 1$ nets you an expected value of $5/3$ tries until you obtain a candy. Now suppose that $n geq 2$. Write $X$ for the number of tries, and $B, M, G$ for the event that the first machine you try is the Bad, Mixed, Good one. Then:
$$
begin{align*}
mathbb{E}(X) &= underbrace{mathbb{E}(X mid B)}_{geq n + 1}mathbb P(B) + underbrace{mathbb{E}(X mid M)}_{> 1}mathbb P(M) + underbrace{mathbb{E}(X mid G)}_{=1}mathbb P(G)\
&>(n+1)frac13+ 1times frac13 + 1 times frac13\
& geq frac53.
end{align*}
$$
Here the "strictly greater than" on line 2 stems from the fact that the expected number of tries when the first machine is Mixed is actually strictly greater than 1. Thus $n = k = 1$ is optimal.
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
$endgroup$
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
add a comment |
$begingroup$
Clearly you always want $k = 1$. If you have tried two machines and gotten candy from neither, the last one must be the Good one, so there's no reason not to try that next. This leaves our choice of $n$. Intuitively it's clear that this one should be 1 as well: after failing to get a candy from the machine once, it's either Bad or Mixed with probability 1/2, while both other machines are Good with probability 1/2, so those machines definitely appear more appealing. But let's make this formal.
The strategy $n = k = 1$ nets you an expected value of $5/3$ tries until you obtain a candy. Now suppose that $n geq 2$. Write $X$ for the number of tries, and $B, M, G$ for the event that the first machine you try is the Bad, Mixed, Good one. Then:
$$
begin{align*}
mathbb{E}(X) &= underbrace{mathbb{E}(X mid B)}_{geq n + 1}mathbb P(B) + underbrace{mathbb{E}(X mid M)}_{> 1}mathbb P(M) + underbrace{mathbb{E}(X mid G)}_{=1}mathbb P(G)\
&>(n+1)frac13+ 1times frac13 + 1 times frac13\
& geq frac53.
end{align*}
$$
Here the "strictly greater than" on line 2 stems from the fact that the expected number of tries when the first machine is Mixed is actually strictly greater than 1. Thus $n = k = 1$ is optimal.
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
$endgroup$
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
add a comment |
$begingroup$
Clearly you always want $k = 1$. If you have tried two machines and gotten candy from neither, the last one must be the Good one, so there's no reason not to try that next. This leaves our choice of $n$. Intuitively it's clear that this one should be 1 as well: after failing to get a candy from the machine once, it's either Bad or Mixed with probability 1/2, while both other machines are Good with probability 1/2, so those machines definitely appear more appealing. But let's make this formal.
The strategy $n = k = 1$ nets you an expected value of $5/3$ tries until you obtain a candy. Now suppose that $n geq 2$. Write $X$ for the number of tries, and $B, M, G$ for the event that the first machine you try is the Bad, Mixed, Good one. Then:
$$
begin{align*}
mathbb{E}(X) &= underbrace{mathbb{E}(X mid B)}_{geq n + 1}mathbb P(B) + underbrace{mathbb{E}(X mid M)}_{> 1}mathbb P(M) + underbrace{mathbb{E}(X mid G)}_{=1}mathbb P(G)\
&>(n+1)frac13+ 1times frac13 + 1 times frac13\
& geq frac53.
end{align*}
$$
Here the "strictly greater than" on line 2 stems from the fact that the expected number of tries when the first machine is Mixed is actually strictly greater than 1. Thus $n = k = 1$ is optimal.
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
$endgroup$
Clearly you always want $k = 1$. If you have tried two machines and gotten candy from neither, the last one must be the Good one, so there's no reason not to try that next. This leaves our choice of $n$. Intuitively it's clear that this one should be 1 as well: after failing to get a candy from the machine once, it's either Bad or Mixed with probability 1/2, while both other machines are Good with probability 1/2, so those machines definitely appear more appealing. But let's make this formal.
The strategy $n = k = 1$ nets you an expected value of $5/3$ tries until you obtain a candy. Now suppose that $n geq 2$. Write $X$ for the number of tries, and $B, M, G$ for the event that the first machine you try is the Bad, Mixed, Good one. Then:
$$
begin{align*}
mathbb{E}(X) &= underbrace{mathbb{E}(X mid B)}_{geq n + 1}mathbb P(B) + underbrace{mathbb{E}(X mid M)}_{> 1}mathbb P(M) + underbrace{mathbb{E}(X mid G)}_{=1}mathbb P(G)\
&>(n+1)frac13+ 1times frac13 + 1 times frac13\
& geq frac53.
end{align*}
$$
Here the "strictly greater than" on line 2 stems from the fact that the expected number of tries when the first machine is Mixed is actually strictly greater than 1. Thus $n = k = 1$ is optimal.
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
edited Jan 18 at 11:04
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
answered Jan 18 at 10:38
Mees de VriesMees de Vries
17.3k12957
17.3k12957
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
add a comment |
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
$begingroup$
I don't see why $E(X | M)P(M)$ evaluates to $1 times frac{1}{3}$, for $n geq 2$. Obviously, $P(M)= frac{1}{3}$, but when you are dealing with $M$, $X$ can assume any value $i$ such that $1 leq i leq n$, each with probability $(frac{1}{2})^i$.
$endgroup$
– dkalocinski
Jan 18 at 11:00
1
1
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
Note that there is a $>$ sign in between. $mathbb E(X mid M) > 1$, and $mathbb P(M) = frac13$.
$endgroup$
– Mees de Vries
Jan 18 at 11:01
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
@elelel, I've changed the formatting a bit for more clarity.
$endgroup$
– Mees de Vries
Jan 18 at 11:08
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
$begingroup$
Got it. Thanks, @Mees de Vries. I like your solution, because it's short compared to mine.
$endgroup$
– dkalocinski
Jan 18 at 11:11
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%2f3076954%2fcandy-machines-and-optimal-strategy-in-terms-of-expected-value%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
