The number of trimming rounds estimation

Research
1

Hello,

I’ve red the article “Cuckoo Cycle: a memory bound graph-theoretic proof-of-work” but haven’t understand sentence:“The number of trimming rounds, which can be set with option -n, defaults to 1+(B+3)*(B+4)=2, which was determined empirically to achieve a load close to 50%.”

I think that it’s possible to estimate number of trimming rounds to achieve a (some) load using binomial distribution. And it should be more precious than empirically data.

Or may be I don’t understand something?

3 Likes
2

Apparently someone has proven the following Cuckoo Cycle Conjecture:

which allows us to compute exactly how many rounds are needed to reduce the number of remaining edges to any desired fraction.

4 Likes
3

Oh, thx a lot. I should learn it…

2 Likes
4

I think that before your article you need to read thishttps://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BA%D1%83%D0%BA%D1%83%D1%88%D0%BA%D0%B8,
there is a foundation, and then you already have the analysis.

1 Like
5

Yes. I’ve make a mistake.

Of course it’s possible use binomial distribution but just for the first trimming step. So the calculation gives us good estimation 63%. But a lot off different kind of graphs can lead to the same graph after the first step. These are dependent probability events.

Thx for attention