Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine I have $(s_1, ..., s_N) \in S$ binary switches in a panel that can be switched between states $0$ and $1$. Initially, we flip all of the switches to the $0$ state.

Now, for each of $(t_1, ..., t_N) \in T$ time steps, I sequentially go to each switch, $s_i$, and with probability $p_{\text{on}}$, I flip the the switch to the $1$ state (i.e. I set $s_i = 1$), and with probability $p_{\text{off}}$, I flip the switch to the $0$ state (i.e. I set $s_i = 0$). With probability $(1-(p_{\text{on}}+p_{\text{off}}))$, or if the switch is already in the state I wish to switch it to, I do nothing. As such, we can expect that the number of time intervals a switch is in a particular state is governed by an exponentially distributed random variable where $\lambda = p_{\text{on}}$ for the $0$ state, and $\lambda = p_{\text{off}}$ for the $1$ state.

If we want to maximize the probability $P_k$ that the same arbitrarily selected set of $k$ light switches are on (and NO other light switches outside of this set are ON) for $j \leq ||T||$ time steps, what are optimal values for $p_{\text{on}}$ and $p_{\text{off}}$, recalling that $(p_{\text{on}}+p_{\text{off}}) \leq 1$? How well can I do? What is the spacing between events where a set of the same $k$ light switches are on for $j$ time intervals?

Update (no change to the actual question): What if we have fixed $p_{\text{on}}$ or fixed $p_{\text{off}}$, and we can only optimize $p_{\text{off}}$ or $p_{\text{on}}$, respectively?

share|cite|improve this question
How do you mean "only $k$"? If you mean "at most $k$", then the solution is trivially $p_{\text{off}}=1$, $p_{\text{on}}=0$. If you mean "exactly $k$", you should take out "only" (or perhaps replace it by "exactly"). – joriki Oct 13 '12 at 3:03
@joriki Good catch. I changed "only" to "exactly". – Afternoon Tea Oct 13 '12 at 3:07
You just changed the question the second I'd answered it. Please think more carefully about what you want to ask before asking others to spend time thinking about it. Let me know when you're sure the question says what you want it to say. – joriki Oct 13 '12 at 3:19
You seem to be using $T$ in two different meanings now. In the first occurence, it's a set; in the second occurrence it's a number. Also the meaning of the set $T$ isn't clear. Don't you just mean that there are $T$ time steps, say, $1$ to $T$? – joriki Oct 13 '12 at 3:21
By the way, you can get proper formatting for the subscripts of the probabilities like so: p_{\text{off}}. I've defined macros \pon and \poff in my answer that you can copy if you want. – joriki Oct 13 '12 at 3:23
up vote 0 down vote accepted

The transition matrix for each individual switch is

$$ \def\pon{p_{\text{on}}}\def\poff{p_{\text{off}}} \pmatrix{1-\pon&\pon\\\poff&1-\poff}\;, $$

where the first component corresponds to state $0$ and the second component to state $1$. The equilibrium distribution (with eigenvalue $1$) is $(p_0,p_1)$ with $p_0=\poff/(\poff+\pon)$ and $p_1=\pon/(\poff+\pon)$. The second eigenvector is $(1,-1)$, with eigenvalue $\lambda:=1-\poff-\pon$. Thus the marginal distributions for the individual switches approach equilibrium exponentially with $\lambda^t$. If $k$ and $N$ aren't very small, the time required to hit the desired configuration will be much longer than the time scale set by $\lambda$, so we can approximate the distribution by the equilibrium distribution and avoid a full non-equilbrium treatment, which would be rather complicated.

You didn't specify how you want to deal with events where the desired configuration persists for more than $j$ time steps. If you count every individual overlapping stretch of $j$ time steps as a separate success, then the long-term optimum would be to take $\lambda\to1$, since the probability of the configuration at any given time step being the desired one is independent of $\lambda$ and the probability for it to persist grows monotonically with $\lambda$. Thus, in order to have an interesting problem we should count each stretch of at least $j$ time steps with the desired configuration just once.

The probability for any given time step to start such a stretch is

$$ p_0^{N-k}p_1^k\left((1-\sigma p_1)^{N-k}(1-\sigma p_0)^k\right)^{j-1}\left(1-(1-\sigma p_1)^{N-k}(1-\sigma p_0)^k\right)\;, $$

