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.

 

[blue_raver22]

Dear Bincy,

Thank you for sharing your interesting problem with me. I would approach this problem by first understanding the underlying distributions and their behavior. In this case, we know that the distributions are independent but not identical, and we only have information about their averages. This means that we cannot make any assumptions about the specific distributions, but we can still analyze the average behavior of the process.

To find the average steps required to terminate the game, we can use the concept of expected value. The expected value of a random variable is the average outcome that we would expect if we repeated the process many times. In this case, the random variable is the number of steps required to terminate the game.

To calculate the expected value, we can use the formula E[X] = ∑ xP(x), where X is the random variable, x is the possible outcomes, and P(x) is the probability of each outcome. In this case, the possible outcomes are the number of steps, and the probability of each outcome can be calculated using the given information about the average fraction of balls removed in each step.

Using the given information, we can calculate the expected value as follows:

E[X] = (1/a1) + (1-a1)/a1 * (1/a2) + (1-a1)(1-a2)/a1a2 * (1/a3) + ... + (1-a1)(1-a2)...(1-an-1)/a1a2...an-1 * (1/an)

= ∑ (1-a1)(1-a2)...(1-ai-1)/a1a2...ai-1 * (1/ai)

= ∑ (1-∏ai)/∏ai

= ∑ (1-e^-1)(1-e^-2)...(1-e^-n)/∏e^-i

= ∑ (1-e^-n)/e^(1+2+...+n)

= ∑ (1-e^-n)/e^(n(n+1)/2)

= (∑ (1-e^-n))/e^(n(n+1)/2)

= (∑ e^-n - ∑ e^-n)/e^(n(n+1)/2)

= (1-e^-n)/e^(n(n+1)/2)

= 1/e^(n+1)/2

Therefore, the average steps required to terminate the