Sociologist Al Dahdah
email: .marine.aldahdah@gmail.com

Forthcoming in Development and Change Between philanthropy and big business, how mHealth becomes a new technical device for global health

Keywords: MHEALTH, DIGITAL HEALTH, PHILANTHROPY, MATERNAL HEALTH

With seven billion users in 2017, mobile phones have become the most widespread communication technology worldwide. From appointment reminders to mobile glucometers, healthcare systems are increasingly using mobile technologies to improve healthcare. These programs, called 'mHealth', contribute to the present shift in international health described by many scholars as 'global health'. Thus, dynamics of globalization and commodification associated with global health justify and encourage the spread of technical devices such as mHealth in the global South. Deployed by global players to respond to global challenges, mHealth engages strong participation by private actors. Based on the ethnography of an mHealth program implemented in Africa and Asia, this article analyzes the broader impact of mHealth initiatives on the contours of public health systems. It focuses specifically on power dynamics, philanthropic and market interests underlying the expansion of these new technical artifacts in the global South. It shows that advocates of mHealth play a major role in the commodification of health by addressing health issues as marketing cases and considering developing countries as untapped markets. It highlights how mHealth contributes to the creation of private health markets at the bottom of the pyramid in the global South that benefit the Northern digital economy.

Mobile operators, cell phone manufacturers and private foundations from the digital sector constitute core stakeholders of mHealth programs. All newcomers on the scene of international health, they contribute to the high proportion of private investors and publicprivate partnerships already associated with global health (Adams et al., 2008; Atlani-Duault and Vidal, 2013; Ollila, 2005). This evolution has mostly been studied through partnerships with pharmaceutical companies (Gerrets, 2010; Guilbaud, 2015) aimed at deploying vaccines or medicines. In line with a techno deterministic vision of aid (Cherlet, 2014), mHealth embodies a different convergence of interests between public health actors and private actors from the digital industry, a techno political convergence (Fejerskov, 2017) that has impact on the perimeter of public health itself. Based on empirical data collected between 2014 and 2015 in Ghana and India 1 , this article focuses mainly on interviews with stakeholders of mHealth programs in these two countries and particularly on one case study: Motech.

Funded by the Bill and Melinda Gates Foundation, the Mobile Technology for Community

Health project (Motech) was developed to improve maternal and child health in rural areas in developing countries thanks to mobile health devices. This project combines modules of health information for pregnant women and health professionals, identification and tracking of patients, collection and processing of health data, SMS alerts and voice messages. A hundred face-to-face in-depth interviews were conducted in English and/or Hindi with professionals involved in mHealth programs in Ghana and India 2 . Among these interviews, forty involved stakeholders directly engaged in the implementation of the Motech project 3 . A qualitative survey dedicated to the usage of Motech was also conducted at the village level in two districts of Ghana in 2014 and two districts of Bihar in 2015. 35 Motech project administrators, 20 health managers, 50 community health workers, and 200 women enrolled 1 This research was funded by a doctoral scholarship from the French National Research Agency on AIDS, HIV and Hepatitis, a french public research agency. This research is not part of any implementation or evaluation studies that were conducted by the mHealth stakeholders cited and studied in this paper, it never received any funding or guidelines from them. The Ghanaian fieldwork took place between May and September 2014, several fieldworks took place in different locations in India mainly Delhi and the State of Bihar, between November 2014 and October 2015. 2 With employees from ministries of health and Telecommunications, public health agencies, United Nations agencies, NGOs, mobile operators, digital agencies, mobile operators, and private foundations all involved in mHealth programs implemented in Ghana and India in 2014-2015. 3 Face-to-face indepth interviews were conducted in English or Hindi with employees from Gates, Grameen and BBC foundations in charge of Motech in Accra, Delhi and Patna in 2014 and 2015.

in the program were interviewed in focus groups or in face-to-face interviews conducted in English or in the local languages (Fanté and Hindi) with the help of a local researcher. All the interviews were fully transcribed in English and imported in nVivo software along with the field notes to conduct a qualitative analysis4 .

The Motech project encloses implementation of different interrelated services using mobile phones. The two major services are a health information messaging services for pregnant women and lactating mothers and a data management system for community health workers (Grameen Foundation Ghana, 2014). The aim of the first application is to provide maternal health information for pregnant women, mothers with children younger than 12 months and their families. Women can sign up to receive text or voice message in one of the regional languages with time-specific health information. The less than two minutes weekly messages encourage pregnant women to seek antenatal and postnatal care and to deliver in a health facility. In the first year of the child, the messages continue with health information regarding nutrition and health advice for the mother and child, such as family planning and alerts for immunization. The second application allow health workers to collect data on pregnant women and to plan their work accordingly, the system sending them automatic reminders about due dates of pregnant women under their responsibility. Motech was launched in Ghana in 2010 as a free mobile device, it was exported to India (State of Bihar) two years later based on the Ghanaian experience but as a fee-based service; pregnant women had to pay 1 rupee per vocal message.

The Bill & Melinda Gates Foundation (BMGF) is Motech's main sponsor from the Ghanaian launch in 2010 until the Indian national extension in 2016. Each year, the Gates Foundation allocates more than $3 billion in grants to development projects, one-third of which is dedicated to 'global Health' programs. For Gates, improving health essentially requires new technologies (Fejerskov, 2017). By suggesting the use of mobile technologies to improve maternal health in the developing world, Motech fits perfectly into a 'Gatesian' vision of health: a precise technological response to a particular health issue. The proposed mHealth technology is even more innovative than a vaccine or a drug program, as no mHealth devices had ever been deployed in the global South before 2008. From philanthropic grants to the commercialization of the device, Motech's itinerary echoes the notion of 'philanthrocapitalism', a way to deploy new markets through a good cause (Bishop and Green, 2008). Bishop and Green identify the peculiarities of this two-tier philanthropic movement. At the micro level, philanthrocapitalists want to change the way philanthropy is done by applying Big Business rules to the charitable sector (by monitoring scholarship recipients, imposing profitability indicators and accounting targets). At the macro level, philanthrocapitalism refers to how capitalism itself can be naturally philanthropic, bringing social innovations through new products that benefit everyone (Bishop and Green, 2008). This term has since been taken up by several authors to explain a new way of giving which has become preponderant in many global health PPPs and development programs financed by private actors (Aneja 2016, Global Health Watch 2011, Martens and Seitz 2015). This article will discuss the dual philanthropic and commercial dimension of mHealth initiatives and demonstrate how mHealth can be used as a strategy to develop new markets in the global South. This article proceeds in two steps. As a first step, it will look at the public-private partnership (PPP) and initial funding of Motech and analyze how these philanthropic donations are investments for mHealth funders. In a second step, it will show how the logics of markets have determined the itinerary of Motech and how mHealth is big business after all.

MHEALTH, A PHILANTHROPIC INVESTMENT

mHealth is at the intersection of two markets, at the crossroads of mobile services and health products. Thus, the 'mobile phone' component of mHealth is constantly drawing these devices towards mobile-related commercial dynamics. Estimated at $26 billion in 2013, the mHealth market responds to the mercantile logics of the telecommunications sector that sometimes undermine the health expectations that some may have vis-à-vis these services (Pew Research Center 2012; research2guidance 2013). The example of Motech illustrates the way in which philanthropic and commercial logics intersect, making mHealth a product of capitalism.

mHealth programs are systematically relying on donations from digital companies or private ICT foundations. These new philanthropic entrepreneurs from the early 2000s -the Gates Foundation being a flagship among them -suggest a rapprochement or even a fusion of commercial exchange and giving. Philanthropists can choose the gift, through the special advantages it offers for businesses, as a form of tax-exempt investment. In the United States, as in most liberal countries, philanthropic foundations are tax-exempt, and contributions to these foundations are subject to significant tax deductions (Birn 2014). In 2006, when Warren Buffett announced his donation of $37 billion to the Gates Foundation, he was quick to point out that the money given would be more useful than in the pocket of the US Treasury, a feeling shared by other philanthropists who, through their foundations and with the help of renowned accounting firms, set up complex tax avoidance systems (Sikka 2013). The Gates Foundation is involved in such strategies and the majority of its funds are allocated to organizations exempt from taxes 5 . This phenomenon is evident in the Motech project, as the Gates Foundation's funds are majorly allocated to two private foundations which benefit precisely from this exemption status: the American Grameen Foundation 6 and the British BBC Media Action 7 . The Grameen Foundation is a transversal actor of the project, in charge of the technical aspects and implementation in Ghana, whereas BBC Media Action manages implementation in India. Thus, the first recipients of Gates' money for Motech are philanthropic foundations from the global North.

Philanthropists investing in philanthropic foundations

Motech was created and survived because of the multiple grants provided by the Gates Foundation. From 2010 until 2012, Grameen Foundation received a first grant of $ 4.3 million for Motech's Ghanaian pilot, a second of $ 2.75 million, and a third of $ 2 million through the 'Grand Challenge Saving Lives at Birth' grant that Gates co-administers. Thus, since 2010, at least nine million dollars have been allocated to Grameen Foundation for the 5 Excerpt from Gates Foundation website : http://www.gatesfoundation.org/How-We-Work/General-Information/What-We-Do-Not-Fund, consulted on 02/04/16. 6 Founded in 1997, the Grameen Foundation is part of the nebula of organizations (around fifty) -Grameen Danone, Grameen Phone, Grameen Intel -which follow the philosophy of the micro-credit bank, established in Bangladesh in 1976 by Mohammed Yunus. This American foundation aims to disseminate the Grameen bank model by providing access to micro-credit and by offering banking services adapted to 'the poorest of the poor'. The foundation moved into digital technology at the beginning of 2000 and has been involved in the 'mobile for development' sector, mainly through mobile banking services (mMoney or mBanking) for the poor. 7 Founded in 1993, BBC Media Action is the philanthropic arm of the BBC Group. The Foundation calls for the use of Media and Communication to reduce poverty. Based in London, the foundation extended its operations to India in 1999. The Gates Foundation is the second largest donor to the BBC Foundation after the British Department for International Development (DFID).

