Average steps required to terminate a game.

[bincy]

Hii Everyone,

A a box contains $N$ balls. In each step, we remove some number of balls from the box according to some distribution, where the distributions are independent but not identical. We don't know any other details of the distributions but their averages. It means in the first step in an average $a_1$ fraction of balls are removed, In the second step $a_2$ of the remaining and in the third $a_3$ of the remaining balls in an average and so on...until the number of balls become zero. I have to find out the average steps required to terminate the process. Consider $a_{i}=e^{-(\frac{1}{i})}$regards,
Bincy

 

[springfan25]

You said that a is the proportion of balls removed at each step, so the game is over when $$a_i$$ = 1, and there is no way to predict that from the averages.The situation gets a bit more complicated if you round up the number of balls that can be removed, but i expect the outcome is the same (ie average game length cannot be predicted with the information in the question).

 

[bincy]

Hi,

You said that a is the proportion of balls removed at each step, so the game is over when $$a_i$$ = 1, and there is no way to predict that from the averages.

Eg. Say I have 10 balls. My $a_i=\frac{1}{2}$ irrespective of $i$, Then in the first take, i may take 5, second 2, 3rd 2, 4th 1. This is just a sample path. In an average i take 5 in 1st, 2( round it from $\frac{5}{2}$) in the second, 1( $\frac{3}{2}$ )in the third, 1( $\frac{2}{2}$ )in the forth, and 1 in the last(Please note that I will take atleast 1 ball at a time, Therefore w.p.1 last ball). Therefore average number of steps < 5.

In my question $a_i$ depend on step $i$. I think something can be inferred from the given information.
Thanks in advance,

regards,
Bincy

 

[springfan25]

Notation:
x = the realized stopping time
$$a_i$$ = the realized values of a.

$$\bar{x}$$ = the average stopping time (you want to compute this)
$$\bar{a_i}$$ = the average values of a (you know these)

I assume that the $$\bar{a_i}$$ are averages conditional on there being balls available to take at step i (ie, conditional on the game not having ended at previous turns). This proof is not valid without that assumption.

Proposition
For an N ball game It is possible to compute $$\bar{x}$$ from $$\bar{a_1} ...\bar{a_n}$$

Falisification
Disproof by counter example for the 2-ball case below.

Lets do 2 balls as it is easier. You always take at least 1 ball so $$a_2 = \bar{a_2}=1$$, and the stopping time can be expressed in terms of the realisation of $$a_1$$ alone.

Specifically, x=1 if $$a_1=1$$ and x=2 otherwise.

The examples below will show that two process can have the same $$\bar{a_1}=0.5$$ but different $$\bar{x}$$

Situation 1:
State1: $$a_1 = 1$$ with probability 0.5
State2: $$a_1 = 0$$ with probability 0.5

Clearly $$\bar{a_1}$$=0.5
$$\bar{a_2}=1$$ from the assumption in red at the top of this post.

The stopping time is 1 in state 1, and 2 in state 2. Each happens with probability 0.5 so we have $$\bar{x} = 1.5$$.

Situation 2
$$a_1 = 0.5$$ with probability 1
$$a_2 = 1$$ with probability 1

Clearly $$\bar{a_1}=0.5,\bar{a_2}=1$$ again.

There is only 1 possible sample path in this case ($$a_1=0.5,a_2=1$$) and the stopping time is 2.Conclusion
Situations 1&2 have the same observed information ($$\bar{a_1}=0.5, \bar{a_2}=1$$) and different average stopping times. Therefore it is not possible to compute $$\bar{x}$$ from $$\bar{a_i}$$. Since there is no formula for this specific case, there cannot be a general formula covering all cases where N=2.

By extention it there could be no formula for N=3 in all cases, since i can turn a 3 ball game into a two ball game by having :
$$a_1 = 1/3$$ w.p 1.
$$a_2$$ with the same distribution as $$a_1$$ from the 2 ball game
$$a_3$$ with the same distribution as $$a_2$$ from the 2 ball game

Analysis of the stopping time in situation 1&2 would proceed as before, except the stopping time (and average stopping time) would be 1 turn higher in each case.Finally, we can repeat that process for larger and larger games. So all comments in this thread are valid by induction for any N>2.

Remark
I have prooved that you cant, in general, do a computation for the average stopping time. However there may be specific cases when you can (no, I am not going to find them!)

Your second post asks if any inference can be made at all, which is a much weaker requirement which i won't try to prove either way.