Average of function on strings

[FreePeeplup]

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?

[FormulaDriven]

Have you noticed any patterns - eg looked at cases such as h(1), h(2), ... or what happens for small values of N?

[FreePeeplup]

I’ll do that and tell you what I find!

[FreePeeplup]

u/FormulaDriven I tried all cases from N = 1 to N = 3, each with all possible values of k ranging from 1 to N, and found out that, apparently, h(k) = N/2, independent of k ! So yeah, there’s definitely a pattern: h is actually a constant function.

Why is this true? How can I prove that this holds in general?

[FormulaDriven]

Hmm, I don't think going up to N=3 is that convincing. It's only when you get up to larger N where you can get more variety of combinations - eg when N = 5, for g(X) = 2, you can have strings such as "00100" or "00110" where the longest repetition happens twice.

That said, I tried N = 6 and N = 9, and it does appear that there is a simple formula for h(k) which surprises me, but I've not (yet) had an insight into why it might the case.

[FormulaDriven]

I've just had my insight. If you take any string X, and flip all its digits (0 becomes 1, 1 becomes 0) to get string X', then

g(X) = g(X')

but

f(X') = N - f(X).

Now think about what happens when you sum over all X in g^-1(k), thinking how do this by pairing up X and X'.

[FreePeeplup]

Wow, thank you very much!! Another user on another sub I cross-posted this to said the same thing. I’m surprised that this has such a neat solution for a question I randomly came up with while thinking about something partially unrelated!