A few days ago, I was doing some statistical research for Betafreak Minecraft to find a good way to allow items to have only one byte for a health bar, yet still allow for more than 256 uses. Using my statistics skills, I came up with the solution below: the Multi-Geometric Distribution.

Basically, the multi-geometric distribution (as I call it) applies to a random variable whose value is the number of attempts requried to attain m successes, when the probability of success is p. In other words, you perform a chance event with odds of success p (e.g. flipping a coin has p at .5) and increment x every time, and you stop once you have m successes. If you keep doing that many times and graphed all your x's in a histogram (bar graph) or stem-and-leaf plot, that would be the multi-geometric distribution for x.

Using my trusty TI 84 PSE and a few test scenarios (such as flipping a coin until you get 3 heads and rolling a die until you get 2 6's), I was able to determine the following formulas (given a particular m and p):

► Probability of x being a: P(x=a) = (x-1 nCr x-m)*(1-p)^(x-m)*p^m
► Expected (mean) value: μ=m/p
Standard deviation from the mean : σ = sqrt(m(1-p)/p^2)

Rearranging the formulas, we can determine m and p from a given μ and σ (if you were too lazy to click the link, x lies within 2σ of the mean about 95% of the time):
m = μp
p = μ / (σ^2 + μ)

How is this useful? In the calculator programming world, it is actually quite useful. As I detailed above, you might want to save memory on a health bar, but want more than the possible range of values offered by said health bar. You could also use this for an intermittent speed - randomly determine whether to move or not every time you try.

Edit by Merth: Fixed the list.
Your explanation is not very clear, but I think you just "invented" the binomial distribution.
Compynerd255 wrote:
How is this useful? In the calculator programming world, it is actually quite useful. As I detailed above, you might want to save memory on a health bar, but want more than the possible range of values offered by said health bar.
How does this do that?
Tari wrote:
Your explanation is not very clear, but I think you just "invented" the binomial distribution.


Very close, but I think what Compy discovered is actually the negative binomial distribution.
That is some pretty complex math.
Runer112 wrote:
Tari wrote:
Your explanation is not very clear, but I think you just "invented" the binomial distribution.


Very close, but I think what Compy discovered is actually the negative binomial distribution.

Thanks, Runer, I didn't know it was called that. I discovered it using different terms, and I still called it the "multi-geometric" distribution because I realized that you could also derive these formulas by adding the results of m geometric distributions (add their μ's and σ's).

merthsoft wrote:
Compynerd255 wrote:

How is this useful? In the calculator programming world, it is actually quite useful. As I detailed above, you might want to save memory on a health bar, but want more than the possible range of values offered by said health bar.

How does this do that?


Use code similar to the following (this is generalized C-style code):

Code:

class HPBar
{
   byte value;
   byte type;
}

void initialize(HPBar bar, int type)
{
   bar.value = initialMValues[type]; // lookup initial value of M
   bar.type = type;
}

void attemptDecrease(HPBar bar, int value)
{
   int i = 0;
   while (i < value && bar.value > 0)
   {
      if (Math.random() > PValues[bar.type]) // compare random number to corresponding value of P
      bar.value--;
      i++; //EDIT: I didn't remember to increment i
   }
}

// Use this in drawing the bar
int returnBarLength(HPBar bar, int maxLength)
{
   return bar.value * maxLength / initialMValues[bar.type];
}


Also, as an example, the Minecraft Wiki claims that the bow can be used 385 times - which is greater than a byte allows. I don't really want to use two bytes of storage to keep track of the durability, so I use this distribution instead. I'm willing to have a deviation of up to 50 shots 95% percent of the time, so I apply the distribution:
1) μ = 385, σ = 25
2) p = μ / (σ + μ) = 385 / (25 + 385) = .381
3) m = μ * p = 385 * .381 = 147
So, when I create a bow, its corresponding M value is 147, and its corresponding P value is .381.
Compynerd255 wrote:
A few days ago, I was doing some statistical research for Betafreak Minecraft to find a good way to allow items to have only one byte for a health bar, yet still allow for more than 256 uses. Using my statistics skills, I came up with the solution below: the Multi-Geometric Distribution.


This part is pretty misleading. An 8 bit byte has 256 possible values. That means that you can uniquely identify 256 different states of the health. Any scheme that allows you to get more than 256 states out of an 8 bit byte violates information theory. From what you posted, it appears that you effectively select a random number and the bar has a possibility of simply not decreasing if that number meets certain criteria.
Qwerty.55 wrote:
Compynerd255 wrote:
A few days ago, I was doing some statistical research for Betafreak Minecraft to find a good way to allow items to have only one byte for a health bar, yet still allow for more than 256 uses. Using my statistics skills, I came up with the solution below: the Multi-Geometric Distribution.


This part is pretty misleading. An 8 bit byte has 256 possible values. That means that you can uniquely identify 256 different states of the health. Any scheme that allows you to get more than 256 states out of an 8 bit byte violates information theory. From what you posted, it appears that you effectively select a random number and the bar has a possibility of simply not decreasing if that number meets certain criteria.

Yes, that is correct. Basically, I wanted to go between two extremes: using memory to have a constant health (or time) interval, and rolling a random number each repetition to determine breakage (which is unacceptable because it's totally possible that the item will break after only 1 use). This solution allows you to control the spread of the distribution.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement