9

First of all, I'm sorry if I'll use some game related terms, but that's where the question that bugged me for the last week came from.

Let's say, we have a mana pool of size $M$, and we can cast a spell that costs $n$, with $n < M$. The spell has a probability $p$ to give us $kM$ mana, where both $p$ and $k$ are fixed constants in the interval $[0,1]$.

What is the probability to get mana starved, that means, to end up without enough mana to cast any more instances of our spell after $t$ casts?

edit : as a first ( and simpler ) case, we can assume $M = qn$ with $q \in N , q > 1$ and $kM = pn , p < q$ .

kaharas
  • 1,034
  • Shall we assume that this does not take into account regeneration per time unit? – bryan.blackbee Mar 11 '13 at 14:54
  • Yes, I wanted to keep things "simple", so I ignored the mana regeneration ... and since usually that is a small amount compared to N,this shouldn't introduce too much bias – kaharas Mar 11 '13 at 14:58
  • This is similar to the idea of 'first return' in random walks. – polkjh Mar 11 '13 at 15:28
  • Does "a mana pool of size $M$" mean that you can never have more than $M$ mana, or just that you initally have $M$ mana? And are any of these quantities restricted to integers? – joriki Mar 11 '13 at 15:38
  • $M$ is both the maximum mana you can have, and his starting value. I guess, for simplicity, we could assume both $M$ and $n$ as integers; for a starting case, we could also assume that $M = qn$ with $q$ integer greater than 1 – kaharas Mar 11 '13 at 15:39

2 Answers2

1

You get starved after $q$ casts if you have had at most $w$ successes and $(q+1)n \gt M+wkM$. The probability of $w$ or less successes is $\sum_{j=0}^w {q \choose j}p^j(1-p)^{(w-j)}$. This does not guarantee you haven't already starved.

Ross Millikan
  • 374,822
1

I can give a partial answer for the case $M,n,kM\in\mathbb{N}$. In this case, you can model your situation as a discrete Markov-chain on $\{0,\dots,M\}$. The $M+1\times M+1$ transition matrix $P$ is described by

$$P_{ij}=\cases{1 &\text{ if $i=j<n$}\\ 1-p &\text{ if $i\geq n, j=i-n$}\\ p & \text{if $i\geq , j=i+kM$}\\ p & \text{if $\geq (1-k)M, j=M$}\\0&\text{ otherwise.}}$$

As an example, for $n=1, kM=2, M=4$ this looks like

$$P = \left(\matrix{1&0&0&0&0\\1-p&0&0&p&0\\0&1-p&0&0&p\\0&0&1-p&0&p\\0&0&0&1-p&p}\right)$$

The probability $q$ you are interested in is

$$q = \sum_{i=0}^{n-1}P^{t}_{Mi}$$

I don't see a nice short form for this expression, but it can surely be evaluated by a CAS.

Jens
  • 1,293