MHB Average steps required to terminate a game.

  • Thread starter Thread starter bincy
  • Start date Start date
  • Tags Tags
    Average Game
AI Thread Summary
The discussion centers on calculating the average number of steps required to terminate a game involving the removal of balls from a box, where the removal proportions vary with each step. It highlights that while the average proportions of balls removed (a_i) can be known, they do not provide sufficient information to predict the average stopping time (x) due to the variability in removal paths. Counterexamples illustrate that two scenarios can yield the same average removal proportions but result in different average stopping times, demonstrating the complexity of the problem. The conclusion asserts that, in general, there is no formula to compute the average stopping time based solely on the average removal proportions for cases with two or more balls. Specific cases may allow for inference, but a general solution remains elusive.
bincy
Messages
38
Reaction score
0
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
 
Physics news on Phys.org
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).
 
Hi,
springfan25 said:
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
 
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.
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top