bb
Member
Offline
Activity: 84
Merit: 10


August 09, 2011, 08:20:54 PM 

I should really know this myself, but I can't wrap my head around it.
The probability of a share finding a block is 1/difficulty, right? (So that on average there are 'diff' shares per block.)
Now, what probability distribution does this lead to? (It can't be pure Gauss...) Poisson?
And furthermore, if I want to do some simulations, how do I generate random "total shares" so that they follow such a distribution?
Thanks!








Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.





Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2058
Merit: 1029


August 09, 2011, 09:07:03 PM 

Distribution of what? The total number of shares in a round follows the geometric distribution (the discrete version of the exponential distribution), with mean equal to the difficulty. The number of blocks found among a given number of shares, follows the binomial distribution, or to an extremely good approximation, the Poisson distribution with mean (number of shares / difficulty). And furthermore, if I want to do some simulations, how do I generate random "total shares" so that they follow such a distribution?
Take a number uniformly distributed in [0,1]. Take the negative of the natural logarithm of it. Multiply by the mean. This gives you an exponentially distributed variable. Round up, this will give you approximately a geometric distributed one.




bb
Member
Offline
Activity: 84
Merit: 10


August 14, 2011, 09:46:08 PM 

Thanks a lot for clearing this up. I have since used this to do a(nother) pool hopping simulation.




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2058
Merit: 1029


August 15, 2011, 07:33:58 AM Last edit: August 15, 2011, 07:51:29 AM by Meni Rosenfeld 

The motivation of your post  the fact that fallback is not necessary with many proportional pools  is not new. I've said this already here (Table B.1) and before that. The reason it's unnecessary because when there are many pools, you never get to 43.5%  there will virtually always be a pool with less than that. So you don't need any of the "random threshold selection from the range [0.5, 1.5]" nonsense.




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2058
Merit: 1029


August 15, 2011, 08:04:57 AM 

I won't post in the bitHopper thread because it's too busy, so with your permission I'll reply here to a comment there: I assume you are giving each pool a table of random block find times (randomly generate a highprecision round percentile 0% to 100%, turn that percentile into number of individual hashes required using correct math, turn that into times using hashrate), and then are simulating the switching and share percentages earned.
No. I am using Meni's formula. You can't use anything that will provide a uniform random distribution. It has to be at least a binomially distributed random, and at best a timedistributed fractional poisson distribution. I'm using the built in poisson distribution randomiser built into R with some jiggery pokery to make it a poisson timedistributed random(really share based) instead of the standard poisson distribution http://stat.ethz.ch/Rmanual/Rpatched/library/stats/html/Poisson.html. Ryouiki has a bespoke poisson randomiser built on mersenne twister as a random seeder. So there's a bunch of examples to get you going! I don't know where you heard the term "poisson timedistributed random", but you should use standard terminology: A process of independent random events happening at a given rate is called a Poisson process. The distribution of the number of events in a given time interval in a Poisson process is called the Poisson distribution. The distribution of the time between any point and the next event in a Poisson process is called the Exponential distribution. The discrete version of the exponential distribution, which gives the number of shares in a round, is called the Geometric distribution. Now, the procedure I outline is the correct way to obtain an exponentially distributed random variable (the active ingredient is taking a logarithm). I don't know how bb did his simulation so can't comment whether this is what he needs.




bb
Member
Offline
Activity: 84
Merit: 10


August 15, 2011, 01:28:27 PM 

The motivation of your post  the fact that fallback is not necessary with many proportional pools  is not new. I've said this already here (Table B.1) and before that. The reason it's unnecessary because when there are many pools, you never get to 43.5%  there will virtually always be a pool with less than that. So you don't need any of the "random threshold selection from the range [0.5, 1.5]" nonsense. I had only seen organofcorti's simulation and had not seen your (unfinished) paper before. I knew there was a mathematical derivation. I am just better at programming than at probability theory. In my simulation too, there is little to no time spent at the backup pool when hopping multiple pools. For six pools however I found that there is still some time spent at pools being at > 0.43 ( see this post).




organofcorti
Donator
Legendary
Offline
Activity: 2058
Merit: 1007
Poor impulse control.


August 15, 2011, 03:08:12 PM 

I won't post in the bitHopper thread because it's too busy, so with your permission I'll reply here to a comment there: I assume you are giving each pool a table of random block find times (randomly generate a highprecision round percentile 0% to 100%, turn that percentile into number of individual hashes required using correct math, turn that into times using hashrate), and then are simulating the switching and share percentages earned.
No. I am using Meni's formula. You can't use anything that will provide a uniform random distribution. It has to be at least a binomially distributed random, and at best a timedistributed fractional poisson distribution. I'm using the built in poisson distribution randomiser built into R with some jiggery pokery to make it a poisson timedistributed random(really share based) instead of the standard poisson distribution http://stat.ethz.ch/Rmanual/Rpatched/library/stats/html/Poisson.html. Ryouiki has a bespoke poisson randomiser built on mersenne twister as a random seeder. So there's a bunch of examples to get you going! I don't know where you heard the term "poisson timedistributed random", but you should use standard terminology: A process of independent random events happening at a given rate is called a Poisson process. The distribution of the number of events in a given time interval in a Poisson process is called the Poisson distribution. The distribution of the time between any point and the next event in a Poisson process is called the Exponential distribution. The discrete version of the exponential distribution, which gives the number of shares in a round, is called the Geometric distribution. Now, the procedure I outline is the correct way to obtain an exponentially distributed random variable (the active ingredient is taking a logarithm). I don't know how bb did his simulation so can't comment whether this is what he needs. I was referring to deepceleron's post, not bb's, and addressing bb not deepceleron. I know what he and you did was correct and the procedure to create a random number that will be distributed according to the poisson process is well known. i apologise for the confusion.




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2058
Merit: 1029


August 15, 2011, 04:36:07 PM 

I was referring to deepceleron's post, not bb's, and addressing bb not deepceleron. I know what he and you did was correct and the procedure to create a random number that will be distributed according to the poisson process is well known. i apologise for the confusion.
That makes some sense, except that if you read deepceleron's post you'll see it's correct too and is basically the same as what I wrote. You draw the percentile uniformly in [0,1], and translate it to a value using the inverse of the cumulative distribution function (log in our case).




organofcorti
Donator
Legendary
Offline
Activity: 2058
Merit: 1007
Poor impulse control.


August 15, 2011, 09:32:18 PM 

To make it clear, I was responding to bb's quote of his post: I assume you are giving each pool a table of random block find times (randomly generate a highprecision round percentile 0% to 100%, turn that percentile into number of individual hashes required using correct math, turn that into times using hashrate), and then are simulating the switching and share percentages earned.
in which deepceleron does not make any mention of the type of random number distribution he or she thought would be used.




