Bitcoin Forum
April 27, 2018, 07:48:25 AM
 News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Pool share probability simulation  (Read 1620 times)
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.
bb
Member

Offline

Activity: 84
Merit: 10

 August 09, 2011, 08:59:02 PM

Just a followup: if the probability distribution were Poission, shouldn't there be a very small variance with the huge number of shares?

See e.g.: http://www.wolframalpha.com/input/?i=poisson%281800%29
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 2044
Merit: 1000

 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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
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: 2044
Merit: 1000

 August 15, 2011, 07:33:58 AM

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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 2044
Merit: 1000

 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 high-precision 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 time-distributed fractional poisson distribution.

I'm using the built in poisson distribution randomiser built into R with some jiggery pokery to make it a poisson time-distributed random(really share based) instead of the standard poisson distribution http://stat.ethz.ch/R-manual/R-patched/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 time-distributed 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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
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: 1000

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 high-precision 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 time-distributed fractional poisson distribution.

I'm using the built in poisson distribution randomiser built into R with some jiggery pokery to make it a poisson time-distributed random(really share based) instead of the standard poisson distribution http://stat.ethz.ch/R-manual/R-patched/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 time-distributed 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.

Bitcoin network and pool analysis 12QxPHEuxDrs7mCyGSx1iVSozTwtquDB3r
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 2044
Merit: 1000

 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).

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
organofcorti
Donator
Legendary

Offline

Activity: 2058
Merit: 1000

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 high-precision 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.

Bitcoin network and pool analysis 12QxPHEuxDrs7mCyGSx1iVSozTwtquDB3r