Topic: "How to hop" has moved - page 6. (Read 16256 times)

I'm confused here.  I think the number of snake eyes in N throws follows a binomial distribution and the number of throws to result in one snake eye follows a geometric distribution.  Both of these distributions are built on the underlying base of independent identically distributed Bernoulli trials.  The Poisson distribution provides an approximation for the binomial distribution when n is large and p is small (and hence is an excellent choice in practice for handling bitcoin mining).


Ok.  I only brought it up because the assumption of many games in the past and future was not made in the question and did affect the answer.


I think you are wiser than I.


You're welcome.  I was briefly interested in spending some time (a full day) looking at all the reward systems mathematically, perhaps inventing one or two of my own in the process.  I discovered however that a decent body of work on this subject already exists.

Good luck with your competition!

So reading your posts in with that in mind, I found your analysis of the game start and finish boundary problems interesting. I still have more thinking to do though. It takes a while. Mills grinding slowly but exceedingly fine etc. Well, fine-ish, anyway.


Point taken. The 'time' between snake eyes being rolled is the number of throws, not the time taken for the throws, and the number of throws to end a game is a series of Bernoulli trials. Pooled bitcoin mining would approximate a Poisson process better. But the number of snake eyes in N throws still follows a Poisson distribution. The number of throws to result in one snake eye follows a binomial distribution. I understand you realise that but I wanted to spell it out for other readers.

Yes, from what I understand atm, you couldn't show the start/finish boundary problem without summing that way. I was assuming, as you say, as many games in the past and the future as necessary to make the start and finish of a series of games irrelevant and tbh hadn't I considered the problem at all.

Well, no, but the conversation might interest people enough to do their own reading. I find that unless very well crafted, intuitive explanations can lead readers astray since the writer has to assume *some* level of knowledge on the part of the reader. If you assume to too little knowledge the reader gets bored and assume too much knowledge and the reader makes incorrect intuitive leaps. I can't find that happy medium so I try to make the math as simple as possible to follow.

Well, that was great! Thanks for persevering teukon. I'm sure I wasn't the only one to find that interesting.

Comp ends in only 3 days. Any other entrants?

Ok.  Most of my original post was about what happens at the beginning and end of a "series of games".  The confusion has come from my saying "game" for your "series of games" and "round" for your "game".  Certainly there is no funny business going on shortly before or after snake-eyes.


Good point, I have not been reading these posts in full detail but just trying to get a feeling for the mathematical approach taken.  Your approach really is fine if you are talking about the binomial distribution but calling this a Poisson process is technically an error.  This is a discrete process, not a continuous one.  My apologies for not reading your post thoroughly.


Ah, we're just talking about different random variables.  The expected total payout for a throw is certainly p*B.  You're right, I made an error here.

Of course, E(X_0) is 1/n*(p*B) and hence

When focusing on how the binomial distribution is a sum of Bernoulli ones it's very easy to write "E(X_i) = p" without thinking.


The sum is, in my opinion, an important part of this problem.  Without it my solution would read:

Assuming there have been at least 9 previous throws and will be at least 9 future throws, the expected value of a throw is
Because it costs $1 to play the expected profit from any turn is exactly $0 and hence there is no winning strategy (possibly unless we allow ourselves throws close to the beginning or end of a series of games).

The interesting bit is in seeing why the expected value of a throw is $1.  If someone cannot see that it really is $1 then I doubt using words like "binomial" and "distribution" won't help.  Instead, I think the simplest reasoning is to consider how much you expect to get from each of the next 10 throws (including your own).  In each case you would be one of 10 people sharing an expected 1/100 * $100 = $1 reward so your expected income from the throw is $0.10.  Summing the expected incomes of all 10 of these throws yields the expected return of $1.

Just a bit more about your post, since you put a lot of thought into it:


I actually didn't use the binomial distribution in the post - I only mentioned that the number of snake eyes found in N throws follows a Poisson distribution.