Motech project in Ghana. However, this is only the most visible part of Motech Ghana's funding since, as of 2008, the Gates Foundation had already allocated a $ 4 million grant to Grameen Foundation for mobile health services in Ghana, not yet called Motech but certainly laying the foundation for it. For the Indian expansion of Motech, the Gates Foundation allocated four successive grants to Grameen Foundation to adapt the Motech platform to the Indian context (totalling $3.45 million). Indeed since 2006, the Grameen Foundation has received 14 grants from the Gates Foundation to develop mobile services for the poor, covering at least an amount of $38 million, including $13 million allocated to Motech.

Thanks to Motech, the Grameen Foundation has developed an expertise in mobile health systems that can be mobilized for other health issues in other countries. It is a central actor for Motech in Ghana, as it developed the technical solution and implemented the program in the different districts of Ghana, but in India the first recipient of Gates' money was the British BBC Foundation.

For the Motech project in Bihar, the BBC Media Action Foundation takes over the role that Grameen Foundation had in Ghana, as field implementer and project manager. The Gates Foundation is the second largest donor of the BBC Foundation after UK Department for International Development (DFID). Since 2006, BBC Media Action has received $41.7 million from the Gates Foundation, spanning 8 grants. 80% of these funds were allocated exclusively to India ($33.6 million), of which 95% was exclusively focused on Bihar ($ 31.8m). The $27.6 million awarded by the Gates Foundation in December 2010 to the BBC Foundation for the Bihari project represented the equivalent of 75% of its total allocation for the previous year, a considerable sum for the Foundation. Thanks to the surge of Gates' grants, in 2011 it will change its name and increase its payroll by 45% in just a year8 . BBC Media Action is the central actor in the implementation of Motech India. For this purpose, the foundation had to open an office in Patna, the capital of Bihar, with a team dedicated to the project. It also has a large team in its Delhi office that runs extensions of Motech deployed in other Indian states. Moreover, BBC Foundation has been working since 2014 on extending Motech apps to the rest of India but funding for this national extension of Motech is particularly opaque, as no official grants had been allocated to BBC Foundation.

Both Grameen and BBC Foundations have been focusing their activities on digital technologies over the past five years. Both foundations have so-called technical teams that manage the technological dimension of the Motech project, but it is more about supervision and direction of the technical platform. Indeed, private IT companies from USA and UK are involved in the evolution of Motech's code, computing components, servers, databases, and IVR systems. They received either a large chunk of the grants received by Grameen and BBC foundations as subcontractors or autonomous grants directly allocated by the Gates foundation.

Philanthropic investments in private IT companies

The Gates Foundation presents itself, above all, as a 'technical expert' and not a 'simple donor', as explained by one of its employee: 'We don't give money if we don't know the area and can support you in terms of technical inputs' 9 . The Motech platform and its applications embody the technical expertise of the Gates Foundation in the brand-new field of mHealth. In fact, the Gates Foundation relies on a number of technical partners who are concretely in charge of developing the Motech platform. They are numerous, they vary in size, but all of them are private players from the global North, with a non-profit as well as a for-profit status and agenda.

If the first recipients of Gates' grants are philanthropic foundations it means that on the one hand the Gates foundation does not give grants to the states and on the other hand that the granted funds will not be taxed when arriving in the-also exempted-grantee's pocket. The public treasury will therefore not receive any share of these monies. But one could argue that the Gates Foundation is not responsible for favourable tax policies for philanthropic activities. However, things get more problematic when the Foundation offers grants to private, for-profit companies.

Taking the example of the world's best-known mobile banking service, mPESA, Lindsey

McGoey describes the double tax exemption mechanism involved. In 2010 and 2011, the Gates Foundation allocated $7.7 million to Vodacom (UK Vodafone Group) to deploy 9 Interview with B., Private Foundation, Delhi, February 2015 mPESA in Tanzania. Through this transaction, it exempts the Telco from paying taxes on 'development' activities related to these millions of dollars in grants (McGoey 2013, 85). In the field of telecommunications, it is apparently easy to maintain the confusion between philanthropic donation and investment in commercial products like mPESA that is now a lucrative mobile service sold by one of the biggest multinationals.

Motech presents the same configuration. Privately owned IT companies, have received millions from Gates in tax-exempted grants to develop software that will be part of their portfolio of commercial technical solutions. This double exemption system is a noticeable strategy of private foundations and ICT developers, who can thus save large sums on their research and development budget. In line with recent international and multilateral negotiations to favour Northern-led digital commerce in the global South, BMGF grants are then helping to develop UK and US digital industry and its new markets in the global South (Dolan, 2012; Foster and Azmeh, 2018; Mann, 2018).

Dimagi is Motech's most visible technical contractor 10 . This American 'social enterprise' specialized in ICT for development (ICT4D) has been working with Grameen since February 2012 to improve Motech: 'Dimagi is also our partner at a higher level, for any Motech work.

Any project that has a Motech component they are involved with. Grameen and Dimagi both work together on the customization' 11 . Since Dimagi joined the Motech project, the company has received at least $ 13.3 million of grants from Gates to develop mobile technologies in developing countries 12 . Dimagi employs about a hundred people worldwide with teams mainly at the company headquarters in Cambridge, Massachusetts, but also in Delhi. Dimagi is an interesting example of a global North company geared towards the global South; it is a recognized member of the American benefit corporations group or B Corp, a label that unites 10 'Dimagi is a software social enterprise that develops technologies to improve service delivery in underserved communities. Dimagi operates on the belief that enabling high-quality mobile solutions at scale can impact millions of people's lives' quote from Dimagi's Website : http://www.dimagi.com/about/ consulté le 05/04/16. 11 Interview with R, Private Foundation, Delhi, February 2015. 12 Dimagi has received between 2012 and 2015, $ 12 million for the global Motech platform and $ 1.3 million explicitly posted on India according to Gates' Foundation Website, section « Grantees » consulted on 05/03/15. the adepts of 'social capitalism'. According to Dimagi Vice President Carter Powers, Dimagi's mission is triple: 'impact, team satisfaction and profit' 13 .

With the national extension of Motech in India, another international digital company is emerging as Motech's partner: IMImobile International Trade shows that developing countries lose at least $100 billion in annual 13 Excerpt from "For many, 'B Corp' is good business". Boston Business Journal, 10 February 2012. 14 'IMImobile enables organizations of all sizes and sectors to maximize the potential of mobile technologies to improve customer engagement. We believe that mobile will sit at the heart of customer engagement strategies for years to come' quote from IMImobile's Website consulted on 05/04/16.

revenues from the tax evasion mechanisms of multinational corporations (UNCTAD 2015), billions that could be invested by these same developing countries in health or development programs. Nevertheless, Motech has been advertised from the beginning as a public-private partnership for health. Then, what kind of participation of public authorities and governments does it involve?

Relying on The State as a logistics partner and financial guarantee

While private stakeholders are large players in Motech PPP, the participation of public authorities and governments is nevertheless indispensable, first and foremost in terms of image. In order to limit the risks of being accused of blatant neo-colonialism, private players from the global North are strongly encouraged to develop partnerships with the governments of the developing countries where they wish to implement their programs. Beyond image issues, the collaboration with the states can be useful for obvious reasons of field knowledge. Indeed, if private foundations and companies from developed countries oversee the Motech project, local anchorage is essential to be able to effectively implement the program on the ground. Governments and local health actors act as crucial relays to better understand the local context and issues that can emerge on the intervention sites. This local expertise is a reason to involve public actors in projects, as one of the Motech manager explained in Delhi:

'The first challenge is when global institutions like BMGF get involved in implementing the programs, they do not have a very good understanding of local dynamics, so most of the officers of BMGF they come from Seattle USA, which is a very different market, a very different world compared to Bihar'15 . The involvement of public health facilities and health workers can also be helpful in terms of logistics. Local public actors facilitate the deployment of programs at the grassroots level at practically no cost since the project does not have to pay the state agents; this facet is described by an official from the Ministry of Health in Ghana: 'we have a broader presence everywhere. So the health workers are there so you don't have to pay them, they are paid through the public system, so you come and you sell the idea and it trickles down and it's implemented' 16 . BMGF therefore also initiated collaboration with the Ghanaian government and the State of Bihar in order to deploy Motech at the village level with the support of local health workers.

