[EM] Impartial culture with truncation? (Kristofer Munsterhjelm)

[Kristofer Munsterhjelm]

Kathy Dopp wrote:
> On Fri, Jul 16, 2010 at 7:39 AM, Kristofer Munsterhjelm

>> Therefore, my program needs some form of sampling. As impartial culture
>> seems to do reasonably well in the full-rank case, yet I cannot test
>> criteria that may need truncated ballots for a disproof, I was wondering how
>> to generalize it.
> 
> 
> Could you give each of the more than 120^30 (e.g.) possible unique
> voter-ballot combinations equal probability of sampling and choose
> that way?  

I think that's what happens with impartial culture, since that sampling 
has equal probability for each possible ballot. If we consider giving 
each possible assignment of ballots to 30 voters a distinct number, so 
that we could "look them up" by simply drawing a number between 0 and 
120^30 out of a hat, then the probability that the first voter votes, 
say, A>B>C is equal to the probability that it votes B>C>A (1/120). 
Therefore, drawing permutations, where each permutation is equally 
likely, 30 times, should give the same result as picking a random number 
between 0 and 120^30 and translating that into a ballot group. The 
advantage of doing it in the former way is, of course, that you don't 
need to have 256-bit integers to do it nor memory to store every 
possible combination.

> Or could you simply sample each possible unique
> voter-ballot combination one at a time and keep a simple array of
> success or failure at meeting the criterion so as not to run up
> against computer limitations?

If I could devise a bijection between the integer range [0..120^30> and 
all possible ballot groups, then that could work; all I would have to do 
would be to make a 208-bit cipher, then encrypt 0, 1, etc, up, and 
reject all numbers greater than 120^30. This would work because of the 
pigeonhole principle: say the encryption algorithm maps 0 to 6. Then it 
can't map any other integer to 6 because then it would be impossible to 
decrypt "6" again. There would be no need to keep an array, just an 
index number meaning "passed criterion for all below this number" - once 
one finds a failure, that's the disproof and there's no reason to search 
further.

However, this would still require very large integers and so would be 
slow -- and I would have to build the 208-bit cipher and the bijective 
function. A method of drawing a truncated permutation with equal 
probability for each would be better.

> Is the computer limitation, the time it takes to run the program or
> the memory space?  I would be inclined to simply chug away at all the
> possible combinations because if you randomly select some, you may
> miss the criterion failures since you do not know how many criterion
> failures there may be out of the total you would not know how large
> the sample size has to be to hit them.

If you're talking about exhaustive search - trying every single one - 
then the problem is speed. Say I can generate and test a billion ballot 
groups a second. To test all 120^30 I would then have to work for... 
7.5*10^45 years. The cipher solution would shuffle the ballot groups 
around enough to make sampling work, but it wouldn't be exhaustive.

For similar reasons, simply storing all 120^30 explicitly and shuffling 
the indices around would be impossible - there wouldn't be enough memory 
to go around, nor time to even finish the shuffling pass.