1
$\begingroup$

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?

  • 0
    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").2012-10-13
  • 0
    @joriki Good catch. I changed "only" to "exactly".2012-10-13
  • 0
    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.2012-10-13
  • 0
    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$?2012-10-13
  • 0
    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.2012-10-13
  • 0
    @joriki The question now, as formulated, is the intended form. I'm sorry about wasting your time earlier. Yes, we can simply treat $T$ as the number of time steps.2012-10-13
  • 0
    @joriki I've reformatted the text for the probabilities as recommended, thanks.2012-10-13
  • 0
    @joriki To be sure to avoid any confusion, I also added a clarification that the $k$ light switches, should be the only light switches on.2012-10-13

1 Answers 1

0

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\;. $$

  • 0
    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.2012-10-13
  • 0
    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...2012-10-13
  • 0
    @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.2012-10-13
  • 0
    Whatever you'd like is fine, thanks for thinking about my question!2012-10-13
  • 0
    @Afternoon: You're welcome. I've updated the answer to address the new question.2012-10-13
  • 0
    I'm perfectly fine assuming an equilibrium distribution, i.e. where we start out after an arbitrary amount of time $t_0$.2012-10-13
  • 0
    As a quick question, are you calculating the probability of a stretch in which any configuration of 'k' light switches are on? Or are you calculating for some specific set of 'k' light switches? It appears to be the former? Either case is fine.2012-10-13
  • 0
    The latter. Why do you think the former? That would have a binomial coefficient $\binom Nk$.2012-10-13
  • 0
    I apologize, I misspoke. We're calculating the probability a specific configuration of $k$ light switches remains on for $j$ time intervals. However, this particular set of $k$ light switches can be any subset of the $N$ switches as long as it remains consistent throughout the interval, right?2012-10-13
  • 0
    @Afternoon: I think I misinterpreted the question in that regard. I think I see now how you meant it. I've added a bit to the answer in response.2012-10-13
  • 0
    Thanks! So I simply add a coefficient of Binomial[N,k] to the probability at a given time step to start a stretch of length $j$? As such, that shouldn't effect any of the optimizations, great.2012-10-13
  • 0
    @Afternoon: Yes. Did you see the edit in the answer? The asymptotic result is now rather pretty.2012-10-13
  • 0
    Thanks for taking so much time to answer my question!2012-10-13
  • 0
    @Afternoon: You're welcome!2012-10-13
  • 0
    @Afternoon: No, I understood that the other switches are supposed to be off, and they are; that's what the factors $p_0^{N-k}$ ($N-k$ switches are off) and $(1-\sigma p_1)^{N-k}$ ($N-k$ switches stay off) are for.2012-10-13
  • 0
    All good, typo on my end. Looks like we're finished here, thanks again. =)2012-10-13
  • 0
    Everything still looks good, but I don't understand your comment about "separate" events. If you get a chance, could you provide an example of what you mean? It seems to me that, if a particular set of k switches are on, and everything else is OFF, then flipping any switch will create a new set on ON switches, so there's no overlap...2012-10-13
  • 0
    @Afternoon: Sorry, you're quite right, I was confused when I wrote that. I'll delete that comment.2012-10-13
  • 0
    I realize I may not have understood something. When you say that "The probability for any given time step to start such a stretch is..." what exactly did you mean? Obviously when (Pon + Poff) << 1, the probability of anything happening in a given step approaches 0, but for Pon = 2.3*10^(-11) and Poff = 2.3*10^(-9), the computed probability Pr[stretch of at least length 300] = 0.369711. Here we sum Pr[...] for values of j = 300 to infinity.2012-10-14
  • 0
    Did you mean the conditional probability provided that a switch is flipped?2012-10-14
  • 0
    @Afternoon: No, I believe the expression is correct; it seems that you miscalculated. The condition that a switch was flipped is represented by the last factor. For your tiny values of $p_{\text{off}}$ and $p_{\text{on}}$, that factor should be very close to $0$.2012-10-14
  • 0
    I don't see anything wrong with your derivation, but I recalculated and got the same result. k = 1, M = 100, P(on) = 2.3*10^(-11), P(off) = 2.3*10^(-9), and the sum for j = (300 to Infinity) gives a probability of 0.369711...2012-10-14
  • 0
    In Mathematica notation: Sum[Binomial[M, k]*(P0^(M - k)* P1^k)*((1 - r*P1)^(M - k)*(1 - r*P0)^k)^(j - 1)*(1 - (1 - r*P1)^(M - k)*(1 - r*P0)^k), {j, 300, Infinity}], where we define P0 = P(off)/(P(on)+P(off)), P1 = P(on)/(P(off)+P(on)) and r = (P(on)+P(off))2012-10-14
  • 0
    @Afternoon: Sorry, I hadn't read the "here we sum ..." part of your earlier comment attentively enough. There's no need to sum; the probability itself is already the probability for a stretch of *at least* $j$ times steps; summing it like that just multiplies it by a huge factor. If you wanted the probability for a stretch of *exactly* $j$ time steps, you'd have to include another factor of $\left(1-(1-\sigma p_1)^{N-k}(1-\sigma p_0)^k\right)$ to make sure the configuration changes after the $j$-th step.2012-10-14
  • 0
    OH! The "at least" part tripped me up, thanks for the clarification!2012-10-14
  • 0
    Is there an intuitive reason why it would be the case that for j=1 and k=1, P(off) = 1/2 is optimal for optimal P(on)?2012-10-15
  • 0
    Actually, it seems like P(off) scales as ~1/(2*j)... interesting.2012-10-15
  • 0
    @Afternoon: For $j=1$ and $k=1$, you're just trying to get the switch to go on and off as often as possible. It seems pretty intuitive to me that that will happen if $p_{\text{off}}=p_{\text{on}}=1/2$. The expected time to go on and off once in this case is $p_{\text{off}}^{-1}+p_{\text{on}}^{-1}$, which diverges as either probability goes to zero, so it seems clear that the optimum is in the middle.2012-10-15