Equipartition and Euler

[Colin Fiat]

Years ago I read somewhere in Ion's immense website about equipartition:

When drawing a randomly numbered ball and replacing it into the 'barrel', after drawing as
many balls as the highest numbered ball, roughly 60% of the balls will have been drawn.

That is to say, given a barrel of 50 numbered balls, drawing one ball and recording its
number before returning it to the barrel until 50 balls have been chosen, you will find, on
average, that 30 balls have been drawn and 20 have not.

Running millions of tests on large sets of random numbers yields an equipartition value of
1-(1/e) = 1-(1/2.71828) = 0.6321.

So what you may ask? Well for starters, it is the only constant I can think of related to
random numbers.

Secondly, a modification to the Euler value and the calculation method of equipartition
leads to an interesting failure in Zero Knowledge Proofs. A similar mechanism is also
known as Capture-recapture. Similar is Frequency Analysis or The German Tank Problem.

With zero knowledge proofs, you need to be assured that there are no unwanted items in
a large collection good items but you can only see a small sample at any time. So you
can view a small sample, record how many there are and mark each item. The second
round may contain items you have previously marked. Record the amount of new and
repeat items until repeat / new = 1/(e-1) = 0.581976. The total repeat+new= very close
to the total items.

What has this to do with lotteries? Almost anything you care to apply.

Take pick 3 games where 3 balls of 0 to 9 are drawn to produce a number from 000 to
999. These thousand possible combinations are perfect candidates. After 1000 draws
there will have been, on average, 582 of the possible combination drawn and 418 not
drawn.

My conjecture is that taking the last 418 drawn results as the 40% undrawn values and
the next 582 as being the 60% of repeat drawn values, 162 of the 40% previously drawn
numbers will be drawn again. Which ones is anyone's guess.

[LouisBachelier]

Hi Colin

I am always curious of new inputs; and you draw our attention on Zero knowledge proof issue.
I was not able to discover what you meant by the following:

..........................
Secondly, a modification to the Euler value and the calculation method of equipartition
leads to an interesting failure in Zero Knowledge Proofs. A similar mechanism is also
known as Capture-recapture. Similar is Frequency Analysis or The German Tank Problem.

.

Can you develop a bit over the modification of the Euler constant leading to an interesting failure in Zero knowledge proofs?

Thanks in advance

[Colin Fiat]

Hi Louis,

I had thought the paragraph beginning, “With zero knowledge proofs” was a little brief
but the focus was not on this. Let me try a simulated real world explanation.

Suppose in a two player game, each player has a secret number of uniquely numbered
game tokens. One player accuses the other of cheating due to stealing a token.
Perhaps they are red and blue for each respective player.

To verify that the accused has no stolen tokens without divulging the total number,
the tokens are randomly distributed into several hidden or covered piles. The other
player chooses one of the piles to examine and records the token numbers. Then the
tokens are randomly redistributed into several piles. It does not matter if some tokens
are not placed into a random pile for each random choice provided every token has a
chance at being selected at least once.

Each examination adds to the tally of total tokens viewed, the number of new and
the number of previously viewed tokens. After many randomizations and viewings,
there will come a time when the number of repeat viewed tokens divided by newly
viewed tokens equals 0.581976 or 1/(e-1). The total number of tokens viewed will be
very close to the total number of tokens the player has.

Here’s some pseudo code:

while repeat / nonrepeat < 0.6
  if random number not previously generated
    increment nonrepeat
  else
    increment repeat
  end if
  increment total
wend
guessed number is total

Javascript version: http://www.iinet.net.au/~htjs/temp/equipartiton.htm