So I calculate the expected value as p*B not n*p as you have. So either we have different meaning of expected value or one of us is wrong there! I'm ok with being wrong if you can show me why.


It's unnecessary to sum the series since the expected value for a throw in the game, p*B, consists of unchanging constants.

It's late for me here so I might not have followed you properly, so I'm looking forward to your reply.

Throws in any previous game are rewarded if the current game is short, ie less than 10 throws. The game ends when the dice come up snake eyes, as per my understanding of iopq's post on his game (is that correct iopq?)

So if you threw snake eyes on the first throw of a game, you'd get $10, and the last nine throwers of the previous game get $10 each. Then a new game starts. In the real world, with 24 hour casinos and no end of gamblers, I think we can assume that starting a series of games and ending a series of games would be a rare occurrence.

I hope that clears it up!

It's only unfair to expect it if I'm making the reward contingent on his response. I'm not. The offer holds, and any other entries are still welcome.

All I'm doing is promoting discussion. I'm not requiring a response or a change in the entry. I apologise if I gave that impression.
Well, I'm glad you followed iopq's work too! There's a lot of interesting points there. And from your post I guess his proof is satisfactory for you? Fair enough! But I'm still not making any decisions about the competition until the deadline, midnight 19-10-2011 UTC.

I think it's unfair to expect more than this when the question was


It seems that people have found a winning strategy and provided sufficient justification to show that it is winning.  They may not have found the best winning strategy or justified that their strategy is the best but this is not what is asked for.  You do say the winning strategy but only at one point and you never ask for the best strategy.  I would say the 1 BTC has been earnt.

The 4 BTC on the other hand would certainly require some elegant mathematical reasoning.

I think you missed my point.

Firstly, I don't question your logic on the use of the Binomial distribution.  I omitted talking about it because it is not needed to reason out the expected value of a throw (I'm trying to keep things simple).  I will now expand on my thoughts and use standard mathematical notation but I still prefer my original form.

Suppose a player takes a turn and throws the dice.  Suppose also that there have been at least 9 past and at least 9 future throws.  We want to calculate the expected amount that the player will receive.

