Here is a problem arising (via a tortuous path) from trying to determine the spectrum of Vershik's adic map on Pascal's triangle (a moderately well-known question: is the spectrum trivial, that is, is the map weakly mixing?).
Let $N$ be a large integer. Set $A \equiv A(N)$ to be the set of $0-1$ sequences of length $2N$ (so $|A| = 4^N$), and let $S$ be a subset of $\{ 2, 4, 6, \dots, 2N\}$, say with size $t \sqrt N$ (roughly) for some $t > 0$. I am interested in the likelihood that an element of $A$ has an initial segment with an equal number of zeros and ones, that initial segment terminating in a point of $S$.
Let $\alpha (S)$ be the number of sequences in $A(N)$ such that at some point in $S$, $s$, the initial segment ending at $s$ has an equal the number of ones and zeros (obviously, $s$ has to be even, which is why $S$ consists of even integers). We say that the sequence in $A(N)$ is {\it balanced at $s$} when this occurs.
This can be re-expressed in terms of paths in Pascal's triangle: a path in Pascal's triangle, starting at the apex, is balanced at $s$ if it hits the central point at level (row) $s$.
I have a couple of questions associated with this.
1 Is it true that the sequence $S$ consisting of the terminal $t\sqrt N$ portion of $\{2,4,6, \dots, 2N\}$ yields the minimum value of $\alpha(S)$, or close to the minimum (say, at most double the actual minimum), over all subsets of its cardinality?
2 If we fix $t = 1$, for example, is it true that there exists a constant $c$ (independent of $N$) such that $\alpha (S) \geq c 4^N$? That is, if $|S|$ is the floor of $\sqrt N$, the probability of having such an initial segment is at least $c$.
Concerning the set $S $ consisting of the last $\sqrt N$ elements of $\{2,4,6, \dots, 2N\}$, it is not difficult to show there is a constant (rather small, although I did not try to estimate it) $c$ such that $\alpha(S)\geq c 4^N$ for all $N$. This can be obtained directly from the formulas for Dyck-like paths (e.g., instead of beginning and ending at zero, starting and finishing at other points).
At the other extreme, if $S$ is sufficiently spaced out (e.g., space between consecutive integers in $S$ is around $t^{-1}\sqrt N$), then again a $c$ (that is, independent of $N$---but it will of course depend on $t$) comes out, although it is difficult to estimate, and the method only seems to work if $t < 1/\sqrt \pi$. This can be done with inclusion-exclusion.
The first conjecture is plausible. It is easy to see that if we shift $S$ to the right as far as possible (that is, so its largest member is $2N$), then we obtain a smaller $\alpha(S)$ (or at worst, equal), and this also works for shifting any terminal subset of $S$ to the right, fixing the rest.
The interpretation as paths on Pascal's triangle suggests that this type of problem might have been considered before. But I'm not familiar with the literature. Any ideas?
It may be that $\sqrt N$ is too close to the borderline: the likelihood that a $0-1$ sequence will be balanced at $s$ is ${s\choose {s/2}}/2^s \sim 1/\sqrt {\pi s/2}$ (when $s$ is modestly large), so if hitting different points were independent (they aren't, of course, although there is a relatively simple relationship), we would get $c \geq 1-e^{-1/\sqrt \pi}$ or something like that (for $t= 1$). So it may be necessary to assume something like $|S| \sim N^{1/2 + \epsilon}$, in order that such a $c$ exist.
