# Colored egg carriage problem

Bob has lots of painted eggs to $50$ different colors. He wants to carry one egg of each color from point $A$ to $B$. The probability that he breaks an egg is $P$ (same for all colors). I want to formulate cost of carrying all $50$ eggs for two different conditions:

1. If there is any broken egg when he reaches point $B$, he goes back to point $A$ and tries to bring eggs of the same color he broke (only broken eggs will be brought and he can take one egg of each color).
2. If there is any broken egg when he reaches point $B$, he goes back to point $A$ and tries to bring all eggs from scratch (all $50$ eggs will be brought again).

Going from point $A$ to $B$ count as $1$ cost. Going back to from $B$ to $A$ does not count.

-
What is $x$ in $P(x)$? Can Bob carry at most $50$ eggs at the same time? –  Karolis Juodelė Dec 27 '13 at 21:36
Yes, capability is 50. I have written $P(x)$ as a constant, you can take it 1/50 for example. –  Ricardo Cristian Ramirez Dec 27 '13 at 21:39
Are you only allowed to take one egg at a time or can you just take all remaining needed eggs with you? –  Ragnar Dec 27 '13 at 22:42
$P(x)$ has no meaning unless you specify what $x$ is. Also, you didn't specify what exactly he does under the first condition. Common sense would imply that if Bob breaks just one red egg on the first trip, he would bring 50 red eggs on the second trip. –  user21820 Dec 28 '13 at 2:33
@Ragnar We can take up to 50 eggs at a time. So that all remaining eggs can be taken. –  Ricardo Cristian Ramirez Dec 28 '13 at 14:25

