Help Specify possible definitions for this Boolean Function

Question

My math is rusty, but I need some guidance here.

Problem

I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$.

I have the following constraints specifying the possible states configurations:

1. The promotion runs from Date $d_1$ to $d_n$ for $N$ days
2. Between the days $d_1$ to $d_n$, there can only be a maximum of $M$ winners.
3. It is preferable (but not necessary) to uniformly distribute the winners over the days $d_1$ to $d_n$, thus, on a given day $d_i$, it is preferable to limit the maximum number of winners to $K = {M\over n}$.
4. On a given day $d_i$, it is also preferable to uniformly distribute the winners across the total number of time units $T$ in the day, so that the probability that a person arriving at the promotion at time $t_j$ can win is $1\over T$.

Additionally, at any given time $(d_i,t_j)$

• let $m$ be the total number of actual winners between the day range $d_1$ to $d_i$ so far.
• and let $k$ be the total number actual winners between the time unit range $t_1$ to $t_j$ so far.

It is required to fully define a function or algorithm, $f(i,j,m,k,N,T,M,K)\to [0,1]$

My Attempt So Far

$f(i,j,m,k,N,T,M,K) =\begin{cases} 1 ,\text{if }|rand() - ({N-i\over N}).({T-j\over T}).({M-m\over M}).({K-k\over K})| \le \epsilon \\ 0 ,\text{otherwise} \end{cases} $

Where, $rand()$ is a random-number generating function over $[0,1)$, e.g the inbuilt random function of the python programming language.

Am not sure (and that's part of why I need help), whether this implementation of mine is correct (or true to the spec).

Update:

Definitely, $rand()$ doesn't necessarily have to be equal to the expression (refer to my attempt), but for $|rand() - expression| \le \epsilon$, where $\epsilon$ is suitably small.

Answer 1

Here is a partial solution. Suppose you are just trying to distribute $K$ tickets over $T$ time units, $K\leq T$. What you really want is a probability function that assigns a probability of winning, given the state.

Assume that there is exactly one visitor every time interval. Let $t$ be the number of time intervals elapsed and $k$ be the number of winners so far. I propose the function $p(t, k, T, K) = (K-k)/(T-t)$.

One can easily confirm that this function will always produce exactly $K$ winners, assuming a constant stream of visitors. I further claim that this probability function produces a uniform probability of $K/T$ of winning at any given time. The proof goes something like this. Let $q(t, T, K)$ be the probability of winning at time $t$ given initial conditions $T$ and $K$. Then $$q(t, T, K) = \frac{K}{T}\cdot q(t-1, T-1, K-1) + \frac{T-K}{T}\cdot q(t-1, T-1, K)\mbox{.}$$ You can use this to inductively prove the claim that $q(t, T, K) = \frac{K}{T}$.