Monday, January 4, 2010

Minyanim and Mathematics: A protocol for anonymous counting.

In Judaism, many communal prayers require a minimum of ten people. This quorum is called a "minyan" which is often also used to mean a service in general. (In Orthodox Judaism, only Jewish adult males count for a minyam while in Conservative Judaism all Jewish adults count). However, certain liturgical elements on fast days (such as a Torah reading at the afternoon prayer) require not just ten present, but ten who are actually fasting.

However, people may not wish to advertise that they are not fasting even if they are willing to assist with the minyan. Moreover, even a very observant individual might have a reason not to fast and would not want people to know about it (such as a medical condition). This leads to the following problem: How do we determine how many people are fasting without requiring people to disclose whether or not they are fasting?

In a recent minyan I attended, this question was handled by the gabbai (the person in charge of running the minyan) asking everyone to close their eyes and hold up one hand if they were fasting. This is obviously unsatisfactory since the gabbai finds out who is fasting. One could suggest slips of paper or the like. but they could be easily connected to particular individuals. To make this problem interesting, it is helpful to assume that everyone knows the identity of the sender of any communication they receive. Is there a solution under which individuals' statuses remain private while the minyan is assured of 10 fasters?

Curiously the answer is yes albeit the solution is a bit cumbersome. Here's how: The gabbai picks a random integer (the distribution doesn't matter although in practice one might want a reasonable distribution that approximates a bell curve or an exponential distribution or something similar). The gabbai takes this integer and adds 1 to it if he is fasting. The gabbai whispers this number to another person. That person adds 1 to the total if he is fasting and similarly passes it on to another person. The last person gives his number to the gabbai. The gabbai now subtracts the random integer that they initially added. The total the gabbai has is the number of people fasting.

A few notes about this algorithm. First, it is important that, when the gabbai is picking a random integer, that every integer has some non-zero probability of being chosen. Consider, for example, what would happen if the gabbai was known to only pick positive integers. If the gabbai picks 1, the next person can tell if the gabbai is not fasting. Thus, the gabbai can never pick 1. But then, by the same logic, the gabbai won't be able to pick 2. Or 3. And so on. This problem is avoided if the gabbai can pick any integer whether or not it is positive.

There is also a degenerate case of if only the gabbia is fasting or only the gabbai is not fasting. In those cases, the exceptional individual can work out the status of everyone else.

The algorithm also assumes that people are not going out of their way to obtain information. If two people bracket a third and cooperate, they can figure out the middle person's status as a faster.

In fact, it turns out that it is possible to make a more sophisticated protocol that would prevent this and similar tricks. This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. Implementation also would require much more computation than can be done by hand.

Less intensive algorithms can be used to increase the number of people who must cooperate. It is, for example, an interesting exercise to construct a variation of the above such that finding out someone's status requires the cooperation of at least three people.

This algorithm in practice is cumbersome. Moreover, the goal it seeks to accomplish is minor since, if the fast day liturgy is used, those sections of the services actually need to be performed by people who are fasting. Thus, the gabbai will need to know the status of at least a few people. However, this algorithm has the slight advantage that, if there are not enough people to recite the fast day liturgy, then no one will know which people cause the deficiency.

Johan said...

"This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. "

What if we require information-theoretical security? Is it known that it cannot be done?

Amnon said...

Here's another "Minyanim and Mathematics" for you:

A few years ago I attended a very ordinary (orthodox) minyan on a very ordinary weekday (with a very ordinary spread of ages). When it came time for mourner's kaddish, there was silence - there were no mourners present. Surely the chances of this happening are tiny - it never happened to me before, and hasn't happened since.

With some basic assumptions (distribution of arrivals, ages, mortality, age differences between people and their parents/spouses, etc, etc), this shouldn't be too hard to calculate. Any actuaries out there?

Joshua said...

Johan, I suspect that it is doable likely using a variation of the generalization to three people, but I don't know enough to construct or prove such a claim. I think it be doable if one has each person add a series of random number and their vote number and then have subsequent rearrangements where each person going through subtracts off one of their random numbers.

Amnon, it isn't that infrequent in small minyanim, especially on college campuses. Without detailed actuarial knowledge I wouldn't be able to calculate it (and I'm certainly not an actuary). But here's a rough estimate: Suppose there are k people in a minyan and suppose people live about 80 years. So for an average individual the chance (roughly) that one parent died in the last year is about 1/80. This is obviously not correct since people under about 12 years old can't have kids and people under 20 aren't likely to have kids. So let's say for the k people the chance is about 1/60. That means that the chance that either parent died in the last year should be about 1- (59/60)^2 which is about 3.3 percent. Assuming a usual minyan has around 25 people, the chance is about 43%% that no will have to say kaddish due to a parent.

However, the minhagim for when people say kaddish for other relatives is complicated. For example, some people have a minhag not to say kaddish for brothers and sisters if the parents are still alive to do so. So one would not only need actuarial data for that but also some idea what the breakdown is by tradition.

Also, one has kaddish on the anniversary of a death. This entire matter is also complicated by the fact that many people go to shul specifically when they need to say kaddish and wouldn't show up otherwise. So the effective pool for people who would potentially need to say kaddish is in reality generally much larger than the size of the minyan actually present.

cipher said...

Don't enable them!

Out of curiosity, which shul was it?

Joshua said...

Cipher, this was at the Orthodox minyan at Boston University.

cipher said...

Ah. I was wondering if it was one of the shuls in Brookline or Brighton.