If the state is included in the PPP both as a logistics partner and as an expert on local issues, it can also be seen as an outlet for the devices and an additional guarantee of their sustainability. The state then becomes a trading partner to which the device is to be sold when philanthropic grants have dried up. This commercial dimension and attempts to sell products promoted by PPPs in the global South have already been denounced for partnerships on access to medicines or vaccines. Several reports and research papers have highlighted the interests of Big Pharma to introduce HPV or TB vaccines through PPPs in India for instance (Birn 2014, Global Justice Now 2016, McGoey 2015). The involvement of states as future buyers of the product developed by PPPs is also very strong in IT and digital health partnerships, as Motech proves. In India and Ghana, once the philanthropic manna was over, the government's take-over seemed to be the first possible outcome according to the three foundations (Gates, Grameen and BBC). The role of the state in PPPs such as Motech is thus far from being negligible, but this partnership is not a win-win, contrary to what is constantly showcased. States are helping to deploy the devices, might be ready to take over some of them, but these devices are sometimes not compatible and even unsuited to the needs of local infrastructures. Some governments even feel exploited and do not wish to extend collaborations like Motech. This is the case of the Ghanaian ministry of health, which refused to maintain its collaboration with Motech because it hijacked its public workforce: 'we'll not be part of what they are doing because we know that they are wasting our time. They can spend their money and then go and it ends' 17 . Critics of PPPs argue that if these partnerships cannot benefit the public partners in the global South, they surely can benefit philanthropists and private partners who set them up (Biehl and Petryna 2013). They point to the complex entanglement of commercial and philanthropic interests that are evident in ventures like mHealth.

Philanthrocapitalists, through their gifts, display their belief in the inefficiency of the state and their aversion to mechanisms of distributive justice such as taxation. They believe in managerial performance and prosperity through markets: in this respect, they consider the gift as a capitalist investment to be monitored and made profitable. As Bill Gates explains, generous involvement calls for recognition, a 'return' on investment (Gates 2008, 2). These entrepreneurs advocate a more rational management of the funds allocated by philanthropy, 17 Interview with O., GHS, Accra, June 2014.

in particular through support for narrow and short-term projects; they also claim a greater attention to and a stronger hand on implementation processes. The Gates Foundation describes its operations in terms of strategies, objectives to be achieved, allocation of resources, and investment 18 . This way, the notion of investment-the sacrifice of resources today to hope for profit tomorrow-is central to the discourse of ICT philanthropists. It is precisely this return on investment that is at the heart of 'philanthrocapitalism'. Birn offers a historical perspective on this form of donation and highlights an entrepreneurial vision already present with early 20th century philanthropists like Carnegie or Rockefeller. But she explains that today's philanthrocapitalists carry the commercial dimension of gift and the valuation of commercial interests farther than the ancestors of philantrocapitalism. She emphasizes that beyond commercial interests, the idea is now to move health from the public domain to the private commercial sector (Birn 2014). There is 'no such thing as a free gift' as stated by Lindsey McGoey and this form of philanthropy is, in fact, a new way to make huge profits (McGoey 2015).

MHEALTH IS BUSINESS

Motech in Ghana gives an interesting illustration of philanthrocapitalism. The MTN foundation contributed to the Motech pilot project in the Upper East region of Ghana, through a temporary exemption of airtime costs. MTN -Ghana's leading Telco -has clearly stated its foundation's goal of investing in ICT-oriented development projects: 'Now the foundation is only focusing on ICT related projects, our vision is to become a leader of a new bold digital world.' 19 . The foundation therefore finances projects close to its core business ; Motech was its first project in the health sector. The operator first offered free data and call time for the pilot phase in the Upper East region, but reintroduced fees when the project was extended to the Central region. The mobile operator MTN therefore participated in 2010 in financing the Motech pilot scheme through its foundation. Later on in November 2013, MTN launched a fee-based commercial version of the same application in Ghana: 'It's for MTN users only. The fee is split in two, 50% for Grameen and 50% for MTN' 20 . We can therefore 18 Gates Foundation website : http://www.gatesfoundation.org/How-We-Work consulted on 02/04/16. 19 Interview with R, MTN Foundation, Accra, June 2014. 20 Interview with E, Grameen, Accra, June 2014.

safely say that MTN has capitalized on its philanthropic participation in the Motech project by launching a Motech fee-based mobile service only two years after its philanthropic investment. In this way, mHealth constitutes a new field of investment for MTN to develop new commercial mobile products.

The itinerary of Motech in Ghana and India illustrates the commercial turn that mHealth can take. Initially conceived as a randomized controlled trial (RCT), Motech Ghana did not start with obvious mercantile characteristics. Indeed, it was positioning itself as a free service offered to pregnant women and healthcare workers. Nevertheless, from the beginning the Motech documentation used the word client to talk about beneficiaries of the program, which positions the device in consumerist logic. The world of mobile phones and mobile applications reinforces this mercantile approach and dramatically draws mHealth towards commercial consumption practices. The commercial dimension of Motech will be strengthened over time and the launch of the paid application by MTN in Ghana in 2013 marks a decisive turn towards markets for Motech; Motech then becomes a product of the mobile economy provided by a multinational company. Launched at the same time, the Indian version of Motech was conceived from the beginning as a marketing venture.

Sales techniques

In charge of the implementation of Motech in India, BBC Media Action positioning has been strongly inspired by sales and marketing techniques. In Delhi, the foundation explains the vision of the Motech project in Bihar: 'How we position this is that like somebody has to go and sale a shampoo, we have to go and sale behaviors, that is our job, and it is very important for us to be good salespersons, to convince people to take up something, including behaviors' 21 . Kilkari (one of the three Motech applications in India) represents one of the products of the Motech range: 'Since Kilkari is directly targeted at the beneficiary, it was marketed like a product. We did a mid-media campaign to advertise it, we trained frontline workers about that and gave them sales card to sell Kilkari. Every time they sell Kilkari they project was deployed in Bihar; Kilkari's 'trade representatives' are community health workers who receive incentives if they succeed in selling the service 23 . Kilkari's goal, it may be recalled, is to convey health messages to families in rural Bihar to improve maternal health. Enrolment to Kilkari happened through promotional actions conducted by community health workers that are paid by the government of India. For this enrolment the BBC used a 'sales cycle approach' that health workers had to implement to convince women to buy the mobile service (that costs one rupee per message):

'The Frontline workers were trained on a sale cycle approach. It's like a salesman, first you have to identify a need, then you have to propose a solution to it, and then you have to make the family commit to that solution and then you have to follow up from time to time' 24 .

Several BBC employees repeatedly explained how crucial the 'sales pitch' was for the project: 'Sales pitch is also a very important part of Kilkari. When FLW approach a beneficiary the first time for pitching the service, the introduction of the service and the pitch she makes is a very critical factor. It's the only time when the beneficiary gets to know about the service or understand its relevance and benefits' 25 . In that line, health workers were trained and encouraged to use these sales techniques during home visits under the close supervision of a local BBC employee, the 'district marketing officer'. The health workers are thus truly transformed into local sales representatives and at the same time accused of not doing this marketing venture properly out of greed: 'Frontline workers receive incentives if they are subscribing beneficiaries. Because of this financial interest, they know that if they say it's a paid service, maybe the beneficiary would refuse to subscribe, so they will underplay this' 26 .

The Motech project in India uses traditional sales and marketing techniques imported from the commercial sector. Kilkari is sold as a product whose promotion campaign has gone through several channels to reach multiple consumer segments, which the BBC foundation calls a '360° approach', a magic formula repeated by every BBC employee from Delhi to Samastipur: 'We use a 360° approach. We use multiple exposures to the same message. The 23 Community health workers received 10 rupees of mobile phone credit on their mobile account for each woman who subscribed to Kilkari and then listened to 4 messages and 20 rupees for 8 messages. 24 Interview with K, BBC, Patna, September 2015. 25 Interview with A., BBC, Delhi, September 2015. 26 Interview with B., BBC, Delhi, September 2015. beneficiary being at the centre of the whole approach'27 . If these sales techniques constitute instruments for the commercial framing of this global health program, the positioning of Motech's stakeholders, their competitive relations, and the defence of their own interests strengthen the commercial dimension of this mHealth project.

'Open source' and property rights

In a highly competitive global environment where market power is built on ever more 'commercial inventiveness' and new products, intellectual property is a major economic and strategic weapon for businesses. In the field of health, the defence of intellectual property rights was particularly highlighted for its deleterious role in access to essential medicines in developing countries (Kapczynski and Krikorian 2010). It is interesting to note that in the mid-1990s at the time of the negotiations on the Agreement on Trade-Related Aspects of Intellectual Property Rights (TRIPS), Microsoft and other IT companies played an important role in pushing for a strengthening of intellectual property laws (Global Health Watch 2008).

The Gates Foundation fits well into this 'microsoftian' legacy, as clarified by Erik Iverson, from the global Health program of the Foundation: 'we absolutely respect intellectual property rights. We recognize their importance and we certainly recognize the importance of companies and their involvement in developing products and having them commercialized both in developed and developing countries'28 . Motech is therefore in line with this approach of defending the property rights of each of its private contributors. But Motech's ownership does not translate into traditional patents or evident intellectual property rights; it relies on a seemingly open-source solution that is locked in reality.

The 'Motech platform,' or 'Motech suite' as it is called by its designers, brings together the different software necessary to operate the applications that constitute Motech Ghana and Motech India. The questions surrounding the ownership and rights of use of this platform call for contrasting answers. According to the Grameen Foundation, there is no question of property rights since Motech is an open-source platform and therefore free to be used and associated with the software, it remains as impenetrable as a proprietary version and constitutes, in that way, a commercial asset.

According to several interviewees, Motech allowed the Grameen Foundation to establish a new legitimacy in the field of ICT for development and health, but also to deploy a team in a 'new' geographical area: 'They were willing to take on a challenge with health, because they were known for other things, but health was a rather new area, which was introduced to them…. Grameen foundation wasn't established in Ghana; they didn't have any presence in Ghana before Motech'31 . Through Motech, the Grameen Foundation has established itself in Ghana and is now selling projects for West Africa from its Ghana headquarters. It has legitimized itself in an area (West Africa) and a sector (mHealth) far from its usual activities of microcredit and banking solutions, activities that it has not, however, lost sight of. Indeed, the Foundation also tests, through Motech, the connection between information service and

