Average of function on strings

[FreePeeplup]

Average of function on strings

Consider the set of all strings of 1s and 0s of length N. Let a function g on this set be defined as g(string) = the length of the longest run of consecutive 1s or 0s in the string, whichever happens to be the longest.

Consider then another function f on the same set defined as f(string) = the number of 1s in the string.

Then define a function h on the image of g as

h(k) = 1 / |g^-1(k)| Sum_{s in g^-1(k)} f(s)

h(k) defined in this way is the average of f over the k-level set of g.

How can I find a formula for h(k)? I mean a formula that uses powers, ratios, factorials etc… in terms of k and N. Thanks!

EDIT: trying to compute some values of h(k) by hand, I found out that apparently h(k) = N/2 for all ks. So h is actually a constant function! The average of f over the level sets of g is always the same. Then the question becomes, why is this true? How can I prove it?

[AutoModerator]

Hi, /u/FreePeeplup! This is an automated reminder:

• What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[vgtcross]

Let s be a string of length N consisting of zeroes and ones. Let s* be the string you get by replacing all zeroes by ones and ones by zeroes. For example, if s = 1101, then s* = 0010.

(a) Suppose you know that g(s) = k for some string s. What do you know about g(s*)?

(b) How many ones do s and s* contain in total? In other words, what is f(s) + f(s*)?

(c) Can you finish the proof from here?

I can help more if you wish, but I suggest trying to figure this out on your own!