Let X_i be the expected amount the player receives from the i-th throw (where i=0 is the player's throw and i=1..9 are the 9 future throws).

We want to calculate E(X_0 + X_1 + ... + X_9).  (Where E is the expectation operator).

The X_i's are independent identically distributed Bernoulli random variables with parameter p = 1/100 (probability of success).

There are two main ways to calculate this expected value.  The first is to consider X = X_0 + ... X_9 as a random variable in it's own right.  This will be a binomial random variable (just as you describe) and you can use the known formula for the expected value of such a random variable (number of trials * probability of success; n*p).

The other way is to note that the expectation operator is linear so
E(X_0 + ... + X_9) = E(X_0) + E(X_1) + ... + E(X_9) = n*E(X_0) = n*p
Indeed, this is the main way in which the formula for the expected value of a binomial distribution is derived.  The beauty of taking the second method here is that it the expected value of a Bernoulli random variable is intuitive so formulae can be largely avoided.  I find it difficulty to express myself properly on a forum but I feel this is the elegant way to reason about this game.

The majority of my post was discussing the assumptions needed to make the mathematics rigorous.  If you make an assumption that this game extends infinitely in both directions then everything is fine but most people will assume that the game starts at some point and ends at some point.

What happens, for example, if we actually start playing this game and I get snake eyes on my first throw?  Would I recieve $100 or would I recieve only $10 (the other $90 theoretically given out to the previous 9 players).  In the latter case there is no problem but in the former case the first 10 throws give the player a positive expected profit.  Instead of being 10 * 1/10 * $1 the expected value would be (1 + 1/2 + 1/3 + ... + 1/9 + 1/10) * $1.

What happens when a game ends?  If I make the last throw of the game then surely $1 is too much to pay for only a 1/100 shot at receiving $10.

A real PPLNS pool has to start at some point and must end at some point too.  A naive PPLNS pool will screw up here, giving out high value to the initial miners and constantly borrowing from the future until, when the pool closes, the people holding the last N shares lose out.  This is a trapezoid scheme.  A carefully implemented PPLNS pool would try to avoid this, probably by creating a pool kitty which is funded by the initial miners and pays out to the final miners.  A PPLNS pool has other factors to worry about, such as changing N and changing difficulty.  Just as with starting and ending a pool, these changes need to be handled gracefully to make sure that the expected value of each share is correct.

iopq (and any other interested contestants): You are still calculating the reward for a player since the beginning of the game. The problem with that is although it provides information about how much a player can be expected to earn, it doesn't provide you with enough information to pinpoint a strategy. All you can do is calculate and observe trends. If you calculate the expected value of a throw, then whenever it is above 1.0 you should throw, and whenever it is below, you should not.

Calculating the expected profit as you have done will always result in a profit greater than the cost even by a tiny margin since it can only equal the cost if there are an infinite number of throws so that the reward for the game minus the cost of the game equals zero.

What I think you mean your calculations to tell us is that earlier throws are rewarded more than later throws. But you don't show us when a particular throw is worth less than the mean value of a throw, which (since you define profit as winnings minus cost) would be less than zero. This is what you need in order to determine the best strategy.

Early on, when I couldn't figure out how to simulate expected values of shares (which ended up being quite easy, simulating winnings since the start of a round was harder) I generated similar data, showing expected profit per round and then comparing that to a different expected profit per round (see HTH1). Have a look at how hard it is to figur out a strategy that way, and then look at HTH2 where there are graphs of expected values of a particular share, and it's much easier to see what the correct strategy for that 'game' is.

Hint 4: HTH7 has full instructions on how to do this.

teukon, I just thought of an even simpler example: If the payout was paid only to the person who threw the snake eyes  - is there a winning strategy?

This is the same as the case of paying the last ten throws, with N=1 instead of 10. Only the variance changes.

teukon, I'm not clear on what you're saying here. In the real world, the chances you mention can be calculated. See if the following makes sense to you, or show me where I'm wrong.

To find out if on average you will profit or not, for this type of payout system you have to find how many 'snake-eyes' are expected in the next 10 throws. If there is 0, your throw is worth nothing. If there are 1, your throw is worth $10, 2 snake eyes you get $20 up to $100 if there are 10 snake eyes in the next 10 throws.

We can assess this more generally. The frequency of snake-eyes occurring is a Poisson process, so the number snake-eyes occurring before before a number of throws follows the Poisson distribution. Define p = probability of success, B = the reward, N= the number of throws rewarded and L = number of snake-eyes expected after N throws, and we know there is no fee at this casino.

To get the expected value of an event, we need to calculate the probability of the event and the reward for that event. In this case, if a throw is rewarded once, it will always be the same: the reward/number of throws rewarded:
To find out how probable multiple rewards are we need to determine L. Since L follows the Poisson distribution, its mean is the expected number of snake-eyes during N throws:
The expected value of the throw:

So the expected value of a throw is invariant: there is no strategy which will gain you more since B and p never change.

In the posted game's case, the expected value of any throw is $100* 1/100 = $1.

Please note that this is not anything original. I've adapted chapter 3.3 of Analysis of Bitcoin pooled mining reward systems to the dice game. If I've made a mistake in my analysis of the game or its reward system it is mine, not Meni's.

thousand players scenario
one toss strategy:

toss 1 profit: 100*1/(1+999) - 10/1000 = 0.09
toss i(=n+1) profit: 100*1(1+999i) - 1/100= 100*1(1+999+999n) - 1/100
EV = 0.009 + Sum[(9/10)^n((10*1/(1+999+999n)) - 1/1000),{n, 1, Infinity}] ~= 0.0156

two toss:
toss 1 profit: 100*1/(1+999) - 10/1000 = 0.09
toss 2 profit: 100*2/(2+2*999) - 20/1000 = 0.08
EV = 0.009 + 0.008*0.9 + Sum[(9/10)^n((10*2/(2+999+999n)) - 2/1000),{n, 2, Infinity}] ~= 0.0222

hundred players scenario
toss 1 profit: 100*1/(1+99) - 10/100 = 0.9
toss i(=n+1) profit: 100*1(1+99i) - 1/100= 100*1(1+99+99n) - 1/100
EV = 0.09 + Sum[(9/10)^n((10*1/(1+99+99n)) - 1/100),{n, 1, Infinity}] ~= 0.157

toss 1 profit: 100*1/(1+99) - 10/100 = 0.9
toss 2 profit: 100*2/(2+2*99) - 20/100 = 0.8
EV = 0.09 + 0.08*0.9 + Sum[(9/10)^n((10*2/(2+99+99n)) - 2/100),{n, 2, Infinity}] ~= 0.223

ten players scenario
toss 1 profit: 100*1/(1+9) - 10/10 = 9
toss i(=n+1) profit: 100*1(1+9i) - 1/10= 100*1(1+9+9n) - 1/10
EV = 0.9 + Sum[(9/10)^n((10*1/(1+9+9n)) - 1/10),{n, 1, Infinity}] ~= 1.68

toss 1 profit: 100*1/(1+9) - 10/10 = 9
toss 2 profit: 100*2/(2+2*9) - 20/10 = 8
EV = 0.9 + 0.8*0.9 + Sum[(9/10)^n((10*2/(2+9+9n)) - 2/10),{n, 2, Infinity}] ~= 2.36

I can see that a share is worth different amounts even when scaled to what it costs
the ratios for each number of players is not the same

in fact, the solution for larger number of players is five tosses and for a lower number of players is four tosses
for five thousand players:

four toss
0.0018 + 0.0016*0.9 + 0.0014*0.9*0.9 + 0.0012*0.9*0.9*0.9 + Sum[(9/10)^n((10*4/(4+4999+4999n)) - 4/5000),{n, 4, Infinity}] = 0.00524994
five toss
0.0018 + 0.0016*0.9 + 0.0014*0.9*0.9 + 0.0012*0.9*0.9*0.9 + 0.0010*0.9*0.9*0.9*0.9 + Sum[(9/10)^n((10*5/(5+4999+4999n)) - 5/5000),{n, 5, Infinity}] = 0.00525006

so for a sufficiently large number of players you need to toss 5 times

Not quite - you showed that the EV for a particular player's throw depends on the number of players, not the expected value of the actual throw.

I certainly appreciate your tenacity!

But try finding the expected value of a throw. Go to HTH7 and look at how I derive the expected value for a share, not for the hopper.

that's not true, I've shown that the EV for each throw depends on the number of players in the game due to the fact that more players participating doesn't increase the chance of a payout, but generates shares

so the monetary value is inherently linked to the amount of players participating in each throw
it gets especially cheap to participate in a throw when a lot of players participate

example:
when a lot of players participate in throw 5 because it's a lucky number or whatever, it can be profitable to participate in it yourself, since the amount of money you pay to participate is now less due to the money splitting thing, but you still get a full share despite paying less dollars

ten thousand players scenario
one toss strategy:

toss 1 profit: 100*1/(1+9999) - 10/10000 = 0.009
toss i(=n+1) profit: 100*1(1+9999i) - 1/1000= 100*1(1+9999+9999n) - 1/1000
EV = 0.0009 + Sum[(9/10)^n((10*1/(1+9999+9999n)) - 1/10000),{n, 1, Infinity}] ~= 0.00156

two toss:
toss 1 profit: 100*1/(1+9999) - 10/10000 = 0.009
toss 2 profit: 100*2/(2+2*9999) - 20/10000 = 0.008
EV = 0.0009 + 0.0008*0.9 + Sum[(9/10)^n((10*2/(2+9999+9999n)) - 2/10000),{n, 2, Infinity}] ~= 0.00222

three toss
toss 1 profit: 100*1/(1+9999) - 10/10000 = 0.009
toss 2 profit: 100*2/(2+2*9999) - 20/10000 = 0.008
toss 3 profit: 100*3/(3+3*9999) - 30/10000 = 0.007
EV = 0.0009 + 0.0008*0.9 + 0.0007*0.9*0.9 + Sum[(9/10)^n((10*3/(3+9999+9999n)) - 3/10000),{n, 3, Infinity}] ~= 0.00252

four toss
toss 1 profit: 100*1/(1+9999) - 10/10000 = 0.009
toss 2 profit: 100*2/(2+2*9999) - 20/10000 = 0.008
toss 3 profit: 100*3/(3+3*9999) - 30/10000 = 0.007
toss 4 profit: 100*4/(4+4*9999) - 40/10000 = 0.006
EV = 0.0009 + 0.0008*0.9 + 0.0007*0.9*0.9 + 0.0006*0.9*0.9*0.9 + Sum[(9/10)^n((10*4/(4+9999+9999n)) - 4/10000),{n, 4, Infinity}] ~=0.00262

five toss
toss 1 profit: 100*1/(1+9999) - 10/10000 = 0.009
toss 2 profit: 100*2/(2+2*9999) - 20/10000 = 0.008
toss 3 profit: 100*3/(3+3*9999) - 30/10000 = 0.007
toss 4 profit: 100*4/(4+4*9999) - 40/10000 = 0.006
toss 5 profit: 100*5/(5+5*9999) - 50/10000 = 0.005
EV = 0.0009 + 0.0008*0.9 + 0.0007*0.9*0.9 + 0.0006*0.9*0.9*0.9 + 0.0005*0.9*0.9*0.9*0.9 + Sum[(9/10)^n((10*5/(5+9999+9999n)) - 5/10000),{n, 5, Infinity}] ~= 0.00262

first throw is 156% efficiency, second throw is 166% efficiency, third throw is 130% efficiency, fourth throw is 110% efficiency, the fifth throw being a wash
we're really reaching the limits of Wolfram Alpha here, though, the result it gave me is that fifth throw is slightly higher EV in the next few digits, but I can't be sure if that's right or not since it's not giving the exact formula, but only an estimation due to the huge amount of computation we're doing

I mean, I don't get how we got the second throw as more efficient than the first, it could be all calculation errors
I'll try with a thousand players later

I wrote: not
See the difference? Ignore the players, they are irrelevant to the game itself.

Sorry I don't have time to respond properly just now. I did want to let everyone know that How to hop 7: Expected values is posted.

No hints today, since 'How To hop 7' has lots of hintyness inside. I hope to be able to respond to you all tonight.

Cheers!

I don't think that's possible

consider this:

you throw 4 times when there are 4 players in the game
after 4 throws a group of friends come back from lunch and now there's 10 people in the game for throws 5 and up (you stop playing if you win before 4 throws and leave)

EV = 2.25 + 1.8 + 1.4175 + 1.0935 + Sum[(9/10)^n((10*4/(4+9+9n)) - 4/4),{n, 4, Infinity}] ~= 2.76

suddenly, your EV more than halved because the amount of players in the later rounds doubled

Assuming that there were at least 9 past throws and will be at least 9 future throws, a throw gives the player an expected return of exactly $1.  This is because a throw has a total payout expected value of $100/100 = $1 and a player will receive 1/10 of the payout for their throw and 1/10 of the payout for each of the 9 future throws.  If there are fewer than 9 past throws then you receive a large proportion of the payout for your throw so on average you will profit.  If there will be fewer than 9 future turns then you clearly lose on average.

Consequently, in most real world cases, the winning strategy is to make as many of the first 10 throws as possible and then leave (unless there is a real chance that there will be fewer than 20 throws in total).

For miners this means joining new PPLNS pools that you think have implemented the reward system in this naive way and leaving after the first N shares have been found (again, banking that the pool will receive at least 2N shares).  Hopefully new PPLNS pools will not be so basic.