3
$\begingroup$

Lets say i have a set of 100 trials i want to test, each one has a probability of success of T / 100, where T = trial number (so first trial is 1 / 100, second trial is 2 / 100). Also everytime a trial succeed, our trial number starts back to 1, but in total we still do 100 trials. Now the question is, what is number of successes i should expect after 100 trials?

To give a better idea, i'm trying to do a point system, where everytime you do something you gain 1 point, and you repeat this for 100 times. Each time you do that "something" if a random generated number, 1 to 100, is lower or equal to the points you have, you have a success, so the points you have go to 0, otherwise you go on increasing points. So again what i want to know is the formula to calculate how many times i'm expected to have a success with this system.

The "100 times/trial", and the probability increasing by 1% are just an example, as i said in the comments i actually have an old system that i want to somewhat reproduce with this new system.

$\endgroup$
6
  • $\begingroup$ I'm assuming that your randomly generated number is uniformly distributed? $\endgroup$ Commented Apr 8, 2014 at 11:20
  • $\begingroup$ Yes it is, forgot to add it :) $\endgroup$
    – Smjert
    Commented Apr 8, 2014 at 12:19
  • $\begingroup$ Well, I'm not able to provide a closed-form expression for you, but using some monte carlo trials, I came up with an expected number of successes to be roughly 6.6. After 1000 trials, the fewest I found were 4, and the most were 10. $\endgroup$ Commented Apr 8, 2014 at 12:36
  • $\begingroup$ Thank you, though i think i will edit a bit the question because i'm trying to find the formula to calculate this, because the 100 trials are just an example, i actually want to be able to "balance" it. Basicly i have an old system that test a fixed probability, in the end i have that after 66 trials i'll have a success. Now i want to somewhat reproduce this probability with the new system $\endgroup$
    – Smjert
    Commented Apr 8, 2014 at 12:49
  • $\begingroup$ I see that maybe it's kind of complicated to have a closed-form expression, well meanwhile i'll try with monte carlo. $\endgroup$
    – Smjert
    Commented Apr 8, 2014 at 13:00

1 Answer 1

2
$\begingroup$

Let $N=100$. The number of steps since the last success occurred performs a Markov chain on $\{1,2,\ldots,N\}$ where each transition $k\to1$ has probability $k/N$ and each transition $k\to k+1$ has probability $1-k/N$. Successes are visits to the state $1$.

By the classical one-step analysis, the stationary measure $(\pi_k)$ of this Markov chain solves the system $$\pi_{k+1}=(1-k/N)\pi_k\ (1\leqslant k\lt N),\qquad\pi_1=\sum\limits_{k=1}^N(k/N)\pi_k.$$ Thus, $$ \pi_1=\frac{N^N}{N!}\,\left(\sum_{k=0}^{N-1}\frac{N^k}{k!}\right)^{-1}. $$ Using Stirling's formula to estimate the prefactor and the central limit theorem to estimate the parenthesis, one sees that, when $N\to\infty$, $$ \pi_1\sim\sqrt{\frac2{\pi N}}, $$ hence, for $N$ fixed, when $T\to\infty$, the number of visits to the state $1$ up to time $T$ is approximately $$ \sqrt{\frac2{\pi N}}\,T. $$ Assuming that $N$ is large enough to be considered as a large number of steps for the Markov chain on $\{1,2,\ldots,N\}$ (a rather dubious hypothesis), the mean number of visits of state $1$ (aka, the mean number of successes) would scale as $$ \sqrt{\frac{2N}\pi}, $$ which, for $N=100$, is about $7.98$.

$\endgroup$
2
  • $\begingroup$ Well have to say that till now this seems to be "the solution". When i did some test with the code i've written i've found results around that number, and using that formula with other N seems to work. Though if i understood correctly, never did Markov chains :P, this requires that the various probabilities of the trials increase linearly, while if it's random it "won't work", right?. Meaning.. i do the thing that makes me gain 1 point, but i also can do another thing that can make me gain 0.5 points, i no particular order. $\endgroup$
    – Smjert
    Commented Apr 8, 2014 at 15:36
  • $\begingroup$ The transition probabilities appear in the linear system solved by the stationary distribution $\pi$. If one specifies different transition probabilities, the linear system is modified but not the method of resolution of the problem. $\endgroup$
    – Did
    Commented Apr 8, 2014 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .