wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Expected length of repeating random sequences
        
(Message started by: towr on May 12^th, 2013, 12:12pm)

Title: Expected length of repeating random sequences
Post by towr on May 12^th, 2013, 12:12pm

What's the expected number of coins you'd need to toss to get a sequence that repeats itself? (i.e. first half equal to the second half)

And, in general, how about for dice with k sides? (Assuming it isn't already infinite for 2.)

Title: Re: Expected length of repeating random sequences
Post by pex on May 13^th, 2013, 3:07am

on 05/12/13 at 12:12:15, towr wrote:

What's the expected number of coins you'd need to toss to get a sequence that repeats itself? (i.e. first half equal to the second half)

Seems like the number of such sequences of length 2n is A216958 (http://oeis.org/A216958)(n); at least, it matches as far as I bothered to check (up to n=7) and it deals with a similar problem. No closed form, nor even a recurrence, for A216958(n) seems to be known, so looking for sum [ (2n) A216958(n) / 2²ⁿ ] might be kind of hard.

My hunch is that it's actually infinite, based on how easy it is to mess up the property you're looking for.

Edit: The number of sequences of length n that do not yet include such a repetition is A122536 (http://oeis.org/A122536)(n). Not much help though, as the listed recurrence depends on A216958.

Title: Re: Expected length of repeating random sequences
Post by rmsgrey on May 13^th, 2013, 6:59am

There are 2ⁿ binary sequences of length 2n where the first and second halves are identical, so, if you don't stop just because you've already met the condition, the probability of meeting the condition at length 2n is 2^-n.

The expected number of times a random sequence will match the condition is a familiar sum:
1/2 + 1/4 + ... = 1

That's an upper bound on the probability a sequence of length 2n meets the condition at least once - some sequences will meet the condition more than once (all heads and all tails each meet it n times) and the probability of meeting the condition at length 6 is not independent of the probability of meeting it at length 4, so I'm out of shortcuts...
The corresponding lower bound on the expected length of sequence is 4 (n=2)

With a three-sided die, the expected number of hits in a given sequence is:
1/3+1/9+1/27+... -> 1/2 which I think gives us lower bound on the expected length of sequence of infinity, but it's been too long since I last used the relevant maths, so I could be wrong

Title: Re: Expected length of repeating random sequences
Post by dudiobugtron on Oct 16^th, 2014, 11:44pm

I assume 0 and 1 aren't acceptable answers? ;)

Title: Re: Expected length of repeating random sequences
Post by rmsgrey on Oct 17^th, 2014, 4:55am

on 10/16/14 at 23:44:18, dudiobugtron wrote:

I assume 0 and 1 aren't acceptable answers? ;)

0 is probably acceptable, but uninteresting. For 1, it raises the question of what half a head looks like...

Title: Re: Expected length of repeating random sequences
Post by dudiobugtron on Oct 17^th, 2014, 12:36pm

on 10/17/14 at 04:55:49, rmsgrey wrote:

0 is probably acceptable, but uninteresting.

I think it's pretty interesting (http://en.wikipedia.org/wiki/Interesting_number_paradox)! :P

Quote:

For 1, it raises the question of what half a head looks like...

Indeed, I was considering only the mathematical sequence, and not the actual physical coin.