Author |
Topic: Expected length of repeating random sequences (Read 3828 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Expected length of repeating random sequences
« on: May 12th, 2013, 12:12pm » |
 Quote  Modify
|
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.)
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Expected length of repeating random sequences
« Reply #1 on: May 13th, 2013, 3:07am » |
Quote Modify
|
on May 12th, 2013, 12:12pm, 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(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) / 22n ] 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(n). Not much help though, as the listed recurrence depends on A216958.
|
| « Last Edit: May 13th, 2013, 3:35am by pex » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Expected length of repeating random sequences
« Reply #2 on: May 13th, 2013, 6:59am » |
Quote Modify
|
There are 2n 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
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Expected length of repeating random sequences
« Reply #3 on: Oct 16th, 2014, 11:44pm » |
Quote Modify
|
I assume 0 and 1 aren't acceptable answers? 
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Expected length of repeating random sequences
« Reply #4 on: Oct 17th, 2014, 4:55am » |
Quote Modify
|
on Oct 16th, 2014, 11:44pm, 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...
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Expected length of repeating random sequences
« Reply #5 on: Oct 17th, 2014, 12:36pm » |
Quote Modify
|
on Oct 17th, 2014, 4:55am, rmsgrey wrote:| 0 is probably acceptable, but uninteresting. |
|
I think it's pretty interesting! 
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print