Commercial interests and untapped markets

The commercial interests of mHealth are multiple and vary according to the players involved.

ICT Foundations seek to sell their expertise to customize the mobile platforms or content disseminated on these devices. Through mHealth, mobile operators are looking to sell more airtime or over-charged calls. Each of these players has a particular expertise; a service to sell that will make it more innovative or more 'competitive'. Three of Motech's key players -MTN, Grameen, and BBC foundations-defend market interests, rights, and forms of ownership over Motech while enjoying a non-profit status.

Mobile operators like MTN are interested in mHealth for fairly clear reasons, as one Grameen employee in Ghana explained: « Telcos get reputation, easy client acquisition and increased airtime use thanks to Mobile Midwife (Motech) » (ITW with G., Grameen, Accra, 07/14). Mobile operators provide access to the mobile network, and their profits are proportional to their weight in the market. Increasing the number of its customers or the number of paid services per client is a central motivation for involvement in mHealth projects for them. They are essential to access the network and sometimes condition the devices and their viability, in particular because of the connectivity costs they charge to the projects' implementers. This involvement of mobile operators in mHealth is spreading in the global South and these devices become a new field of competition for them. Driven by the prospect of an imminent saturation of the mobile market, each operator is seeking to attract and keep customers with new mobile services, charging more and more for one minute of communication. Indeed, MTN -the market leader in Ghana -is not the only one to sell mHealth devices like Motech. Other mobile operators based in Ghana have similar dynamics.

Vodafone is financing a mobile health information line accessible only by its subscribers; Airtel launched a mobile health insurance service and Tigo a maternal mHealth project during our fieldwork in 2014. All of these operators communicate on the 'social power' of mobile phones, like the director of corporate social responsibility (CSR) of one of them: 'We believe so much in social digital, that's why we are diversifying now. You have many people using mobile phones now, so you also want to come up with new products that people can benefit from as well, as a way of giving back to society. Instead of going to the hospital to line up for hours to access service, it becomes easier if somebody can just pick up the phone and have a voice on the line telling you: if you have an headache, press 1 to speak to somebody, or an asthmatic attack press 2, then it becomes easier for people to get first aid treatment before going to the hospital. These are some of the thing we think mobile can solve. Those services will be only for our users. It's service based on short codes, if you don't use our network you cannot use the service. These short codes come with revenue shares.' 32 This quote illustrates the spirit behind involvement of mobile operators in mHealth: a narrow vision of the use of technology to meet health needs, associated with the revenue prospects generated by this new service. The commercialization of one of the Motech app in Ghana shows the direct link between the philanthropic activities of the MTN Foundation and the economic strategies of the mobile enterprise. All the mobile operators met during this research use their foundation or CSR strategy to test mHealth products that they market shortly thereafter.

Mobile operators are not the only stakeholders wanting to develop the business of mHealth.

Motech's philanthropic foundations, whether BBC or Grameen, also defend their interests, offer services, and strengthen their expertise with a project like Motech. We have seen it with Grameen foundation already but BBC Foundation also defends its expertise and added value on the Indian versions of Motech. As explained at the beginning of this article, it has developed and restructured considerably, thanks to the grants received from the Gates Foundation for the project in Bihar; its financial balance is in fact, conditioned by donations from Gates (BMGF). The national launch of Motech in India gives to its activities a national scope and a connection with the central government that it never had before, but still completely dependent on the Gates Foundation as one official from the Central Health Ministry confirms: 'BMGF brought in BBC Media Action, BMGF said that they are good at the communication part. But we approach only BMGF' 33 . The Foundation nevertheless seeks to diversify its clients and funders by building on the mHealth devices deployed in Bihar. The BBC Foundation systematically emphasizes its expertise in terms of communication, its role in adapting messages to the Indian context, and its link with the central Ministry of Health: 'the Ministry of Health and Family Welfare in India has delivered maternal and child health mobile phone content developed by BBC Media Action to more than 260,000 families' 34 . As stated here, the BBC Foundation has developed the content and media for the three Motech While evaluating their investments and potential image and economic spin-offs, these new mHealth entrepreneurs say they can leave a positive impact and improve the lives of people in the poorest countries, an approach that Peter Redfield describes as 'gadget capitalism with a human face' (Redfield 2015, 78). The term 'gadget' should be taken seriously, when one looks at mHealth devices. While mobile applications leave no material traces, no physical infrastructure, no specialized skills or knowledge in the countries where they are deployed, they nevertheless offer a new mercantile approach to care and health administration that leaves traces. Favouring interests of the Northern-based digital industry, they contribute to the commodification of health in the global South and to the creation of new private digital health markets geared toward the poor.

  14 . Based in London with offices in Hyderabad, Atlanta and Dubai, IMImobile is a private company listed on the London stock exchange, which employs 700 people worldwide. IMImobile is helping to deploy a new version of Motech platform, able to manage the mass of data, the different IVR systems in local languages, the connectivity challenges with the different mobile operators required by the national extension of Motech in India. Even if it didn't receive any direct official grant from the Gates Foundation, IMImobile is a major partner of the program in India. The Gates, BBC and Grameen Foundations, IMI Mobile, and Dimagi are all private entities from the global North. They constitute major stakeholders of the project and promote through this device the ability of mobile technologies to solve health and social problems and the efficacy of business solutions to generate income and economic growth in the global South. They highlight the fact that Gates foundation does not direct its funding towards businesses or players from the global South. In 2009, David McCoy and his colleagues studied Gates' overall investment in 'global health' and showed that out of the 659 grants awarded; only 5% went to organizations in 'low or middle income' countries (McCoy et al., 2009). Moreover, if the majority of technical subcontractors are also private companies from the global North it means that local small or medium digital companies are not benefiting from this manna either financially of in terms of technical knowledge and know-how. Investments in telecommunications by global North actors in the global South are seen as contributions to help the development of poor countries, even if these strategies by the richest businesses and individuals necessarily lead to a reduction of resources for public services and hence for public health systems. A recent report of the United Nations Conference on

  get 10 rupees balance on their phone' 22 . BBC employees working for Kilkari are called 'state marketing officer' in Patna and 'district marketing officer' in each of the districts where the 21 Interview with M., BBC, Delhi, March 2015. 22 Interview with A., BBC, Delhi, March 2015.

  accessed, as explained by Grameen's employee: 'If you want to use Motech, it's open source, you just go on the internet, you download it and look at the code and see what it does, if you need any help then you come to us' 29 . But for the Ghanaian Ministry of Health, the Grameen Foundation is the sole owner of the platform: 'Motech platform is owned by the Grameen foundation. The data belongs to the Grameen foundation right now and the platform is used by them for other countries such as India' 30 . If Motech is open-source software downloadable by everyone, particular skills and specific technical knowledge are essential to be able to use the html code and the various components of Motech, which is different from acquiring property rights. While open-source software is often put forward as a tool to compensate for unequal access to software, it remains a technical artefact that is difficult to transfer (Sim and Philip 2008). There is therefore no 'owner' of Motech with an established copyright, but in fact only the Grameen Foundation can use the platform. The two other Ghanaian mHealth programs-No Yawa and CCH-that used Motech in 2014 were also entirely managed by the Grameen Foundation. The other partners who carry these projects-DKT International, Marie Stopes, Concern Worldwidedo not have access to the platform and the associated databases either. The Indian Ministry of Health and BBC Media Action, which manage projects using Motech in India, also have to go through the Grameen Foundation for any use or evolution of the platform. When the various technical dysfunctions of Motech are raised with Grameen's technical team, these are most of the time justified by the difficulty in maintaining the platform due to the turnover of the technical team and the difficulties of learning how to handle the code of Motech. Thus, the Grameen Foundation recognizes the difficulties of using the open-source code and has put in place training schemes for its incoming teams, but has not rolled out this transfer of skills for the other partners in the project-for example, to train the technicians of the Ghanaian or Indian ministries of health. A 'technical skills deficit' to manage Motech is thus put forward for all other Motech partners. It is in fact a form of protectionism from Grameen which has an expertise to sell and wishes to remain in this particular 'business'. Therefore, in the case of Motech, open-source code is neither a guarantee of accessibility nor a guarantee of technological transfer. Without transfer of knowledge and know-how 29 Interview with A., Grameen F., Accra, July 2014. 30 Interview with M., GHS, Accra, May 2014.

  mobile banking on the same platform, since the Indian version of Motech manages transfers of phone credit from 'clients' to Motech platform and from Motech platform to health workers. Through the Ghanaian and Indian experimentations, Grameen has been able to develop a technical solution that can cover a very wide spectrum of health issues, as well as manage information and money flows anywhere in the world. As explained earlier, if the open-source license of Motech Suite is accessible to everyone, using the platform requires technical skills and knowledge that are difficult to transfer without Grameen's agreement and involvement. In fact, only the Grameen Foundation can use the Motech platform. It represents a central technical expert of Motech, and in Accra, Delhi or Patna, any use of the Motech platform must first pass through them. The Grameen Foundation has therefore become a key player in the enterprise, and its services are not free.

