News for hackers. Stuff that matters.
Re:Realtime Bitcoin webGL globe – visualizing all transactio... by kaoD on Friday January 31, 2014 @02:38PM (#7158700)
What do you mean? If blocks are 10min apart (actually less as the network hashrate grows before the difficulty adjustment) and the last block was found 3 minutes ago, a new block is expected to be found after 7 more minutes.
Re:Realtime Bitcoin webGL globe – visualizing all transactio... by bbosh on Friday January 31, 2014 @02:58PM (#7158830)
Each hash is essentially an observation of a uniformly distributed variable (hopefully). When you flip a coin, it's heads with probability 1/2 and tails with probability 1/2. The fact that you flipped heads on the first go doesn't change the probabilities. In the same way, the fact that your hash didn't match the difficult on the first go, doesn't change the probability it will match the difficulty on future hashes. So each hash is independent of the attempts you've already made, so there's the same probability of a match at any time step.
Re:Realtime Bitcoin webGL globe – visualizing all transactio... by kaoD on Friday January 31, 2014 @05:40PM (#7159663)
That's technically right (yep, I know gambler's fallacy too), but it doesn't address my comment.

Testing a block header is just a binary (yes/no) test with a given probability (target/max_target). Finding a block is repeating this test again and again, i.e. a binomial distribution, right?

Finding a block averages 10 minutes, which means that, after 10 minutes trying hashes randomly, the expectation of finding a block is high, i.e. the CDF of the binomial distribution approaches 1.

The result will deviate from the expected result? Of course! After all, it's a distribution... but this doesn't contradict the fact that as you try again a again, the probability of AT LEAST ONE hitting the target gets higher.

So, yes, it doesn't change the individual probability of each outcome, but it sure does mean that more hashes have been tried, i.e. there's a greater probability of a hash being found simply because we've tried more guesses as time passes, i.e. we're measuring the CDF with a high N.

To put it another way: the more coins you flip, the higher the expectation of AT LEAST ONE yielding tails (even if the previous attempts don't change the outcome probability).

Think about it: even if each coin outcome is always 1/2, we're not assessing whether it's going to be tails or not in flip N, but whether after N flips we'll see at least one flipping tails, whose probability is (1 - (1/2)^N).

Flipping a coin 7 times yields a 99% probability of flipping tails (or heads) at least once, regardless of previous outcomes.

And I'll stop here, I think I'm repeating myself :P

Re:Realtime Bitcoin webGL globe – visualizing all transactio... by bbosh on Friday January 31, 2014 @06:14PM (#7159821)
I'm sorry, but this isn't correct. Firstly, you need to understand what Binomial is describing. It is not describing the time between outcomes. It is describing the number of times you will observe a positive result amongst n independent Bernoulli trials (Yes/No trials). By the "CDF approaches 1", what you are saying is that P(X <= n) = 1. But, we know that to be true by assumption -- we can't possibly observe more than n positive results from n trials. The continuous-time analogue would be the Poisson process -- this counts the number of valid blocks that have been generated up to a time t. The inter-arrival time -- the time between valid blocks -- is a random variable with an Exponential distribution. This is the distribution we are really looking at. And Exponential is memoryless (see Wikipedia for a proof).
Re:Realtime Bitcoin webGL globe – visualizing all transactio... by kaoD on Friday January 31, 2014 @06:19PM (#7159844)
Don't be sorry, I love learning and correcting my mistakes! But I'm going to fight :P

Of course it does not describe time. It describes attempts (which grow with time because you're doing N attempts per second, i.e. the network hashrate). My point still stands.

I see your point, but I think we're unknowingly discussing a semantic issue: the expected time is not the time when you're expected to find a block, it is the time where the probability of at least one block being found is high (including the previous attempts). It's only gambler's fallacy if you're discarding the previous attempts and only measuring the probability of hitting a block in a single attempt, which of course is constant throughout all attempts.

> The inter-arrival time -- the time between valid blocks -- is a random variable with an Exponential distribution.

Sure, but if you pick 10 minutes, you'll be right more often than not (not counting hashrate changes, of course) because it averages 10 minutes...

One block is found in 1 minute and the next in 19? No problem. That's why it says "expected" and not "sure".

----

How many times do you have to flip a coin to have a 99% confidence of flipping tails at least once? Seven. You might need less than seven (the first attempt is already 50%) or more than seven (because 99% != 100% and we never reach 100%) but 99 out of 100 times you flip 7 coins you'll hit tails at least once.

I think that's what the "expected" means. You expect to flip tails within 7 flips (because I've arbitrarily set the bar at 99%) so we might be arguing what "expected" means.

Re:Realtime Bitcoin webGL globe – visualizing all transactio... by gus_massa on Friday January 31, 2014 @08:11PM (#7160373)
Suppose you flip a coin and get 4 heads in a row. How many additional times do you have to flip the coin to have a 99% confidence of flipping tails at least once?

If you flip it only 3 additional times you get only a 7/8=88% probability of getting at least one tail.

You need to flip it 7 additional times you get 127/128=99.2% probability of getting at least one tail.

The coin doesn’t remember that the last 4 times it landed head.

Re:Realtime Bitcoin webGL globe – visualizing all transactio... by askmike on Friday January 31, 2014 @02:49PM (#7158777)
The 10 minutes is only an average time at which the network can solve the problem with random tries. You won't see a lot of blocks 10 minutes apart because only when measured over longer timeframes it averages to 10 minutes.

Just like when you flip 10 coins they likely won't result in: head - tail - head - tail - (...). Though on average you end up with 5 tails and 5 heads.

Re:Realtime Bitcoin webGL globe – visualizing all transactio... by kaoD on Friday January 31, 2014 @05:42PM (#7159669)
> You won't see a lot of blocks 10 minutes apart because only when measured over longer timeframes it averages to 10 minutes.

That's why it says expected! To be 100% correct you could plot the cumulative density function as time progresses, but I think just printing the expected time is fine.