0

I'm having a hard time trying to figure out a formula or pattern for averages when iterations are involved. For example:

Let's say you have four apples, and you want an equal chance for any apple to be picked, but they can only be picked or discarded from right to left. One apple MUST be picked by the end of the iteration.

My first thought was to say Apple 1 has a 25% (1 in 4) chance of being picked, so 75% of the time, it's discarded. If A1 is discarded, Apple 2 would then have a 33.3% chance of being picked, and a 66.7% chance of being discarded. If A2 is discarded, Apple 3 has a 50% chance of being picked, and a 50% chance of being discarded. Since the rule is that an apple must be chosen, Apple 4 has a 100% chance of being picked if Apple 3 is discarded.

I feel like the weight of Apple 4 being chosen isn't right, though I can't say if it's higher or lower than Apple 4 being chosen. Perhaps my above scenario is the correct distribution of chance, but it doesn't quite feel right.

Jesse Williams
  • 105

1 Answers1

1

I see nothing wrong with the answer you give. Just to explain where it comes from...

Let $p_i$ denote the probability that the $i^{th}$ apple is selected, conditioned on none of it's predecessors being selected. We want to find the $p_i$.

Clearly $p_1=\frac 14$.

The probability that the second apple is chosen must also be $\frac 14$, hence $$\frac 14= (1-p_1)p_2=\frac 34p_2\implies p_2=\frac 13$$

The probability that the third apple is chosen must also be $\frac 14$, hence $$\frac 14= (1-p_1)(1-p_2)p_3=\frac 34\times \frac 23\times p_3\implies p_3=\frac 12$$

And, of course, we must have $p_4=1 (as it is required that the process select an apple).

To comclude we remark that $$\frac 14=(1-\frac 14)(1-\frac 23)(1-\frac 12)\times 1$$ as desired.

lulu
  • 70,402
  • I did some further testing (in computer code) and it does seem to be right. When I was trying to do it on paper it seemed skewed, but the general distribution seems pretty even. Thank you! – Jesse Williams Nov 23 '16 at 02:04