32

  Interview with R, Telco X, Accra, June 2014. 33 Interview with A., Ministry of Health, Delhi, February 2015. 34 Declaration from BBC media action website :http://www.bbc.co.uk/blogs/bbcmediaaction/entries/2dfa07e0-7471-3616-b153-478ef3c7fc16 consulted on 02/03/15 Indeed, if Motech was developed within the framework of a PPP, it gives ownership rights only to private actors of the global North and not to the public services and governments of the global South that contributed to its implementation. Furthermore, it demonstrates that the market dimension of mHealth cannot be beneficial to the global South if the stakeholders of the global North-who conceptualize and develop these interventions -nurture protectionist and competitive strategies.

We used two-steps coding method with different sets of nodes: a first round of descriptive thematic coding and then a second round of analytic coding related to our research questions.

BBC Media Action annual reports 2010-2011; 2011-2012 ; 2012-2013 ; 2013-2014

Interview with H, BBC, Delhi, August 2015.

Interview with M., GHS, Accra, May 2014.

Interview with K., BBC, Patna, September 2015.

Excerpt from « Interview: Erik Iverson of the Bill & Melinda Gates Foundation| Patents & Patent Law ». IPWatchdog.com | Patents & Patent Law, 28 Februrary 2011.

Interview with M., GHS, Accra, May 2014.

Marine Al Dahdah is a sociologist and a postdoctoral fellow at IFRIS-Cermes3 (Paris

applications in India, a circumstance that allows it to claim ownership of Motech in India.

Recently, the BBC launched two other mHealth programs in Odisha with the financial support of its first donor, DFID, based on the Bihar experiment.

The ownership issues are very present in the Motech device; each partner defends its own interests and the possibility of making profit through this initial investment. As we explained, if stakeholders do not brand patents related to Motech, they specialize their services and products to become key players of the mHealth market in developing countries. Knowing that each and every component of Motech was developed by a private actor from the global North, the property claims and interests defended here are not to the benefit of the global South. Few years after our fieldwork, Motech as mostly merged into the 'Commcare' platform owned by the American company Dimagi, becoming a product of the US digital industry ; it is the most used mHealth platform to tackle community health issues in the global South (Johns Hopkins University, 2016). This mercantile approach to development and the idea that business is the ultimate solution to tackle poverty in the global South continues to take hold and has become normalized. For example, the third United Nations conference on 'Financing for Development' in July 2015 in Addis Ababa promotes the use of market solutions and business principles to finance development (UN 2015); it is therefore an accepted evolution of development policies and even an asserted will of some international agencies.

CONCLUSION

This article discussed the philanthropic and commercial dimension of mHealth. While mHealth exists through philanthropic donations, this does not prevent its inclusion in commercial logics as a marketable digital health product. In this way, this article illustrates the same kind of a philanthrocapitalist dynamic that has already been established by researchers who have looked at PPP with pharmaceutical companies. Nevertheless, even if Motech is part of the growing wave of international health PPPs, philanthropic foundations from the digital sector have particularities. Indeed, contrary to more traditional philanthropists digital philanthropists don't invest in public or local infrastructures in the global South. They gear the majority of their investments towards private foundations and for profit companies that will favour the interest of the global North digital industry and even help them to secure new digital markets in the global South.


Mateusz Skomra

Optimal bounds for bit-sizes of stationary distributions in finite Markov chains

An irreducible stochastic matrix with rational entries has a stationary distribution given by a vector of rational numbers. We give an upper bound on the lowest common denominator of the entries of this vector. Bounds of this kind are used to study the complexity of algorithms for solving stochastic mean payoff games. They are usually derived using the Hadamard inequality, but this leads to suboptimal results. We replace the Hadamard inequality with the Markov chain tree formula in order to obtain optimal bounds. We also adapt our approach to obtain bounds on the absorption probabilities of finite Markov chains and on the gains and bias vectors of Markov chains with rewards.

Introduction

In this note, we study the following problem. Suppose that P ∈ [0, 1] n×n is an irreducible stochastic matrix whose entries are rational numbers with a common denominator M ∈ N. Then, the stationary distribution π ∈ ]0, 1] n of P is a vector with rational entries. Our aim is to obtain an optimal upper bound on the lowest common denominator of the numbers (π i ) n i=1 , which bounds the number of bits needed to encode π.

1.1. Context and motivation. Our main motivation to study the problem stated above comes from the area of stochastic mean payoff games, which form a generalization of finite Markov decision processes. A stochastic mean payoff game is a zero-sum game played by two players (Min and Max) who move a token along the edges of a finite directed graph G = (V, E). Some vertices of the graph are controlled by player Min, some are controlled by player Max, and some are controlled by nature, which moves the token according to some fixed probability distribution. Furthermore, each vertex v of the graph is equipped with an integer payoff r v ∈ Z. The players are supposed to play according to positional strategies, i.e., their decisions depend only on the current position of the token. In particular, if the token lands twice on the same vertex controlled by one of the two players, then this player makes the same decision on both occasions. As a consequence, once the strategies of the players are fixed, the movement of the token is described by a Markov chain (X 0 , X 1 , . . . ) on V , where X 0 is the starting position of the token, and the randomness of this process comes only from the random decisions made by the nature. The payoff of player Max is given by the average reward criterion lim

N →∞ 1 N E(r X 0 + • • • + r X N ) .
1

Player Max aims to maximize this quantity, while player Min wants to minimize it. It is known that stochastic mean payoff games have always have optimal strategies [START_REF] Liggett | Stochastic games with perfect information and time average payoff[END_REF]. In other words, there exists a vector χ ∈ R V , known as the value of the game, such that player Max has a strategy that guarantees that the payoff is not smaller than χ v for all initial states v. Likewise, player Min has a strategy that guarantees that the payoff is not greater than χ v . In particular, if both player play optimally, then the final payoff is equal to χ v . Stochastic mean payoff games attracted a significant interest in the computer science literature thanks to their uncertain complexity status. Even though optimal strategies exist, finding them algorithmically is a nontrivial task. In particular, it is not known if these strategies can be found in polynomial time and this problem has been open for 30 years, even in some restrictive cases (deterministic mean payoff games and parity games) [START_REF] Condon | The complexity of stochastic games[END_REF][START_REF] Gurvich | Cyclic games and finding minimax mean cycles in digraphs[END_REF][START_REF] Emerson | Tree automata, mu-calculus and determinacy[END_REF]. We refer the reader to [START_REF] Andersson | The complexity of solving stochastic games on graphs[END_REF][START_REF] Zwick | The complexity of mean payoff games on graphs[END_REF][START_REF] Comin | Improved pseudo-polynomial bound for the value problems and optimal strategy synthesis in mean payoff games[END_REF][START_REF] Ibsen-Jensen | Solving simple stochastic games with few coin toss positions[END_REF][START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF][START_REF] Halman | Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems[END_REF][START_REF] Calude | Deciding parity games in quasipolynomial time[END_REF][START_REF] Czerwiński | Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games[END_REF][START_REF] Filar | Competitive Markov Decision Processes[END_REF] for more information about mean payoff games and the related algorithmic issues. We also note that the one-player variant of these games is equivalent to Markov decision processes with average reward criterion, studied for instance in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF].

Numerous algorithms for solving stochastic mean payoff games that are proposed in the literature, such as the value iteration algorithms or the pumping algorithm, approximate the value χ without knowing the optimal strategies of the game. When the value is approximated to a sufficient precision, a rounding procedure is used to find χ exactly. We refer to [START_REF] Condon | The complexity of stochastic games[END_REF][START_REF] Ibsen-Jensen | Solving simple stochastic games with few coin toss positions[END_REF][START_REF] Auger | Finding optimal strategies of almost acyclic simple stochastic games[END_REF][START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF] for examples of such algorithms. In order to use a rounding procedure, one needs to have a bound on the precision needed to recover χ. This is done by bounding the denominators of χ. Such a bound can be obtained using the Hadamard inequality, and this approach is used in [START_REF] Condon | The complexity of stochastic games[END_REF][START_REF] Auger | Finding optimal strategies of almost acyclic simple stochastic games[END_REF][START_REF] Akian | Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information[END_REF][START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF], but it leads to suboptimal results in many cases of interest. In this note, we propose to use a more combinatorial approach, based on the Markov chain tree formula [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF]Lemma 3.2], to obtain optimized bounds. As noted above, χ is the payoff of player Max obtained when both players play optimally. Let (X 0 , X 1 , . . . ) be the Markov chain obtained under the optimal strategies and let P be its transition matrix. Our basic case of interest arises when P is irreducible. Then, [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Appendix A.4] shows that χ does not depend on the initial state, χ = η(1, 1, . . . , 1), and η = r T π, where π is the stationary distribution of P . Thus, the denominator of η is not greater than the lowest common denominator of (π v ) v∈V , which leads to the problem stated in the first paragraph of this note.

Main results.

Throughout this note, we use the following notation. We denote [m] = {1, . . . , m} for m ∈ N. Furthermore, let P ∈ [0, 1] n be a stochastic matrix with rational entries and let X := (X 0 , X 1 , . . . ) be a Markov chain on the state space V := [n] with transition matrix P . In general, we do not suppose that P is irreducible, since most of our results do not require this assumption. For every i ∈ [n], let M i be the lowest common denominator of the entries in the ith row of P , and let M be the lowest common denominator of all the entries of P . We also put

D := M 1 M 2 . . . M n .
Moreover, we denote by C 1 , . . . , C p ⊂ [n] the recurrent classes of X and, for all ∈ [p], we denote by π ( ) ∈ ]0, 1] C the stationary distribution on C . Furthermore, let r ∈ Z n be a vector of integer numbers and let χ ∈ R n be the gain vector defined as ∀i, χ i := lim