[Edit: The question has been clarified. I'll leave my original interpretation and answer because it is beneficial as stepping stone to the new question.]

Let $n$ be the number of eggs and $p$ be the probability that each egg breaks, independently of other eggs.

[My original interpretation of the second condition: All eggs are discarded at B if at least one is broken, and he goes back to A and restarts the whole procedure.]

Let $x$ be the expected number of trips and find an equation for $x$ by considering the expected number of trips after one trip. There are two cases corresponding to whether no eggs break or at least one egg breaks. I'm sure you can compute the probability $q$ that the first case occurs, in terms of $n$ and $p$. In that case we need to restart the whole procedure and so the expected number of trips from that point is $x$. In the other case we are done and the expected number of trips from that point is $0$. So we get $x = 1 + q \cdot x + (1-q) \cdot 0$ and then we can find $x$.

[The new question: Unbroken eggs are kept at B and he stops if he has at least 1 unbroken egg of each colour at B.]

Note that the two conditions are equivalent because bringing a egg of a colour that he already has (unbroken) at B makes no difference. Let $f(k)$ be the expected number of trips where $k$ eggs need to be brought. Clearly $f(0)=0$. For each $k>0$, there are now $k+1$ cases corresponding to how many eggs break on the first trip, and you can compute the probability that each case occurs, which gives as before a linear equation involving $f(k)$ and $\{ f(m) : 0 \le m \le k \}$ with coefficients depending on $p$ and $n$, which is $f(k) = 1 + \sum_{m=0}^k P(m\text{ eggs broke}) f(m)$. You can now see that you can find $f(k)$ for any $k$ from $1$ to $n$.

-

Let $p$ the probability that an egg breaks on one journey from A to B and let $n=50$ be the number of different colors.
For case $2$, the probability that no egg breaks is $P=(1-p)^n$. The probability of succeeding the first time is $P$. The probability of succeeding the second time is $(1-P)P$, because the first time failed and the second time succeeded. For the $i$'th trip, it is $(1-P)^{i-1}P$. For the expected number of trips, we get $$\sum_{i=1}^\infty i(1-P)^{i-1}P=\frac 1P$$ (This can be calculated using the formula for the sum of geometric series.) The expected costs is $\frac 1p=(1-p)^{-n}$.

For case $1$, you can use a Markov-chain with $n+1$ states ($0$ to $n$ eggs left). You calculate the probability for each number of eggs breaking and then solve it with some matrix multiplications etc. (but I can't tell you how exactly, see Markov Chains)

-

The chance that $n$ eggs break on one trip is ${50 \choose n}P^n(1-P)^{50-n}$ In case $1$ if $P$ is reasonably small, he won't break very many. He can then bring lots of the needed colors on the second trip and be done with high probability. In case $2$, the chance of a successful trip is $(1-P)*{50}$ If you fail, you haven't made progress, so the expected number of tries is the inverse of this.

-

I'm slightly better at providing simulation results rather than analytical results. As such, I've created algorithms for solving both cases, using Maxima, which is an open-source Computer Algebra System that is usually used by those working with math (although, for the purpose of this simulation, I would have preferred to use a more efficient language).

For the 1st case, my algorithm follows:

n_iter: 1000;

p: float(0.05);
n: 50;
ride_var: 0;

for i:1 step 1 thru n_iter do
(
n_deliv: 0,
ride: 0,
while n_deliv < n do
(
fix_n_deliv: n_deliv,
for egg:1 step 1 thru (n - fix_n_deliv) do
(
if (random(1.0) > p) then n_deliv: n_deliv + 1
),
ride: ride + 1
),
ride_var: ride_var + ride
);
disp(float(ride_var/n_iter));

-----

n_iter   - number of iterations
p        - probability of one egg breaking
n        - number of eggs carried from A to B
ride_var - cumulative number of rides taken
n_deliv  - number of eggs delivered
ride     - number of rides


I've run an algorithm similar to this, varying the probability from 0 to 0.90, in 0.05 intervals. These are my results.

As you can see, the results start at 1, as expected. They progress slowly until $p$ passes around $0.6$. As the probability of breaking one egg nears $1$, the number of trips you need to take nears infinity.

For the 2nd case, my algorithm follows:

n_iter:  1000;
esc_max: 500;

p: float(1/50);
n: 50;
ride_var: 0;

for i:1 step 1 thru n_iter do
(
n_deliv: 0,
ride: 0,
for esc:1 step 1 while (n_deliv < n and esc <= esc_max) do
(
fix_n_deliv: n_deliv,
for egg:1 step 1 thru (n - fix_n_deliv) do
(
if (random(1.0) > p) then n_deliv: n_deliv + 1 else (n_deliv:0, egg:n)
),
ride: ride + 1
),
ride_var: ride_var + ride
);
disp(float(ride_var/n_iter));

-----

esc_max - escape condition, in order to prevent infinite runs.


Due to the computational requirements, I was only able to calculate the first 6 terms.

The last 3 values may have been capped by the escape condition I added. This goes to show the very high rate of growth of the number of travels in this case.

The 2nd case can clearly be seen as the worse of the two. As in the 1st case all eggs that arrived safely were deposited somewhere where they wouldn't break, in this case, success only depends on whether you actually break a single egg. As the probability of breaking an egg is independent, the probability of delivering all eggs doesn't change in trips, as opposed to the 1st case, where, having at least delivered some of the eggs in a step, the probability of delivering all eggs increases over steps.

The color of the eggs has no matter, because the probability of breaking one is independent, and there exists an infinite amount of eggs to work with.

The expected cost can be obtained simply by multiplying the unitary cost of a trip from $A$ to $B$ with the results obtained here.

-

Let's divide this by steps. Let step 1 be the travel between point $A$ and point $B$.

You have $P(x)$ as a chance to break one single egg on arrival to $B$. As the probability is equal for all other eggs, and assuming the events are independent, the probability of $n$ eggs breaking is given by $P(x)^n$.

This being said, one can calculate the chance all eggs arrive safely to the other side.

$$P = 1 - \sum_{i=1}^{n} P(x)^n$$

The cost for the 1st step is therefore given by the following:

$$Cost = P \times C$$

Where $C$ is the cost of the travel. However, this doesn't account the fact that you have to get back and get any egg that broke. To get the total cost one would have to consider all hypothesis iteratively. Assuming that no egg broke on the way back, we would have a repetition of the thought process in the first step. The cost for the 2nd step would be the following.

$$Cost = P \times C + (1-P)(P \times 2C)$$

Note the $2C$, as you had to travel two times.

For the 3rd step:

$$Cost = P \times C + (1-P)(P \times 2C) + (1-P)(1-P)(P \times 3C)$$

The full series (and as such, the full cost) is the following:

$$Cost = \sum_{i=1}^{n \rightarrow \infty} iPC (1-P)^{i-1}$$

The answer is valid for both situations, as replacing one or every egg has no cost or effect on probability, the only thing that matters are the rides from $A$ to $B$.

-
I've been thinking about this concrete problem and I feel the need to warn the above formulas aren't 100% accurate. –  Doktoro Reichard Dec 28 '13 at 2:13
The chance of $n$ breaking is ${50\choose n}p(x)^n(1-P(x))^{50-n}$. The chance they all arrive intact is $(1-P(x))^{50}$ –  Ross Millikan Dec 28 '13 at 14:43