Hacker News Reader

Comment by bbosh | Hacker News Reader

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.

View on HN

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

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

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.

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.

Reply on news.ycombinator.com