N →∞ 1 N E(r X 0 + • • • + r X N | X 0 = i) .
We note that χ is well defined and given by ∀i,

χ i = p =1 ψ(i, C )η ( ) , (1)
where ψ(i, C ) denotes the probability that the Markov chain starting at i reaches C , and η ( ) := j∈C r j π ( ) j for all ∈ [p]. The formula (1) follows from the ergodic theorem of finite Markov chains, see [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Appendix A.4] and [13, Part I, §6- §9] for detailed information. Our main result is the following theorem for irreducible matrices and its corollary, which holds even if P is not irreducible. Theorem 1.1. Suppose that P is irreducible and let π ∈ ]0, 1] n denote its stationary distribution. Then, π is a vector of rational numbers whose lowest common denominator is not greater than min{nD, nM n-1 }.

Corollary 1.2. Suppose that χ = η(1, 1, . . . , 1) for some η ∈ R. Then, η is a rational number with denominator not greater than min{nD, nM n-1 }.

Before discussing these results, observe that M D M k , where k is the number of rows of P that have at least two nonzero entries, k := {i ∈ [n] : ∃j, 0 < P ij < 1}. In particular, we have the inequality min{nD, nM n-1 } nM min{k,n-1} .

(

) 2
As noted above, our proof of Theorem 1.1 relies on a combinatorial formula for stationary distributions, known as the Markov chain tree formula [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF]Lemma 3.2]. By comparison, [START_REF] Akian | Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information[END_REF]Lemma 4.10] uses the Hadamard inequality to obtain a bound n n/2 M n for the same problem. A more precise application of the Hadamard inequality is used in [START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF]Lemma 6] to obtain a bound of the form kn(2M ) k+1 . The inequality [START_REF] Akian | Ergodicity conditions for zero-sum games[END_REF] shows that our estimate is better than both of these bounds. Even more, in Proposition 3.2 we show that our bound is essentially optimal, in the sense that it cannot be improved even by a multiplicative constant. The proof of Proposition 3.2 also shows that this bound remains optimal even if we only want to bound the denominators of π i separately. We also note that the interest of having bounds that depend on k is that these types of bounds may be used for stochastic mean payoff games with bounded number of states controlled by nature, see [START_REF] Gimbert | Simple stochastic games with few random vertices are easy to solve[END_REF][START_REF] Ibsen-Jensen | Solving simple stochastic games with few coin toss positions[END_REF][START_REF] Auger | Finding optimal strategies of almost acyclic simple stochastic games[END_REF][START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF] for more discussion. Furthermore, we point out that [START_REF] Akian | Solving multichain stochastic games with mean payoff by policy iteration[END_REF] shows that the assumption of Corollary 1.2 is satisfied if X is irreducible or has only one recurrent class, but it may also be satisfied even if X has multiple recurrent classes. We refer to [START_REF] Akian | Ergodicity conditions for zero-sum games[END_REF][START_REF] Boros | A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions[END_REF] for conditions that ensure that a stochastic mean payoff game has a value that does not depend on the initial state.

Our next result is especially useful in the situation in which X has an absorbing state, P jj = 1, and we put r j := 1 and r i := 0 for all i = j.

In this case, [START_REF] Akian | Solving multichain stochastic games with mean payoff by policy iteration[END_REF] shows that the gain χ i is equal to the probability that the Markov chain starting at i reaches j. This situation arises in simple stochastic games [START_REF] Condon | The complexity of stochastic games[END_REF] and some of its generalizations [START_REF] Gimbert | Simple stochastic games with few random vertices are easy to solve[END_REF][START_REF] Auger | Finding optimal strategies of almost acyclic simple stochastic games[END_REF][START_REF] Auger | A generic strategy iteration method for simple stochastic games[END_REF]. In particular, in order to bound the denominator of χ i , we want to bound the denominators of absorption probabilities (which are rational numbers). To do so, we use an adaptation of the Markov chain tree formula to absorption probabilities, following the approach presented in [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF]. In order to state out estimate, let T ⊂ [n] denote the set of transient states of the Markov chain X and put D T := i∈T M i . Our approach gives the following result.

Theorem 1.3. The numbers ψ(i, C ) i∈[n], ∈[p]
are rational and their lowest common denominator is not greater that min{D T , M n-2 }.

As previously, we have the inequality D T M k T , where k T k denotes the number of rows of P that have at least two nonzero entries and represent transient states of the Markov chain, i.e.,

k T = {i ∈ [n] : i is transient and there exists j ∈ [n] such that 0 < P ij < 1} .
In particular, we have

min{D T , M n-2 } M min{k T ,n-2} (3)
and this bound improves the bounds obtained in the literature using the Hadamard inequality [START_REF] Condon | The complexity of stochastic games[END_REF][START_REF] Auger | Finding optimal strategies of almost acyclic simple stochastic games[END_REF]. Furthermore, this bound is tight as shown in Example 3.5. Combining Corollary 1.2, Theorem 1.3, and (1), we obtain the following estimate on the gain vector in general chains.

Corollary 1.4. The numbers (χ i ) i∈ [n] are rational and their lowest common denominator is not greater than 3 s/2 D, where s denotes the number of recurrent states of a Markov chain with transition matrix P .

The main difference between the bounds of Corollary 1.2 and Corollary 1.4 is that the latter bound is exponential in s. The example presented in [START_REF] Boros | On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness[END_REF] shows that this is unavoidable in general chains even if k = 1.

To state our final result, we recall the notion of a bias vector. Given P and r, [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Theorem 8.2.6] shows that the gain χ can be found by solving the system of equalities

P χ = χ P u = χ + u -r (4)
in variables (χ, u) ∈ R 2n . More precisely, (4) has a solution and any such solution (χ , u) satisfies χ = χ. If (χ, u) is a solution of ( 4), then we say that u is a bias vector. In general, a bias vector is not unique, even up to an additive constant. Bias vectors play an important role in the policy iteration algorithms for Markov decision processes [29, Chapter 9] and for stochastic mean payoff games [START_REF] Akian | Solving multichain stochastic games with mean payoff by policy iteration[END_REF]. Moreover, in a recent work, Allamigeon, Gaubert, Katz, and Skomra proposed a condition number for stochastic mean payoff games that governs the complexity of the value iteration algorithm [START_REF] Allamigeon | Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming[END_REF][START_REF] Allamigeon | Universal complexity bounds based on value iteration and application to entropy games[END_REF]. This condition number depends on the quantity inf u u H , where the infimum goes over all bias vectors of the Shapley operator associated with a stochastic mean payoff game, and • H denotes the Hilbert seminorm,

u H := max i u i -min i u i . Since u H 2 u ∞ ,
one can use the supremum norm to bound inf u u H . The complexity estimates on value iteration obtained in [START_REF] Allamigeon | Universal complexity bounds based on value iteration and application to entropy games[END_REF] rely on Theorem 1.1 and on the following result. Theorem 1.5. Suppose that u ∈ R n is a bias vector of (r, P ). We have the following estimates: i) if for every ∈ [p] there exists i ∈ C such that

u i = 0, then u ∞ 2 r ∞ n min{D, M n-1 }; ii) if i∈C u i π ( ) i = 0 for all ∈ [p], then u ∞ 4 r ∞ n min{D, M n-1 }.
The discussion in [29, Section 8.2.3] implies that bias vectors of both kinds exist for any pair (r, P ). Furthermore, these types of bias vectors are particularly useful in the policy iteration algorithms for Markov decision processes [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Section 9.2].

A preliminary version of the results presented in this note appeared in the PhD thesis of the author [START_REF] Skomra | Tropical spectrahedra: Application to semidefinite programming and mean payoff games[END_REF]Chapter 8]. We note that Theorem 1.3, which was only briefly mentioned in [START_REF] Skomra | Tropical spectrahedra: Application to semidefinite programming and mean payoff games[END_REF]Remark 8.46], has since been obtained independently by Auger, Badin de Montjoye, and Strozecki [7, Theorem 23], using a similar technique (the proof in [START_REF] Auger | A generic strategy iteration method for simple stochastic games[END_REF] is based on the matrix tree theorem).

1.3. Organization of the paper. The rest of the paper is organized as follows. In Section 2.1 we present the necessary notions on directed trees and forests, which are used in the Markov chain tree formula. In Section 2.2 we present this formula and its adaptation to absorption probabilities. Section 3.1 contains the proofs of Theorems 1.1 and 1.3 and their corollaries. Finally, we present the proof of Theorem 1.5 in Section 3.2.

Preliminaries

2.1. Rooted trees and forests. Let G = (V, E) be a directed graph. In this paper, we allow a directed graph to have loops, but not multiple edges, i.e., we suppose that E is a subset of {(u, v) : u, v ∈ V }. If E ⊂ E is a subset of edges, then we denote by G(E ) = (V, E ) the subgraph that consists of all the vertices of G, but the edges taken only from E . Definition 2.1. Let E ⊂ E. We say that the graph G(E ) is a rooted forest if it does not have any directed cycles and every vertex of G(E ) has at most one outgoing edge. We say that a vertex v ∈ V is a root of G(E ) if it has no outgoing edges. We say that G(E ) is a rooted tree if it is a rooted forest and has exactly one root.