where I've expressed everything in terms of $p_0$, $p_1=1-p_0$ and $\sigma:=\poff+\pon=1-\lambda$. The first two factors give the probability for the desired configuration to occur at the time step, the third factor gives the probability for this configuration to persist for $j$ time steps (i.e. through $j-1$ transitions), and the last factor gives the probability for the previous configuration to have been different. If $\pon$ and $\poff$ can be varied separately, we can treat $p_1$ and $\sigma$ as the two independent variables. To maximize the above probability, we can first maximize with respect to $\sigma$ for given $p_1$. That amounts to maximizing $x^{j-1}(1-x)$ with respect to $x=(1-\sigma p_1)^{N-k}(1-\sigma p_0)^k$, which yields $x=1-1/j$. Substituting this into the probability gives

$$ p_0^{N-k}p_1^k\left(1-\frac1j\right)^{j-1}\frac1j\;. $$

This is independent of $\sigma$ and is just a constant times the probability for the desired configuration to occur, and this is maximized for $p_1=k/N$. You can obtain $\sigma$ from $x$ numerically (the equation of $N$-th degree linking it to $x$ can't be solved analytically), but we can calculate the expected time between two separate persistent occurrences of the desired configuration without knowing $\sigma$, since this is just the reciprocal of the above probability,

$$ \frac{N^N}{(N-k)^{N-k}k^k}j\left(1-\frac1j\right)^{-(j-1)}\sim\frac{N^N}{(N-k)^{N-k}k^k}j\,\mathrm e\;. $$

Thus, asymptotically for large $j$, the expected time between separate persistent occurrences is just $j$ times $\mathrm e$ times the expected time between (not necessarily separate, not necessarily persistent) occurrences of the configuration.

[Edit:] I see from your comments and reading the question again carefully that you may seem to have intended the set of $k$ swtiches to remain fixed only for a particular stretch of $j$ time steps, not overall. In that case, the probability has another factor $\binom Nk$. This leads to another nice asymptotic simplification: for large $N$ and $k$, by Stirling's approximation we have

$$ \binom Nk\sim \frac{N^N}{(N-k)^{N-k}k^k}\sqrt{\frac N{2\pi(N-k)k}}=\frac{N^N}{(N-k)^{N-k}k^k}\frac1{\sqrt{2\pi p_0 p_1 N}}\;, $$

so the expected time between two separate persistent occurrences asymptotically becomes

$$ j\,\mathrm e\sqrt{2\pi p_0 p_1 N}\;. $$

Your additional question how to choose $\poff$ if $\pon$ is fixed or vice versa doesn't have such a nice solution in closed form, since in that case all four factors in the probability contain the one free variable; however, you can easily find the solution numerically for given values of the parameters.

That the optimal value of $p_1$ to maximize the equilibrium probability $p_k$ of exactly $k$ particular switches being on in any given time step is, unsurprisingly, $p_1=k/N$, can be seen by setting the derivative of $p_k$ with respect to $p_1$ to zero:

$$ p_k=p_1^k(1-p_1)^{N-k}\;, $$

$$ \frac{\partial p_k}{\partial p_1}=\frac kp_1 -\frac{N-k}{1-p_1}\mathop{\stackrel!=}0\;, $$

$$ p_1=\frac kN\;. $$

share|cite|improve this answer
I just did something awful to you, I changed the question while you posted the answer, and saw your answer after the posting. The change I made was to ask for the same set of $k$ light switches to be on, and to have them on for $j$ time intervals. – Afternoon Tea Oct 13 '12 at 3:20
Sorry about that. If you'd like I can roll back the changes, accept your answer, and post the change as a new question. I don't know what the proper etiquette is here... – Afternoon Tea Oct 13 '12 at 3:22
@Afternoon: Thanks. If the question I answered were more interesting, that would be a good way to proceed, but since $k/N$ is just what one would expect, I think I'll just overwrite the answer with an answer to your actual question. – joriki Oct 13 '12 at 3:33
Whatever you'd like is fine, thanks for thinking about my question! – Afternoon Tea Oct 13 '12 at 3:43
@Afternoon: You're welcome. I've updated the answer to address the new question. – joriki Oct 13 '12 at 7:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.