Bernoulli Trials of Fixed Parity,Random and Randomly Oriented Graphs

Suppose you can colour n biased coins with n colours, all coins having the same bias. It is forbidden to colour both sides of a coin with the same colour, but all other colourings are allowed. Let X be the number of different colours after a toss of the coins. We present a method to obtain an upper bound on a median of X. Our method is based on the analysis of the probability distribution of the number of vertices with even in-degree in graphs whose edges are given random orientations. Our analysis applies to the distribution of the number of vertices with odd degree in random sub-graphs of fixed graphs. It turns out that there are parity restrictions on the random variables that are under consideration. Hence, in order to present our result, we introduce a class of Bernoulli random variables whose total number of successes is of fixed parity and are closely related to Poisson trials conditional on the event that their outcomes have fixed parity.