(In Definition 2.1 we use the convention that a loop is a directed cycle, so that a rooted forest does not have any loops.) Figure 1 depicts a rooted forest. Before presenting the relationship between the rooted forests and Markov chains, let us give a few comments about Definition 2.1. First, we point out that a rooted forest is, indeed, a forest, i.e., it does not contain any undirected cycle. This follows from the fact that any undirected cycle that does not come from a directed cycle contains a vertex with two outgoing edges. Second, we note that the number of connected components of a rooted forest is equal to the number of its roots. This follows from the fact that from every vertex there is a unique directed path leading to a root. In particular, a rooted tree has one connected component, i.e., it is a tree. The following remark explains the vocabulary and conventions used in Definition 2.1.

Remark 2.2. Since we suppose that G(E ) contains all the vertices of G, the objects that we are considering are, in fact, spanning rooted forests and trees. Since we never consider forests that are not spanning, we drop the word "spanning" from the definition. We also point out that rooted forests are also called branchings and rooted trees are called arborescences. Furthermore, we note that in our definition, rooted forests are oriented in such a way that every edge points "towards the root." However, the opposite convention is commonly used in the literature, cf. [START_REF] Edmonds | Optimum branchings[END_REF] or [START_REF] Schrijver | Combinatorial Optimization. Polyhedra and Efficiency[END_REF]Section 3.2].

The choice of orientation that we made in Definition 2.1 is justified by the fact that the orientation "towards the root" corresponds to the direction of transition between states in the Markov chains that we discuss in Section 2.2.

Combinatorial formulas for Markov chains.

As in the introduction, we denote by X := (X 0 , X

∀v ∈ W, P(∃ , X / ∈ W | X 0 = v) > 0 .
We note that the definition above does not imply that the chain cannot come back to W after leaving it. In particular, W can contain some recurrent states, but not a whole recurrent class. This also implies that the condition of Definition 2.3 can be replaced by a stronger one-if W is open and v ∈ W , then the chain starting at v will leave W almost surely.

If W ⊂ V is open, we denote by τ W := inf{ 1 : X / ∈ W } the moment when the chain leaves W for the first time. Furthermore, for every v, w ∈ W we let

ζ W vw := E τ W -1 =0 1 {X =w} X 0 = v
be the expected number of visits in w before leaving W , provided that the chain starts at v. The following result gives a formula for computing ζ W vw .

Lemma 2.4 ([25, Theorem 3.5.4(1)]). Let P W ×W denote the submatrix of P formed by the rows and columns from W . Then, the matrix (I -P ) is invertible and (I -P ) -1 vw = ζ W vw for all v, w ∈ W . An alternative combinatorial formula for ζ W vw is given by Catoni in [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF], where it is used to derive the Markov chain tree formula. In order to introduce it, we recall that a finite Markov chain is naturally associated with a directed graph representing its transitions. More precisely, we define the graph G = (V, E) by the condition (v, w) ∈ E ⇐⇒ P vw > 0. We can consider that this graph is weighted, with weights p(e) that correspond to the probabilities of transitions, i.e., if e = (v, w) ∈ E, then p(e) := P vw . We also extend this definition to subsets of edges by taking the product. More precisely, if E ⊂ E, then we define the weight of E as the product of the weights of its elements,

p(E ) := e∈E p(e) = (v,w)∈E P vw .
The formulas that we present below consider only subsets of edges that give rise to rooted forests and trees. To this end, we denote

F(R) := {E ⊂ E : G(E ) is a rooted forest
and its set of roots is equal to R} .

It is also useful to consider the forests that contain a directed path between two fixed vertices. We denote

F vw (R) := {E ∈ F(R) : G(E ) contains a directed path from v to w} .
We use the convention that if v = w, then F vw (R) := F(R). If R = {w } is a singleton, then we use the notation F(w ) and F vw (w ) instead of F({w }), F vw ({w }). In this way, we can think of F(w ) as the set of rooted trees whose root is w .

Lemma 2.5 ([12, Lemma 3.1]). Suppose that W ⊂ V is open and denote

S := V \ W . Then, for every v, w ∈ W we have ζ W vw = E ∈Fvw(S∪{w}) p(E ) E ∈F (S) p(E ) -1 .
Remark 2.6. We note that Lemma 2.5 is stated in [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF] only for nontrivial subsets of irreducible chains, but the proof presented in [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF] applies to arbitrary open sets of finite Markov chains. Lemma 2.5 leads to the following two corollaries. The first one characterizes the stationary distributions of irreducible Markov chains. This corollary is known as the Markov chain tree formula, and was discovered by numerous authors [START_REF] Freidlin | Random Perturbations of Dynamical Systems[END_REF][START_REF] Kohler | The frequency of cyclic processes in biological multistate systems[END_REF][START_REF] Shubert | A flow-graph formula for the stationary distribution of a Markov chain[END_REF][START_REF] Solberg | A graph theoretic formula for the steady state distribution of finite Markov processes[END_REF], see also [START_REF] Pitman | Tree formulas, mean first passage times and Kemeny's constant of a Markov chain[END_REF] for more information. The second one characterizes the probabilities of absorption in different recurrent classes. We give the proof of the second corollary, since it is not stated in [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF]. Corollary 2.7 (Markov chain tree formula, [START_REF] Catoni | Simulated annealing algorithms and Markov chains with rare transitions[END_REF]Lemma 3.2]). Suppose that the Markov chain is irreducible. Then, its stationary distribution π ∈ ]0, 1] V is given by the formula

∀w ∈ V, π w = E ∈F (w) p(E ) v∈V E ∈F (v) p(E ) -1 .
Corollary 2.8. Let S ⊂ V denote the set of all recurrent states of the Markov chain and let C ⊂ S be a recurrent class. Suppose that v ∈ V is a transient state and let ψ(v, C) be the probability that the chain starting at v reaches C. Then, we have the equality

ψ(v, C) = w∈C E ∈Fvw(S) p(E ) E ∈F (S) p(E ) -1 .
Proof. Let W := V \S denote the set of transient states and fix w ∈ C. Then, [START_REF] Kemeny | Finite Markov Chains[END_REF]Theorem 3.5.4] implies that the probability that the chain starting at v ∈ W goes to w when it leaves W is equal to

w ∈W P w w ζ W vw .
Moreover, by Lemma 2.5 we have

w ∈W P w w ζ W vw = w ∈W P w w E ∈F vw (S∪{w }) p(E ) E ∈F (S) p(E ) -1 = w ∈W E ∈F vw (S∪{w }) P w w p(E ) E ∈F (S)
p(E )

-1 = E ∈Fvw(S) p(E ) E ∈F (S) p(E ) -1
.

We obtain the claimed result by summing over w ∈ C.

Proofs of the main theorems

In this section, we give the proofs of our main theorems. Section 3.1 contains the proofs of Theorems 1.1 and 1.3 and Section 3.2 contains the proof of Theorem 1.5.

Stationary distributions and absorption probabilities.

The proof of our main theorem for irreducible chains relies on the following observation.

Lemma 3.1. Let Q ∈ {D, M n-1 } and suppose that E ⊂ E is such that G(E ) is a rooted tree. Then, p(E )Q is a natural number.
Proof. Since G(E ) has exactly n -1 edges, p(E ) is a product of n -1 rational numbers with common denominator M . Hence, p(E )M n-1 is a natural number. Moreover, since every vertex of G(E ) has at most one outgoing edge, the product in p(E ) involves at most one number taken from the first row of P , at most one number taken from the second row of P , at most one number taken from the third row of P and so on. Therefore, p(E )D is also a natural number.

1 2 n -1 n p 1 M p n-1 M p 2 M p n-2 M 1 . . . 1 -p 1 M 1 -p 2 M 1 -p n-1 M Figure 2. An irreducible Markov chain from Proposition 3.2.
Proof of Theorem 1.1. Let Q ∈ {D, M n-1 }. By Corollary 2.7, for every w ∈ V we have

π w = Q E ∈F (w) p(E ) Q v∈V E ∈F (v) p(E )
.

By Lemma 3.1, the numerator and the denominator of the above fraction are natural numbers. In particular,

Q v∈V E ∈F (v) p(E )
is a common denominator (π v ) v . Furthermore, note that for every v ∈ V we have

E ∈F (v) p(E ) w =v ( w P ww ) = 1 . (5)
Indeed, w =v ( w P ww ) is the total weight of all graphs G(E ) in which v has no outgoing edges and every other vertex has exactly one outgoing edge. Since every tree rooted at v has these properties, we get [START_REF] Allamigeon | Universal complexity bounds based on value iteration and application to entropy games[END_REF]. Therefore, the lowest common denominator of (π v ) v is not greater than

Q v∈V E ∈F (v) p(E ) nQ .
The next proposition shows that the bound of Theorem 1.1 is optimal for any fixed n. More precisely, let g(n, M ) denote the optimal bound that could be obtained in Theorem 1.1 for any fixed n, M , under the additional assumption that D = M n-1 . Then, we have the following result. Proposition 3.2. For every n 2 we have lim sup

M →+∞ g(n, M ) nM n-1 = 1 .
Proof. We have g(n, M ) nM n-1 by Theorem 1.1. To prove the opposite inequality, fix n 2 and ε > 0. The following construction shows that we can find an arbitrarily large M 1 and an irreducible Markov chain on n states such that the lowest common denominator of (π v ) v is not smaller than (1 -ε)nM n-1 . To do this, let (m 1 , m 2 , . . . ) = (2, 3, 5, . . . ) be the sequence of prime numbers and let δ > 0 be such that ( 1 1+δ ) n-1 1 -ε. For sufficiently large q n we have m n δ(m q !). Take any such q and let M = m q ! + m n , so that M

(1 + δ)m q !. Furthermore, let p 1 = m q ! + m 1 , p 2 = m q ! + m 2 , . . . , p n = m q ! + m n = M . We note that the numbers (p 1 , . . . , p n ) are pairwise coprime. Indeed, if a prime number m divides m q ! + m i and m q ! + m j , then it also divides |m i -m j |. Since |m i -m j | is smaller than m n m q , the number m also divides m q ! and so it divides both m i and m j , which is a contradiction. Consider the irreducible Markov chain shown in Figure 2 and note that this chain satisfies D = M n-1 . Moreover, in this chain every state v ∈ [n] is a root of exactly one rooted tree and the weight of this tree is equal to w =v pw M . Hence, if we denote Q v = p 1 . . . p n /p v for all v, then Corollary 2.7 shows that the stationary distribution of this chain is given by

∀v, π v = Q v w∈V Q w . ( 6
)
We note that the numbers Q v are natural. Even more, the fraction in ( 6) is simple. Indeed, if a prime number m divides Q v , then it divides exactly one of p 1 , . . . , p n because these numbers are pairwise coprime. Suppose that m divides p i . Then, m divides Q w for all w = i and it does not divide Q i .

In particular, m does not divide w∈V Q w , showing that the fraction in ( 6) cannot be simplified. Therefore, the lowest common denominator of (π v ) v is equal to w∈V Q v . Furthermore, we have

w∈V Q w np 1 . . . p n-1 n(m q !) n-1 n( 1 1 + δ ) n-1 M n-1 (1 -ε)nM n-1 .
Remark 3.3. The fact that the fractions in [START_REF] Andersson | The complexity of solving stochastic games on graphs[END_REF] are simple implies that the bound of Theorem 1.1 remains optimal even if one only wants to bound the denominators of π v separately.

The theorem for absorption probabilities follows by a similar argument. The following lemma is analogous to Lemma 3.1. Lemma 3.4. Let Q ∈ {D T , M n-2 } and let S ⊂ V denote the set of recurrent states of X . Suppose that |S| 2 and that E ⊂ E is such that G(E ) is a forrest rooted at S. Then, p(E )Q is a natural number.

Proof. Since |S| 2, the graph G(E ) has at least two roots, and so p(E ) is a product of at most n -2 rational numbers with common denominator M . Thus, p(E )M n-2 is a natural number. Furthermore, p(E ) is a product obtained by taking one number from each row of P that corresponds to a transient state of X . Therefore, p(E )D T is also a natural number.

Proof of Theorem 1.3. Let S ⊂ V denote the set of recurrent states of X . If X has exactly one recurrent state w ∈ V , then ψ(v, {w}) = 1 for all v = w and the claim is trivial. From now on we suppose that |S| 2. Let Q ∈ {D T , M n-2 }. Then, Corollary 2.8 shows that for every v ∈ V we have We now present the proofs of Corollaries 1.2 and 1.4.

ψ(v, C) = Q w∈C E ∈Fvw(S) p(E ) Q E ∈F (S) p(E ) . 1 2 n -2 n n -1 1 M 1 M 1 M 1 M 1 -1 M 1 -1 M 1 -1 M . . .
Proof of Corollary 1.2. Let v ∈ V be a recurrent state of X belonging to some recurrent class C ⊂ V . Then, [START_REF] Akian | Solving multichain stochastic games with mean payoff by policy iteration[END_REF] shows that η = w∈C r w π w , where π ∈ R C is the stationary distribution of C. Hence, by applying Theorem 1.1 to C we get that η is a rational number and that its denominator is not greater than min{nD, nM n-1 }. =0 1 {X =w} denote the number of times the Markov chain visits w before leaving W . Under this notation, we have ζ W vw = E(Z|X 0 = v). Furthermore, let q ∈ [0, 1] denote the probability that the Markov chain starting at w goes back to w before leaving W , i.e., q := P(Z 2|X 0 = w).

Since W is open, there exists a simple path in G that starts in w and ends in some state that is outside W . The probability that the Markov chain starting from w follows this path is not smaller than 1/D W . Therefore, q 1 -D -1 W . Furthermore, note that for all t 1 we have P(Z t|X 0 = v) q t-1 , because in order to achieve Z t the chain starting from v has to reach w and subsequently go back to w at least t -1 times. Thus,

ζ W vw = E(Z|X 0 = v) = ∞ t=1 P(Z t|X 0 = v) ∞ t=1 q t-1 = 1 1 -q D W .
To prove Theorem 1.5, we start with the irreducible case and then move to the general case. Lemma 3.7. Theorem 1.5 is true when P is irreducible.

Proof. We start by proving the case i). Let u ∈ R V be a bias vector such that u n = 0 (the proof if analogous if u v = 0 for some other v ∈ V ). Denote W := V \{n} and let P ∈ R W ×W be the matrix obtained from P by deleting the last row and column. Likewise, let û, r ∈ R W be the vectors obtained from u, r by deleting their last coordinates. Let π ∈ ]0, 1] V be the stationary distribution of P and denote η = v∈V π v r v ∈ R, so that χ = η(1, 1, . . . , 1). We note that |η| r ∞ . The definition of the bias vector and the fact that u n = 0 imply the equality P û = η + ûr. Since W is an open set, Lemma 2.4 gives û = (I -P ) -1 (-η + r). Hence, Lemma 3.6 shows that û ∞ 2 r ∞ (n -1) min{D, M n-1 } 2 r ∞ n min{D, M n-1 } .

To prove the second case, note that the kernel of the matrix (I -P ) is equal to {λ(1, 1, . . . , 1) : λ ∈ R}. Therefore, the set of bias vectors of (r, P ) is given by {λ + u : λ ∈ R}, where u is a bias such that u n = 0. Thus, all bias vectors have the same Hilbert seminorm and the previous case gives

u H = u H 2 u ∞ 4 r ∞ n min{D, M n-1 } .
Since π T u = 0, for all v ∈ V we get

|u v | = | w∈V π w (u v -u w )| max w∈V |u v -u w | u H 4 r ∞ n min{D, M n-1 } .

Figure 1 .

 1 Figure 1. A rooted forest with two roots.

1 1Figure 3 .

 13 Figure 3. A Markov chain from Example 3.5.

3. 2 .Lemma 3 . 6 . 1 ∞

 2361 Estimating a bias vector. We now give our estimates concerning bias vectors. Our proof of Theorem 1.5 is based on the following lemma. Suppose that W ⊂ V is open and let P W ×W denote the submatrix of P formed by the rows and columns from W . Then, we have(I -P ) -w∈W M w min{D, M n-1 }. Proof. Let D W := w∈W M w . We have D W min{D, M n-1 } because W has at most n -1 states. By Lemma 2.4, we have (I -P ) -1 vw = ζ W vw for all v, w ∈ W . Fix v, w and let τ W = inf{ 1 : X / ∈ W } denote the moment when the Markov chain leaves W for the first time. Moreover, let Z := τ W -1

  Proof of Corollary 1.4. Let C 1 , . . . , C p denote the recurrent classes of X . Furthermore, for every ∈ [p] let π ( ) ∈ R C be the stationary distribution on C and let D ∈ N be defined as D := v∈C M v . By combining Theorems 1.1 and 1.3 we get that the lowest common denominator of the numbers ψ(v, C ) v∈V, ∈[p] , π |C 1 | . . . |C p |D 1 . . . D p D T = |C 1 | . . . |C p |D . Therefore, (1) implies that the numbers (χ v ) v∈V are rational and that their lowest common denominator is not greater than |C 1 | . . . |C p |D. By the inequality of arithmetic and geometric means we get |C 1 | . . . |C p | (s/p) p . Furthermore, the function f : R >0 → R defined as f (p) := p ln(s) -p ln(p) achieves its maximum when ln(p) = ln(s) -1, i.e., p = s/e. Therefore, we get (s/p)

	( ) v	∈[p],v∈C	is not greater than

p e s/e . Since e 1/e < 1.5 < √ 3, we obtain |C 1 | . . . |C p | 3 s/2 , which finishes the proof.

Proof of Theorem 1.5. The proof of both cases follows from Lemma 3.7 using the same argument, so we focus only on i). Let S := ∪ p =1 C denote the set of recurrent states of X and W := V \ S denote the set of transient states. For every , let P ( ) ∈ R C ×C denote the submatrix of P formed by the rows and columns with indices in C , and let u ( ) , r ( ) ∈ R C denote the restrictions of u, r to the indices from C . The equations ( 1) and ( 4) imply that u ( ) is a bias of (r ( ) , P ( ) ). Therefore, Lemma 3.7 implies that for all

denote the submatrix of P formed by the rows from W and columns from S and P ∈ R W ×W denote the submatrix of P formed by the rows and columns from W . Define a vector u ∈ R S as ∀v ∈ S, u v := u ( ) v , where is such that v ∈ C . Furthermore, let χ, û, r ∈ R W denote the vectors χ, u, r restricted to the coordinates from W . By the definition of the bias vector we have P û + P u = χ + ûr. Since W is an open set, Lemma 2.4 gives û = (I -P ) -1 (-χ + r + P u). Moreover, (1) implies that χ ∞ r ∞ . Hence, by Lemma 3.6 we get

Furthermore, let R := (I -P ) -1 P ∈ R W ×S . By [START_REF] Kemeny | Finite Markov Chains[END_REF]Theorem 3.5.4], for every w ∈ W, v ∈ S, R wv is the probability that the Markov chain starting at w goes to v when it leaves W . Hence R wv 0 and v∈S R wv = 1 for all w ∈ W . Therefore, we get

and so û ∞ 2 r ∞ n min{D, M n-1 }.